LZ78
LZ78 ist der 1978 von Lempel und Ziv vorgeschlagene Wörterbuch-Kompressionsalgorithmus; er baut ein explizites Wörterbuch auf und kodiert Daten als Paare (Wörterbuchindex, Literal).
Zweck
Erreicht universelle verlustfreie Kompression über ein explizites Wörterbuch; direkter Vorläufer von LZW.
Mechanismus
Es wird ein ab 1 nummeriertes Wörterbuch gehalten; beim Scannen der Eingabe wird das längste bereits im Wörterbuch vorhandene Präfix gesucht, (Index, nächstes Zeichen) ausgegeben und dieses Präfix plus Zeichen ins Wörterbuch eingefügt. Das Wörterbuch wird online aufgebaut und muss nie übertragen werden.
Anwendungsfälle
- Grundlage des LZW-Algorithmus
- Allgemeine Kompression
- Theoretische Analyse und Lehre