> bwt | transformér | komprimer <

// Burrows-Wheeler Transform - reversibel teksttransformation, der gør komprimering mere effektiv

INPUT 0 tegn

Vis rotationsmatrix

Tilføj EOF-marker ($)

OUTPUT 0 tegn

>> funktioner

[REVERSIBLE]

Fuldt reversibel

Tabsfri transformation der kan vendes præcist tilbage til originalen.

[CLUSTERING]

Tegnklyngedannelse

Samler lignende tegn, så efterfølgende kodere kan komprimere mere effektivt.

[BZIP2]

Kernen i bzip2

Grundlag for mange komprimeringsalgoritmer i bzip2-familien.

>> tekniske detaljer

Sådan fungerer BWT

Burrows-Wheeler-transformen laver alle cykliske rotationer af inputstrengen, sorterer dem leksikografisk og returnerer den sidste kolonne i den sorterede matrix sammen med indekset for den oprindelige streng. Det giver lange sekvenser af ens tegn, som komprimeres særligt godt med RLE, Move-to-Front og andre entropikodere.

BWT-eksempel

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

Hvorfor bruge BWT

Forbedrer hvor godt data kan komprimeres
Reversibel uden tab af information
Samler lignende kontekster i blokke
Bygger på samme principper som bzip2
Effektiv forbehandling til andre komprimeringsmetoder

>> ofte stillede spørgsmål

Hvad er Burrows-Wheeler-transformen?

Burrows-Wheeler-transformen (BWT) er en reversibel algoritme, der omarrangerer en tekststreng, så den får lange sekvenser af lignende tegn. Den blev foreslået af Michael Burrows og David Wheeler i 1994 og bruges som forbearbejdning i kompressorer som bzip2 for at opnå bedre komprimeringsgrad.

Hvorfor giver BWT bedre komprimering?

BWT grupperer tegn, der optræder i lignende kontekster, så mange forekomster af det samme symbol ender ved siden af hinanden i output. Sådanne sekvenser komprimeres meget effektivt med RLE, Move-to-Front og entropikodning som eksempelvis Huffman.

Hvad er EOF-markøren?

EOF-markøren (End Of File), typisk symbolet '$' eller et andet unikt tegn, sikrer at alle rotationer er entydige og gør det muligt at finde positionen for den oprindelige streng. Uden den ville nogle strenge ikke have en entydig repræsentation. Ved den inverse transformation fjernes EOF-markøren igen.

Er BWT i sig selv en komprimeringsalgoritme?

Nej. BWT komprimerer ikke direkte, men omformer data, så de er lettere at komprimere. Den kombineres typisk med Move-to-Front, RLE og Huffman-kodning i skemaer som bzip2.