> bwt | transformeer | comprimeer <

// Burrows-Wheeler Transform - reversibele teksttransformatie om compressie te verbeteren

INVOER 0 tekens

Rotatiematrix weergeven

EOF-markering ($) toevoegen

UITVOER 0 tekens

>> functies

[REVERSIBLE]

Volledig reversibel

Verliesvrije transformatie die exact ongedaan kan worden gemaakt.

[CLUSTERING]

Karakterclustering

Groepeert vergelijkbare tekens zodat latere coders beter kunnen comprimeren.

[BZIP2]

Kern van bzip2

Basis van veel compressieschema s geïnspireerd door bzip2.

>> technische info

Hoe BWT werkt

De Burrows-Wheeler-transformatie genereert alle cyclische rotaties van de invoerstring, sorteert deze lexicografisch en geeft de laatste kolom van de gesorteerde matrix terug samen met de index van de originele string. Dit zorgt ervoor dat vergelijkbare tekens bij elkaar worden geplaatst, wat zeer goed samenwerkt met RLE, Move-to-Front en andere entropiecoders.

BWT-voorbeeld

Input: "banana$"

Rotations:
0: banana$
1: anana$b
2: nana$ba
3: ana$ban
4: na$bana
5: a$banan
6: $banana

Sorted:
0: $banana
1: a$banan
2: ana$ban
3: anana$b
4: banana$
5: na$bana
6: nana$ba

Last column: annb$aa
Original index: 4

Output: annb$aa|4

Waarom BWT gebruiken

Verbetert de comprimeerbaarheid van gegevens
Volledig omkeerbaar
Groepeert vergelijkbare contexten
Basis van het bzip2-compressiealgoritme
Effectieve voorbewerking voor andere coders

>> veelgestelde vragen

Wat is de Burrows-Wheeler-transformatie?

De Burrows-Wheeler-transformatie (BWT) is een omkeerbaar algoritme dat een tekenreeks herordent om reeksen met veel herhaalde symbolen te produceren. Het werd in 1994 voorgesteld door Michael Burrows en David Wheeler en wordt als voorbewerkingsstap gebruikt in compressoren zoals bzip2 om betere compressieratio s te behalen.

Waarom verbetert BWT de compressie?

BWT groepeert tekens die in vergelijkbare contexten voorkomen, zodat veel voorkomens van hetzelfde symbool dicht bij elkaar in de uitvoer staan. Deze reeksen laten zich zeer goed comprimeren met run-length-codering, Move-to-Front en entropiecodering zoals Huffman.

Wat is de EOF-markering?

De EOF-markering (End Of File), meestal het symbool '$' of een ander uniek teken, zorgt ervoor dat alle rotaties uniek zijn en dat de positie van de oorspronkelijke string kan worden teruggevonden. Zonder deze markering zouden sommige strings geen unieke voorstelling hebben. Bij de inverse transformatie wordt de markering verwijderd.

Is BWT op zichzelf een compressie-algoritme?

Nee. BWT comprimeert niet rechtstreeks, maar zet gegevens om zodat ze beter te comprimeren zijn. In schema s zoals bzip2 wordt BWT gecombineerd met Move-to-Front, RLE en Huffman-codering.