Burrows-Wheeler-Transformation

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Die Burrows-Wheeler-Transformation (BWT) bezeichnet einen Algorithmus, welcher in Datenkompressionstechniken wie bzip2 Anwendung findet. Er wurde von Michael Burrows und David Wheeler entwickelt.

Inhaltsverzeichnis

1 Verfahren
- 1.1 Bemerkungen zur Sortierung
- 1.2 Warum funktioniert diese Transformation
2 Beispiel
3 Literatur
4 Weblinks

[Bearbeiten] Verfahren

Wenn eine Zeichenkette durch BWT umgeformt wird, bleiben alle Zeichen erhalten – der Algorithmus verändert lediglich die Anordnung der Zeichen. Kommen in der ursprünglichen Zeichenkette mehrmals identische Zeichenfolgen vor, so wird die erzeugte Kette mehrere Stellen enthalten, an denen sich ein einzelnes Zeichen wiederholt. Dieses Verfahren ist bei einer Kompression nützlich, da es leichter ist, eine Zeichenkette mit mehreren, sich wiederholenden Zeichen durch Techniken wie die Lauflängenkodierung zu komprimieren.

Zum Beispiel wird die folgende Zeichenkette SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES in eine Zeichenkette umgewandelt*, welche aufgrund ihrer sich wiederholenden Zeichen einfacher zu komprimieren ist: TEXYDST.E.XIIXIXXSMPPSS.B...S.EEUSFXDIOIIIIT

Die Transformation erfolgt, indem alle Rotationen des Textes sortiert und anschließend die letzte Spalte genommen wird. Der Text „.ANANAS.“ wird z. B. durch folgende Schritte in „.NNAAA.S“ umgewandelt:

Eingabe	Alle Rotationen	Zeilen sortieren	Ausgabe
.ANANAS.	.ANANAS. ..ANANAS S..ANANA AS..ANAN NAS..ANA ANAS..AN NANAS..A ANANAS..	ANANAS.. ANAS..AN AS..ANAN NANAS..A NAS..ANA S..ANANA .ANANAS. ..ANANAS	.NNAAA.S

Der folgende Pseudocode gibt ein (allerdings ineffizientes) Beispiel, wie die BWT und ihre Umkehrung zu berechnen ist. Es wird davon ausgegangen, dass es ein Sonderzeichen 'EOF' als Endmarkierung gibt, welches den Text abschließt, nirgendwo anders im Text vorkommt und während der Sortierung ignoriert wird.

 function BWT (string s)
   create a list of all possible rotations of s
   let each rotation be one row in a large, square table
   sort the rows of the table alphabetically, treating each row as a string
   return the last (rightmost) column of the table

 function inverseBWT (string s)
   create an empty table with no rows or columns
   repeat length(s) times
       insert s as a new column down the left side of the table
       sort the rows of the table alphabetically
   return the row that ends with the 'EOF' character

Das Bemerkenswerte ist nicht etwa, dass der Algorithmus eine einfacher kodierte Ausgabe erzeugt – eine Reihe trivialer Operationen würde dies ebenfalls tun. Das Bemerkenswerte ist, dass der Algorithmus umkehrbar ist, der Originaltext also nur aus den Daten der letzten Spalte rekonstruierbar ist.

Zur Umkehrung wird dieselbe Tabelle wie oben verwendet, jedoch werden alle Spalten mit Ausnahme der letzten gelöscht. Durch die letzte Spalte sind alle Zeichen des Textes bekannt. Um die erste Spalte wiederherzustellen genügt es also, diese erneut zu sortieren. Die letzte vor die erste Spalte gesetzt, ergeben sich alle Zeichenpaare des Originaltextes. Sortiert man diese Liste, so ergeben sich die erste und zweite Spalte. Wiederholt man diese Schritte, so lässt sich die komplette Tabelle rekonstruieren. Anschließend lässt sich die Zeile mit dem Originaltext unter Kenntnis der Endmarkierungen (im obigen Beispiel Punkte an Start und Ende) auffinden.

Durch eine Reihe von Optimierungen können diese Algorithmen effizienter laufen, ohne die Ausgabe zu ändern. Im BWT-Algorithmus ist es nicht nötig, die Tabelle zu speichern. Jede Reihe der Tabelle kann durch einen einzelnen Zeiger auf die jeweilige Zeichenkette repräsentiert werden. Bei der Umkehrung muss weder die Tabelle gespeichert, noch müssen die mehrfachen Sortierungen durchlaufen werden. Es genügt, die Zeichenkette s einmalig mit einem stabilen Sortierverfahren zu sortieren und zu vermerken, wohin sich jedes Zeichen bewegt hat. Dadurch erhält man eine single-cycle permutation, whose cycle is the output. Ein Zeichen im Algorithmus kann ein Byte, ein Bit oder eine andere passende Größe sein.

Es ist noch nicht einmal nötig, eine Endmarkierung zu besitzen: Stattdessen kann ein Zeiger verwendet werden, der sich „merkt“, wo in der Zeichenkette die Endmarkierung wäre. Auf diese Weise müsste die Ausgabe der BWT sowohl die umgeformte Zeichenkette, als auch den Wert des Zeigers enthalten. Dies bedeutet, dass die BWT ihre Eingabe leicht vergrößert. Die umgekehrte Transformation verkleinert diese jedoch wieder auf ihre Originalgröße: Ihr wird eine Zeichenkette und ein Zeiger übergeben, worauf sie nur eine Zeichenkette liefert.

Eine komplette Beschreibung der Algorithmen kann in Burrows und Wheelers Veröffentlichung oder einer Zahl von Onlinequellen gefunden werden.

Eine Beispielimplementation (in C, mit englischen Kommentaren) findet sich in dem polnischen Wikipedia-Artikel.

[Bearbeiten] Bemerkungen zur Sortierung

Mit einer POSIX-Sortierung erhält man einen leicht anderen String

TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT

statt

TEXYDST.E.XIIXIXXSMPPSS.B...S.EEUSFXDIOIIIIT

ISO 8859 hat komplexe Zuordnungsregeln, ignoriert aber Punkte. Posix-Zuordnung behandelt Punkte wie sonstige Zeichen (z. B. Buchstaben).

Die genaue Art der Sortierung spielt allerdings keine Rolle, so lange die Transformation und die Rücktransformation mit dem gleichen Sortierverfahren arbeiten.

[Bearbeiten] Warum funktioniert diese Transformation

Der Grund, warum diese Transformation funktioniert erschließt sich, wenn man mit etwas Abstand auf den Algorithmus sieht. Dann kann man folgendes beobachten:

zuerst werden alle Teilstrings der zu kodierenden Zeichenkette erzeugt (die zyklische Betrachtung der Zeichenkette hat dabei nur eine kleine Auswirkung auf das Ergebnis, da der Algorithmus erst bei großen Datenmengen effizient arbeitet)
diese Teilstrings werden sortiert
dann wird jeweils das Zeichen vor den sortierten Teilstrings ausgegeben

Zeichen haben vor bestimmten Zeichenketten aber eine gute Vorhersehbarkeit. Z. B wird in einem deutschen Text vor einem großen Buchstaben oft ein Leerzeichen stehen. Genauso ist die Wahrscheinlichkeit für ein ‚q‘ vor einem ‚u‘ viel größer als vor einem ‚w‘. Da aber durch die Sortierung alle Teilstrings mit einem ‚u‘ am Anfang aufeinander folgen, sind auch viele der ‚q‘s an einer Stelle konzentriert in der Ausgabe.

[Bearbeiten] Beispiel

Hier ein Beispiel – „Wikipedia!“ für MTF-Algorithmus (Move-To-Front-Algorithmus)

(0) Wikipedia! -> !Wikipedi[a]
(1) ikipedia!W    a!Wikiped[i]
(2) kipedia!Wi    dia!Wikip[e]
(3) ipedia!Wik    edia!Wiki[p]
(4) pedia!Wiki    ia!Wikipe[d]
(5) edia!Wikip    ikipedia![W] <- "Wikipedia!" << "ikipedia!W"
(6) dia!Wikipe    ipedia!Wi[k]
(7) ia!Wikiped    kipedia!W[i]
(8) a!Wikipedi    pedia!Wik[i]
(9) !Wikipedia    Wikipedia[!]

Den Startindex erhält man, in dem man das Original einmal nach links rotiert, und dann in der sortierten Liste nach diesem Eintrag sucht. in diesem Fall Index 5. Enkodiert heißt es also „aiepdWkii!“, 5. Dieser Text hat ein Verhältnis von „!adeikpW“ = 1:1:1:3:1:1:1.

Jetzt muss man ein Alphabet mit allen enthaltenen Zeichen erstellen, den auch der Decoder kennen muss. In der Praxis also am besten eine ASCII-Tabelle. In unserem Beispiel nur „!adeikpW“

Die Zeichen des enkodierten Textes werden im Alphabet gesucht, und nur deren Index abgespeichert. Nach jedem gefundenen Zeichen wird dieses aus dem Alphabet gelöscht und vorne angehangen. Der folgende Index bezieht sich somit auf ein völlig neues Alphabet:

                 !adeikpW
a -> Index [1] | a!deikpW
i -> Index [4] | ia!dekpW
e -> Index [4] | eia!dkpW
p -> Index [6] | peia!dkW
d -> Index [5] | dpeia!kW
W -> Index [7] | Wdpeia!k
k -> Index [7] | kWdpeia!
i -> Index [5] | ikWdpea!
i -> Index [0] | ikWdpea!
! -> Index [7]

Der zweite enkodierte Text heißt demzufolge „1446577507“, 5 der ein Verhältnis von „146570“ = 1:2:1:1:3:1 hat. Zum Vergleich, BWT ohne MTF hatte 1:1:1:3:1:1:1. Damit lässt sich für Huffmankomprimierung eine deutlich bessere Kompressionsrate erreichen.

Um MTF wieder zu dekodieren, geht man den umgekehrten Weg:

                 !adeikpW
Index 1 -> [a] | a!deikpW
Index 4 -> [i] | ia!dekpW
Index 4 -> [e] | eia!dkpW
Index 6 -> [p] | peia!dkW
Index 5 -> [d] | dpeia!kW
Index 7 -> [W] | Wdpeia!k
Index 7 -> [k] | kWdpeia!
Index 5 -> [i] | ikWdpea!
Index 0 -> [i] | ikWdpea!
Index 7 -> [!]

Decodiert: „aiepdkWkii!“, 5

Jetzt müssen wir den decodierten Text sortieren: „aiepdkWkii!“ → „!adeiiikpW“, denn daraus lässt sich der Transformationsvektor errechnen. Man geht jedes Zeichen vom sortierten Text durch, und sucht dieses im Unsortierten. Der Index im unsortierten Text wird im Vektor gesichert, und das Zeichen im unsortierten Text „gelöscht“:

 0   1   2   3   4   5   6   7   8   9
---------------------------------------
 a   i   e   p   d   W   k   i   i  [!]
[!]  a   d   e   i   i   i   k   p   W
---------------------------------------
[9]

 0   1   2   3   4   5   6   7   8   9
---------------------------------------
[a]  i   e   p   d   W   k   i   i
 !  [a]  d   e   i   i   i   k   p   W
---------------------------------------
 9   0

 0   1   2   3   4   5   6   7   8   9
---------------------------------------
     i   e   p  [d]  W   k   i   i
 !   a  [d]  e   i   i   i   k   p   W
---------------------------------------
 9   0  [4]

...

 0   1   2   3   4   5   6   7   8   9
---------------------------------------
                    [W]
 !   a   d   e   i   i   i   k   p  [W]
---------------------------------------
 9   0   4   2   1   7   8   6   3  [5]

Der Transformationsvektor lautet demzufolge „9042178635“.

Startindex I ist 5
L = „aiepdWkii!“
F = „!adeiiikpW“
T = „9042178635“

             I = 5
L(5) = [W] | I = T(5)
L(7) = [i] | I = T(7)
L(6) = [k] | I = T(6)
L(8) = [i] | I = T(8)
L(3) = [p] | I = T(3)
L(2) = [e] | I = T(2)
L(4) = [d] | I = T(4)
L(1) = [i] | I = T(1)
L(0) = [a] | I = T(0)
L(9) = [!]

Decodiert lautet das ganze wieder „Wikipedia!“.

[Bearbeiten] Literatur

M. Burrows and D. Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994.

[Bearbeiten] Weblinks

Dieser Artikel ist eine leicht veränderte Übersetzung aus der englischen Wikipedia. Der Originaltext in der verwendeten Version vom So, 19. Dezember 2004 13:20 CET (12:21, 30. November 2004) befindet sich unter en:Burrows-Wheeler_transform.

Von „http://de.wikipedia.org../../../b/u/r/Burrows-Wheeler-Transformation_d59d.html“

Kategorie: Kompressionsalgorithmus