Move to front

Dieser Artikel wurde am 10. Januar 2007 auf den Seiten der Qualitätssicherung eingetragen. Bitte hilf mit, ihn zu verbessern, und beteilige dich bitte an der Diskussion!

Folgendes muss noch verbessert werden: Braucht sprachliche Verbesserung -- HardDisk ^{rm -rf} 18:15, 10. Jan. 2007 (CET)

Move to front (MTF) ist ein Kodierungsverfahren. Es eignet sich gut, 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 (englisch „Nach vorne verschieben“). Dies wird für jeden Buchsaben des Textes durchgeführt. Das führt dazu, dass viele Zeichen, die direkt aufeinander folgen, nur einmal an die Spitze geholt werden und 0 eine Art „Wiederhohlungszeichen“ ist. Die Huffman-Kodierung kann so deutlich effizienter arbeiten. Die MTF-Kodierung ist umkehrbar, wenn die anfangs verwendete Tabelle bekannt ist, meistens enspricht sie einem Zeichensatz (z. B. dem ASCII) Ein Beispiel in Pseudocode:

 T sei eine Tabelle und eine Kopie der ASCII-Tabelle

 function mft(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 hinter verschoben)
   entferne Element i (die Felder rücken nach)
 return i

 T sei eine Tabelle und eine Kopie der ASCII-Tabelle

 function un-mtf(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

Beispiel

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

Zunächst muss zunächst durch die Burrows-Wheeler-Transformation

(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 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 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 Also wie vorher. Dier Text kann jetzt mit der BWT zurrückübersetzt werden, was hier nicht beschrieben werden soll.

Literatur

c't Magazin für computer technik, Hannover 16/00, S. 194: Packen wie noch nie