Wörterbuchkompression

Wörterbuchkompression, auch Stringersatzverfahren oder Substitutionskompression, bezeichnet alle Datenkompressionsverfahren, die die Rohdaten nach wiederkehrenden Zeichenfolgen absuchen, um diese einem Ersatzsymbol zugeordnet in ein sogenanntes Wörterbuch auszulagern und mit dem Symbol (z. B. der Position im Wörterbuch) zu ersetzen.

Oft werden Wörterbuchverfahren mit anderen Verfahren kombiniert, die andere Formen von Redundanz ausnutzen. Sehr häufig ist die Kombination mit nachfolgender Entropiekodierung.

Methoden

Manche Wörterbuchverfahren benutzen ein statisches Wörterbuch, dessen Einträge schon vor der Kodierung feststehen und dabei nicht verändert werden.

Gebräuchlicher sind Verfahren, die mit einem leeren oder einem vorgegebenen Wörterbuch beginnen und dieses während des Kodierens entsprechend dem Inhalt aufbauen.

Beispiele

Die von Abraham Lempel und Jacob Ziv 1977 und 1978 veröffentlichten Verfahren LZ77 und LZ78 und deren zahlreiche Abkömmlinge und Varianten (LZW, LZSS, LZMA, LZO …) gründen auf diesem Prinzip.

Ein anderes Beispiel ist Sequitur.