De Burrows-Wheelertransformatie (BWT) is een transformatie die toegepast wordt op tekst om ervoor te zorgen dat de tekst makkelijker te comprimeren is. Zo goed als alle compressie-algoritmen (zoals het gekende ZIP-algoritme) gebruiken de BWT als eerste stap voordat ze beginnen te comprimeren. Het doel van BWT is om de tekst zodanig om te werken, dat je veel herhalingen van letters krijgt. De getransformeerde tekst is nog steeds even lang als de oorspronkelijke, maar is wel gemakkelijker te comprimeren. Bepaalde compressiealgoritmes werken namelijk beter op teksten met veel herhalingen van letters.
We kunnen de BWT bijvoorbeeld toepassen op het woord sinaasappel. Om de BWT toe te passen, schrijven we het woord iedere keer één positie geroteerd onder elkaar:
sinaasappel
inaasappels
naasappelsi
aasappelsin
asappelsina
sappelsinaa
appelsinaas
ppelsinaasa
pelsinaasap
elsinaasapp
lsinaasappe
Nu sorteren we deze elf strings alfabetisch:
aasappelsin
appelsinaas
asappelsina
elsinaasapp
inaasappels
lsinaasappe
naasappelsi
pelsinaasap
ppelsinaasa
sappelsinaa
sinaasappel
Merk op dat het oorspronkelijke woord sinaasappel hier toevallig op de elfde rij voorkomt (over het algemeen hoeft dit niet de laatste rij te zijn). Het resultaat van de BWT is de tekenreeks gevormd door de laatste kolom van deze matrix: nsapseipaal. Het opmerkelijke van de Burrows-Wheelertransformatie is dat hij omkeerbaar is: als je bijhoudt op welke rij het originele woord voorkwam in de gesorteerde matrix (hier de elfde), dan kan je uit de tekenreeks nsapseipaal en het getal 11 het woord sinaasappel terugvinden.
Schrijf een programma dat een tekenreeks inleest uit een bestand en als resultaat de overeenkomstige BWT van deze tekenreeks teruggeeft. Elk bestand dat we hier uittesten, bevat slechts één tekenreeks en bestaat uit slechts één regel.
Invoer:
sinaasappel
Uitvoer:
nsapseipaal