Dekodierung

Als Ausgangsbasis für die Dekodierung erhält der Algorithmus einen Datenstrom und ein initialisiertes Lexikon (im Falle eines Textes wird das Lexikon mit 256 Einträgen initialisiert).

LZW verwendet bei der Dekodierung zwei Zwischenspeicher, diese werden als Buffer und Variable bezeichnet.

Der Datenstrom wird Zeichen für Zeichen eingelesen. Da das erste Zeichen immer im Lexikon vorhanden sein muss, wird dieser Vorgang außerhalb der Schleife durchgeführt, d.h. das Zeichen wird eingelesen und der "substring" des Zeichens in einer Variable gespeichert. Diese Variable wird dann ausgegeben und der Buffer wird der Variable gleichgesetzt.

Nun wird das nächste Zeichen eingelesen.

Befindet sich der Code des Inputs (eingelesenes Zeichen) bereits im Lexikon, so wird die Variable dem "substring" des Inputs gleichgesetzt. Ist der Code noch nicht im Lexikon vorhanden, handelt es sich um einen Sonderfall, der nicht besonders oft auftritt. In diesem Fall wird in die Variable der Buffer und das 1. Zeichen des Buffers geschrieben.

Die Variable wird nun ausgegeben und der Buffer plus das 1. Zeichen der Variable in das Lexikon geschrieben, d.h. das Lexikon wird um den Eintrag Buffer plus 1. Zeichen der Variable erweitert.

Abschließend wird der Buffer noch auf die Variable gesetzt und der Vorgang kann von vorne beginnen, sofern nicht das Ende des Datenstroms erreicht worden ist.

Bei der nun folgenden Animation wird der in der Animation im Kapitel "Kodierung" kodierte Datenstrom wieder dekodiert. Bei der Initialisierung des Lexikons werden zu Vereinfachung nur jene Einzelzeichen ins Lexikon eingetragen, die auch im dekodierten Datenstrom vorkommen.

Ergänzende und vertiefende Module