Burrwos-Wheeler-Transformation

eine umkehrbare Transformation, die (im Allg.) einen viel besser komprimierbaren String erzeugt.

Beispiel: abraca.

alle zyklischen
Permutationen:

("abraca",0)
("bracaa",1)
("racaab",2)
("acaabr",3)
("caabra",4)
("aabrac",5)

diese sortieren
(lexikographisch):

("aabrac",5)
("abraca",0)
("acaabr",3)
("bracaa",1)
("caabra",4)
("racaab",2)

Folge der letzten Buchstaben und Position der 0:

("caraab", 1)

daraus kann man die Eingabe rekonstruieren!