Verlustfreie Kompression ist dadurch begrenzt, wie viel Redundanz ein Verfahren erkennen kann. Verfahren der LZ-Familie und die Huffman-Kodierung erreichen bei gewöhnlichem Text jeweils ein Plateau.
Der DEC-Bericht von Burrows und Wheeler aus dem Jahr 1994 beschrieb eine blocksortierende Transformation: Man listet jede Rotation des Blocks auf, sortiert sie und gibt die letzte Spalte aus. Da sich Rotationen Suffixe teilen, gruppieren sich identische Zeichen, und ein kurzer Durchlauf mit Run-Length- und Move-to-Front-Kodierung verwandelt dies in sehr wenige Symbole.
Die Transformation ist umkehrbar, sie ist also eine Umordnung und kein Verlust. Das Ergebnis floss in bzip2 ein, das Text wirksamer komprimierte als zeitgenössische Werkzeuge und das Verfahren zum Standard für langsame, aber dichte Kompression machte.
Sortiere die Rotationen des Blocks, sodass Gleichartiges nebeneinander steht
Das Sortieren der Rotationen bringt identische Symbole dort zusammen, wo der Kontext derselbe ist.
Run-Length- und Move-to-Front-Kodierung finden dann lange, günstige Läufe.
Die Transformation ist eine Permutation, daher ist die Dekompression exakt.
Sie wirkt auf jede wiederkehrende Struktur und ist daher nicht auf einen Dateityp zugeschnitten.
Ordne die Daten vor dem Komprimieren so um, dass identische Symbole nebeneinander stehen. Eine Transformation, die die vorhersagbaren Teile gruppiert, kann einen gewöhnlichen Kompressor dramatisch stärker machen.
Die Burrows-Wheeler-Transformation wurde zur Engine von bzip2 und später zur Grundlage des FM-Index, der Teilzeichenketten findet und Genome kartiert. Dieselbe Idee treibt heute Alignment-Werkzeuge der Bioinformatik mit hohem Durchsatz an.
DEN BELEGEN FOLGEN
Die Quellen
- A block-sorting lossless data compression algorithm DEC Systems Research Center Research Report 124 · web.stanford.edu
- Burrows-Wheeler transform Wikipedia · en.wikipedia.org