> 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.