> bwt | transformer | komprimer <
// Burrows-Wheeler Transform - reversibel teksttransformasjon som forbedrer komprimering
>> funksjoner
Fullt reversibel
Tapsfri transformasjon som kan reverseres nøyaktig tilbake til originalen.
Tegnklynger
Samler like tegn i blokker, slik at senere koding kan komprimere mer effektivt.
Kjernen i bzip2
Utgjør et viktig byggestein i komprimeringsalgoritmer av typen bzip2.
>> teknisk informasjon
Hvordan BWT fungerer
Burrows-Wheeler-transformasjonen lager alle sykliske rotasjoner av inndata-strengen, sorterer dem leksikografisk og returnerer den siste kolonnen i den sorterte matrisen sammen med indeksen til den opprinnelige strengen. Dette gir lange sekvenser av like tegn som kan komprimeres svært 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 bruke BWT
- Forbedrer hvor godt data kan komprimeres
- Reversibel og tapsfri transformasjon
- Samler like kontekster i sammenhengende blokker
- Bygger på samme teknikk som bzip2
- Effektiv forbehandling før videre koding
>> ofte stilte spørsmål
Hva er Burrows-Wheeler-transformasjon?
Burrows-Wheeler-transformasjon (BWT) er en reversibel algoritme som omorganiserer en tekststreng slik at mange like symboler samles i sammenhengende sekvenser. Den ble foreslått av Michael Burrows og David Wheeler i 1994 og brukes som forprosessering i kompressorer som bzip2 for å oppnå bedre komprimeringsgrad.
Hvorfor gir BWT bedre komprimering?
BWT grupperer tegn som opptrer i lignende kontekster, slik at de samme symbolene ofte havner ved siden av hverandre i resultatet. Slike sekvenser egner seg svært godt for run length-koding, Move-to-Front og entropikoding som Huffman.
Hva er EOF-markøren?
EOF-markøren (End Of File), vanligvis symbolet '$' eller et annet unikt tegn, sørger for at alle rotasjoner er entydige og gjør det mulig å finne posisjonen til den opprinnelige strengen. Uten denne markøren ville enkelte strenger ikke hatt en entydig representasjon. Under den inverse transformasjonen fjernes EOF-markøren.
Er BWT i seg selv en komprimeringsalgoritme?
Nei. BWT komprimerer ikke direkte, men omformer data til en form som er enklere å komprimere. I praksis kombineres den med Move-to-Front, RLE og Huffman-koding i skjemaer som bzip2.