Move to front

aus Wikipedia, der freien Enzyklopädie

Move to front (englisch „Nach vorne verschieben“) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows-Wheeler-Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu können. Dazu werden zunächst alle Zeichen, die in den Eingangsdaten vorkommen, in eine Tabelle geschrieben. Die Daten werden Zeichen für Zeichen verarbeitet. Dabei wird zunächst die Position der Buchstaben in der Tabelle ausgegeben und der Buchstabe an die Spitze der Tabelle gesetzt – daher auch der Name der Verfahrens, Move to front. Dies wird für jeden Buchstaben des Textes durchgeführt und führt dazu, dass viele Zeichen, die direkt aufeinander folgen, nur einmal an die Spitze geholt werden und 0 eine Art „Wiederholungszeichen“ ist. Die Huffman-Kodierung kann so deutlich effizienter arbeiten. Die MTF-Kodierung ist umkehrbar, wenn die anfangs verwendete Tabelle bekannt ist, meistens entspricht sie einem Zeichensatz (z. B. dem ASCII) Ein Beispiel in Pseudocode:

T sei eine Tabelle und eine Kopie der ASCII-Tabelle
function moveToFront(Buchstabe B)
  Suche den Index zu B in T und speichere ihn in i
  füge b zu T mit index 0 hinzu. (alle Felder werden nach hinten verschoben)
  entferne Element i (die Felder rücken nach)
return i

T sei eine Tabelle und eine Kopie der ASCII-Tabelle
 function undoMoveToFront(Zahl i)
  Suche den Buchstaben zu i in T und Speichere ihn in B
  füge B mit Index 0 zu Tabelle T hinzu
  lösche Element i aus der Tabelle
  return B

[Bearbeiten] Beispiel

Hier ein Beispiel – „Wikipedia!“ für MTF-Algorithmus.

Zunächst erhält man durch die Burrows-Wheeler-Transformation folgende Matrix:

(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 Häufigkeitsverhältnis der aufgetretenen Zeichen von „!adeikpW“ = 1:1:1:1:3:1:1:1.

Jetzt muss man ein Alphabet mit allen enthaltenen Zeichen erstellen, den auch der Decoder kennen muss. In unserem Beispiel nur „!adeikpW“. Nun wird wie oben beschrieben vorgegangen:

                 !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 Häufigkeitsverhältnis der aufgetretenen Zeichen von „146570“ = 1:2:1:2:3:1 hat. Zum Vergleich, BWT ohne MTF hatte 1: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 Also wie vorher. Der Text kann jetzt mit der BWT zurückübersetzt werden, was hier nicht beschrieben werden soll.