Burrows-Wheelertransformatie
De Burrows-Wheelertransformatie (BWT) is een transformatie van een tekenreeks naar een vorm waarin deze gemakkelijker te comprimeren is. De bekendste toepassing van de Burrows-Wheelertransformatie is het programma bzip2. De Burrows-Wheelertransformatie verandert de volgorde van de tekens in een tekenreeks, de tekens zelf blijven ongewijzigd. Na de Burrows-Wheelertransformatie zullen veel tekens aaneengesloten naast elkaar zitten, zodat bijvoorbeeld het RLE-algoritme beter toegepast kan worden. Om een goede compressie te bereiken, moet de tekenreeks minimaal enkele kilobytes omvatten. De Burrows-Wheelertransformatie werd in 1983 uitgevonden door David Wheeler en in 1994 gepubliceerd door Michael Burrows en David Wheeler .
Algoritme[bewerken | brontekst bewerken]
Neem de tekenreeks 'sinaasappel' in het alfabet [a-z]* als voorbeeld van elf letters. Schrijf 'sinaasappel' om een Burrows-Wheelertransformatie toe te passen iedere keer een positie geroteerd onder elkaar:
sinaasappel inaasappels naasappelsi aasappelsin asappelsina sappelsinaa appelsinaas ppelsinaasa pelsinaasap elsinaasapp lsinaasappe |
Sorteer deze elf tekenreeksen. Sorteren op alfabet ligt voor de hand, maar een andere volgorde kan ook worden genomen, zolang bij het ongedaan maken maar dezelfde volgorde wordt gebruikt:
aasappelsin appelsinaas asappelsina elsinaasapp inaasappels lsinaasappe naasappelsi pelsinaasap ppelsinaasa sappelsinaa sinaasappel |
Noem de eerste kolom in deze gesorteerde matrix E en de laatste kolom L. De Burrows-Wheelertransformatie van een reeks tekens bestaat uit de kolom L, plus de verticale positie van de oorspronkelijke tekst in de matrix, in dit voorbeeld toevallig positie elf. De Burrows-Wheelertransformatie van de tekenreeks is dan ook:
11 |
nsapseipaal |
Het is mogelijk de Burrows-Wheelertransformatie om te keren. Wanneer L bekend is, is E daaruit te berekenen door L te sorteren. Bepaal daartoe uit deze twee tekenreeksen een transformatievector T en kijk voor ieder teken in L op welke positie deze in E voorkomt:
| L | E | T |
|---|---|---|
n s a p s e i p a a l |
a a a e i l n p p s s |
7 10 1 8 11 4 5 9 2 3 6 |
Haal de oorspronkelijke tekenreeks als volgt terug:
- Begin met de index van de Burrows-Wheelertransformatie, de positie van de oorspronkelijke tekst in de gesorteerde matrix, in dit geval een 11.
- Het 11e teken van L is een l. Kijk op positie 11 in T, daar staat een 6.
- Het 6e teken van L is een e. Er staat een 4 op positie 6 in T.
- Het 4e teken van L is een p. Er staat een 8 op positie 4 in T.
- Het 8e teken van L is een p, een 9 op positie 8 in T.
- Het 9e teken van L is een a, een 2 op positie 9 in T.
- Het 2e teken van L is een s, een 10 op positie 2 in T.
- Het 10e teken van L is een a, een 3 op positie 10 in T.
- Het 3e teken van L is een a, een 1 op positie 3 in T.
- Het 1e teken van L is een n, een 7 op positie 1 in T.
- Het 7e teken van L is een i, een 5 op positie 7 in T.
- Het 5e teken van L is een s met een 11 op positie 5 in T. Er wordt gestopt omdat de 11 gelijk is aan de index waarmee is begonnen.
Na het omkeren van dit voorlopige resultaat 'leppasaanis' komt de oorspronkelijke tekenreeks 'sinaasappel' weer terug.
Werkingsprincipe[bewerken | brontekst bewerken]
Het doel van Burrows-Wheelertransformatie is om de tekst zodanig om te werken, dat er veel herhalingen van letters komen. Bepaalde compressiealgoritmes werken namelijk beter op teksten met veel herhalingen van letters.
Het werken van Burrows-Wheelertransformatie berust op het feit dat in een natuurlijke taal bepaalde lettercombinaties meer voorkomen dan andere. Door de transformatie worden de letters gesorteerd op basis van de letterreeks die er op volgt. Bijvoorbeeld, de i in sinaasappel wordt gesorteerd op basis van de letterreeks 'naasap...'. Zo komt in het Nederlands na een 'c' vaak de 'h', dus zullen de letters 'c' in een Nederlandse tekst na een Burrows-Wheelertransformatie tranformatie vaak achter elkaar staan. Hoe langer de tekst, des te sterker het effect. Als in een publicatie van de bond van groentehandelaren het woord 'sinaasappel' tien keer voorkomt, vind je in de getransformeerde tekst alle s-en van dat woord achter elkaar.