> mtf | move | front <
// Move-to-Front – Dynamische Listen-Umsortierung für bessere Komprimierung
Selbstadaptiv
Passt sich automatisch lokalen Mustern in den Daten an.
Lokale Nähe ausnutzen
Kürzlich verwendete Symbole erhalten kleinere Indizes für bessere Komprimierung.
Teil von bzip2
Wird nach der BWT im bzip2-Komprimierungspipeline eingesetzt.
>> technische infos
Wie MTF funktioniert:
MTF verwaltet eine Liste aller möglichen Symbole. Beim Kodieren eines Symbols wird seine aktuelle Position in der Liste ausgegeben und das Symbol anschließend an den Anfang verschoben. Dadurch erhalten häufig verwendete Symbole kleine Indizes, die sich mit nachgelagerter Entropiekodierung besser komprimieren lassen.
Kodierungsbeispiel:
Text: "banana" Anfangsliste: [a,b,c,d,...] "b": Index 1, verschiebe b→Front [b,a,c,d,...] "a": Index 1, verschiebe a→Front [a,b,c,d,...] "n": Index 13, verschiebe n→Front [n,a,b,c,...] "a": Index 1, verschiebe a→Front [a,n,b,c,...] "n": Index 1, verschiebe n→Front [n,a,b,c,...] "a": Index 1, verschiebe a→Front [a,n,b,c,...] Ausgabe: [1,1,13,1,1,1]
Warum MTF verwenden:
- >Verbessert lokale Redundanz
- >Arbeitet zusammen mit BWT
- >Einfache Implementierung
- >Umkehrbare Transformation
- >Passt sich Mustern an
>> häufig gestellte fragen
Was ist Move-to-Front-Kodierung?
MTF ist ein Datentransformationsalgorithmus, der jedes Symbol als seinen Index in einer dynamisch aktualisierten Liste kodiert. Nach dem Kodieren wird das Symbol an den Anfang der Liste verschoben, sodass häufig verwendete Symbole kleine Indizes besitzen.
Warum MTF zusammen mit BWT verwenden?
Die BWT gruppiert ähnliche Kontexte und erzeugt lokale Wiederholungen. MTF wandelt diese Wiederholungen in kleine Zahlen (viele 0 und 1) um, die sich sehr gut mit Run-Length- oder Huffman-Kodierung komprimieren lassen.
Wie funktioniert die Liste?
Die Liste beginnt mit allen 256 möglichen Byte-Werten in Reihenfolge. Beim Kodieren werden verwendete Symbole an den Anfang verschoben. Kürzlich verwendete Symbole bleiben nahe der Front mit kleinen Indizes, während seltene Symbole nach hinten wandern.
MTF im Vergleich zu anderen Transformationen?
MTF ist speziell dafür entwickelt, nach der BWT eingesetzt zu werden. Allein ist es wenig effektiv, eignet sich aber hervorragend, um BWT-Ausgaben in eine gut komprimierbare Form zu bringen. Es ist einfacher als arithmetische Kodierung, aber weniger optimal.
// Durchgerechnetes Beispiel
| # | Symbol | Index | List |
|---|---|---|---|
| 1 | b | 1 | abcdefg… |
| 2 | a | 1 | bacdefg… |
| 3 | n | 13 | abcdefg… |
| 4 | a | 1 | nabcdef… |
| 5 | n | 1 | anbcdef… |
| 6 | a | 1 | nabcdef… |
// Codebeispiele
Input banana initial list: a b c d ... z (index from 0)
Output 1 1 13 1 1 1
Encode output the index of the symbol, then move it to the front
Decode read index, output list[index], move it to the front
Use after BWT: runs of equal symbols become runs of 0s,
which RLE and Huffman/arithmetic coding then compress well (bzip2)
>> Weitere Fragen
F: Wozu dient Move-to-Front?
A: MTF ist keine Kompression an sich, sondern eine Transformation: Zuletzt benutzte Symbole erhalten kleine Indizes. Dadurch entstehen viele Nullen und Einsen, die ein anschließender Entropiecoder (Huffman, arithmetisch) gut komprimiert.
F: Wie hängt MTF mit der Burrows-Wheeler-Transformation zusammen?
A: Die BWT gruppiert gleiche Zeichen zu Läufen. MTF macht daraus Folgen kleiner Zahlen, vor allem 0. Diese Kette BWT → MTF → RLE → Huffman verwendet bzip2.
F: Ist MTF verlustfrei und umkehrbar?
A: Ja. Der Decoder startet mit derselben Anfangsliste und verfolgt dieselben Verschiebungen. Die Anfangsliste (Alphabet und Reihenfolge) muss auf beiden Seiten identisch sein.