Burrows-Wheeler (Rekonstruktion)

(Bastel-Aufgabe/Auflösung)

• Codewort L = caraab, bestimme F = sort(L) = aaabcr
• berechne Z = zip(L, F) = [ca, aa, ra, ab, ac, br].
• sortiere: sort(Z) = [aa, ab, ac, br, ca, ra]
• verfolge Buchstaben entlang der Vertauschungen

Kann geschickt implementiert werden (mit Abzählen statt Sortieren) $\to$ Dekodierung geht schnell.

Kodierung geht auch schnell (Matrix muß nicht im Speicher stehen)

Algorithmus (Burrows-Wheeler $\to$ move-to-front $\to$ Huffman) ist implementiert in bzip2