Move-to-Front Transform
Die Move-to-Front-Transformation (MTF) hält eine Symboltabelle, gibt für jedes Symbol dessen aktuellen Index in der Tabelle aus und verschiebt es dann an den Anfang, sodass häufige Symbole kleine Indizes erhalten.
Zweck
Nach BWT wandelt sie die geballten identischen Zeichen in viele kleine Ganzzahlen um und erzeugt eine für Lauflängen- oder Entropiekodierung günstige Verteilung.
Mechanismus
Die Symboltabelle wird in einer Reihenfolge initialisiert; für jedes Symbol wird dessen aktueller Tabellenindex ausgegeben und es dann nach vorn verschoben — wiederholte Symbole ergeben 0. Die Dekodierung führt dieselben Tabellenoperationen umgekehrt aus.
Anwendungsfälle
- Zweite Stufe der bzip2-Kompression
- Nachbearbeitung nach BWT
- Ausnutzung von Lokalität