Move to front

Das Move to front Verfahren eignet sich gut um Daten die aus der Burrows-Wheeler-Transformation stammen weiter zu Verarbeiten 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. Dann wird der Buchstabe an die Spitze der Tabelle gesetzt (daher auch der Name der Verfahrens, Move to front(eng. Nach vorne verschieben))und anschließent der nächste Buchstabe verarbeitet. Dies führt dazu dass viele Zeichen, die direkt aufeinander folgen nur einmal an die Spize geholt werden und 0 eine Art "Wiederhohlungszeichen" ist. Die Huffman-Kodierung kann so deutlich effizenter 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 ein 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 ein 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

Literatur

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