Der Lempel Ziv Welch Algorithmus

Das LZW Verfahren wird sehr oft mit dem LZ Algorithmus gleichgesetzt. Dem ist aber nicht so. Der LZW Algorithmus ist eine Weiterentwicklung
des LZ78 Algorithmus welcher von Terry Welch entwickelt wurde(1984) und gehört somit auch zu der "Familie" der LZ Algorithmen.
Somit kam der Algorithmus auch zu seinem Namen [Lempel Ziv Welch Algorithmus (LZW)]. Welch entwickelte eine Verfahren zur Hardwareimplementierung
des Algorithmus welcher sowohl bei der Kompression als auch bei der Dekompression eine hohe Arbeitsgeschwindigkeit erreichte.

Der LZW Algorithmus erstellt das benötigte Wörterbuch zur Kodierung während der Ausführung. Dieses Wörterbuch nimmt
die bereits kodierten Zeichen mit auf. In den kodierten Daten sind einzig und allein die Referenzen der Einträge aus diesem Wörterbuch
enthalten. Die ersten 256 Einträge sind mit einzelnen Zeichen vorbesetzt und alle nachfolgenden Einträge repräsentieren längere
Zeichenketten. Der Algorithmus stellt hierbei sicher, dass das Wörterbuch sowohl bei der Kompression als auch bei der Dekompression genau nach dem
selben Schema erstellt wird. Hierfür werden geeignete Mechanismen und Definitionen im Algorithmus bereitgestellt.

Trotz aller Unterschiede habe die LZ Algorithmen auch einige Gemeinsamkeiten:

1.
 alle LZ Algorithmen haben eine verlustfreie Datenkompression
2.
 alle LZ Algorithmen benötigen zur Dekompression keine zusätzlichen Informationen über die Daten, wie dies zum Beispiel beim Huffman
Algorithmus der Fall ist (Baumdiagramm muss mit abgespeichert werden, sonst ist die Datei nicht rekonstruierbar).
Alle benötigten Daten werden während der Dekompression gewonnen.
3.
 die LZ Algorithmen eignen sich daher sehr gut dafür transparent für den Benutzer zum Beispiel im Modem Übertragungsprotokoll V.42
implementiert zu werden

Die Famile der LZ Algorithmen wir in zwei Hauptgruppen unterschieden:
A
 Gruppe A versucht die zu komprimierende Zeichenfolge in der schon erstellten Datenmenge zu finden. Anstatt Widerholungen wird lediglich
ein Zeiger (eine Art Referenz) auf das letzte Auftreten derselben Zeichenfolge abgespeichert. Das verwendete Wörterbuch wird also duch die
bereits erzeugte Datenfolge dargestellt.
Alle Variationen des LZ77 Verfahrens gehören zu dieser Gruppe.
B
 In der Gruppe B wird bei der Kompression ein neues Wörterbuch erzeugt - aus Zeichenfolgen - die in den Quelldaten auftreten. Wird nun eine
Zeichenkette in der Quelldatei gefunden die auch im Wörterbuch vorhanden ist, gibt der Algorithmus eine Meldung und es wird anstelle der
Zeichenkette ein Zeiger auf die Stelle im Wörterbuch abgespeichert. Das besondere an diesem Verfahren ist, dass das Wörterbuch während
der Dekompression wieder genauso erzeugt werden kann und somit nicht mit abgespeichert werden muss (Hauptunterschied zu Huffman).
Alle Variationen des LZ78 Verfahrens gehören zu dieser Gruppe.

Falls man sich tiefer in das Thema einlesen möchte findet man HIER bzw. HIER noch weitere Informationen zu den einzelnen Verfahren (LZ77 LZ78 LZSS LZC LZMW)