Datenkomprimierung Teil 3
Das Komprimierungsverfahren Lempel-Ziv (LZ) ist einer der beliebtesten verlustfreien Speicheralgorithmen.
DEFLATE ist eine Variante von LZ, die für die Dekomprimierungsgeschwindigkeit und das Komprimierungsverhältnis optimiert ist, obwohl die Komprimierungsgeschwindigkeit sehr langsam sein kann, PKZIP , gzip und PNG verwenden alle DEFLATE. LZW (Lempel-Ziv-Welch) war bis zum Ablauf des Patents im Juni 2003 ein Unisys-Patent, dieses Verfahren wurde für GIF-Bilder verwendet. Erwähnenswert ist auch das LZR (LZ-Renau)-Verfahren, das die Grundlage des Zip-Verfahrens bildet. Das LZ-Verfahren verwendet ein tabellenbasiertes Komprimierungsmodell, bei dem Tabelleneinträge durch wiederholte Datenstrings ersetzt werden. Bei den meisten LZ-Methoden wird diese Tabelle dynamisch aus den anfänglichen Eingabedaten generiert. Diese Tabelle wird häufig unter Verwendung von Huffman-Codierung (z. B. SHRI, LZX) geführt. Ein aktuelles LZ-basiertes Codierungsschema, das gut funktioniert, ist LZX , das im CAB-Format von Microsoft verwendet wird.
Die besten Komprimierungswerkzeuge verwenden probabilistische Modellvorhersagen für die arithmetische Codierung. Die arithmetische Codierung wurde von dem finnischen Informationstheoretiker Jorma Rissanen erfunden und von Witten, Neal und Cleary in eine praktische Methode umgewandelt. Dieser Ansatz ermöglicht eine bessere Komprimierung als der wohlbekannte Huffman-Algorithmus und ist gut geeignet für eine adaptive Datenkomprimierung, bei der Vorhersagen kontextsensitiv sind. Die arithmetische Codierung wurde im JBIG-Binärbildkomprimierungsstandard, dem DejaVu-Dokumentkomprimierungsstandard, verwendet. Das Dasher-Texteingabesystem ist ein umgekehrter arithmetischer Kodierer.