Stringersatzverfahren

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

Gebräuchlicher sind Verfahren, die mit einem Vorgabewörterbuch anfangen und dieses beim Kodieren dem verarbeiteten Inhalt anpassen oder es von Grund auf nach und nach 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, ...) gründen auf diesem Prinzip.

Ein anderes Beispiel ist Sequitur.