> bwt | transformera | komprimera <
// Burrows-Wheeler Transform - reversibel texttransformering som gör data lättare att komprimera
>> funktioner
Helt reversibel
Förlustfri transformering som kan återställas exakt till ursprungstexten.
Teckenklustring
Grupperar liknande tecken så att efterföljande kodare kan komprimera effektivare.
Kärnan i bzip2
En viktig byggsten i komprimeringsalgoritmer av bzip2-typ.
>> teknisk information
Hur BWT fungerar
Burrows-Wheeler-transformen skapar alla cykliska rotationer av indata-strängen, sorterar dem lexikografiskt och returnerar den sista kolumnen i den sorterade matrisen tillsammans med indexet för den ursprungliga raden. Detta ger långa serier av liknande tecken som kan komprimeras mycket väl med RLE, Move-to-Front och andra entropikodare.
BWT-exempel
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
Varför använda BWT
- Förbättrar hur väl textdata kan komprimeras
- Är helt reversibel och förlustfri
- Samlar liknande kontexter i sammanhängande block
- Utgör grund för komprimeringsalgoritmen bzip2
- Är ett effektivt förbehandlingssteg före vidare kodning
>> vanliga frågor
Vad är Burrows-Wheeler-transformen?
Burrows-Wheeler-transformen (BWT) är en reversibel algoritm som ordnar om en teckensträng så att långa serier av liknande symboler uppstår. Den föreslogs av Michael Burrows och David Wheeler 1994 och används som förbehandling i kompressorer som bzip2 för att uppnå bättre komprimeringsgrad.
Varför förbättrar BWT komprimeringen?
BWT grupperar tecken som uppträder i liknande kontexter, så att samma symbol ofta hamnar bredvid sig själv i resultatet. Sådana serier komprimeras mycket bra med run length-kodning, Move-to-Front och entropikodning som Huffman.
Vad är EOF-markören?
EOF-markören (End Of File), vanligtvis symbolen '$' eller något annat unikt tecken, gör alla rotationer entydiga och gör det möjligt att hitta den ursprungliga radens position. Utan den skulle vissa strängar sakna en unik representation. Vid den inversa transformeringen tas EOF-markören bort.
Är BWT i sig självt en komprimeringsalgoritm?
Nej. BWT komprimerar inte direkt utan omformar data till en form som är lättare att komprimera. I praktiken kombineras den med Move-to-Front, RLE och Huffman‑kodning i scheman som bzip2.