LZ78

LZ78 ist ein von Jacob Ziv und Abraham Lempel entwickeltes Verfahren zur Datenkompression. LZ78 ist der Nachfolger des ein Jahr zuvor erschienenen Algorithmus LZ77.

Während der LZ77-Algorithmus mit alten Daten arbeitet, zielt LZ78 auf neue Daten ab. Dies geschieht durch Vorwärts-Scannen des Eingabe-Puffers, der mit einem Wörterbuch verglichen wird. Der Algorithmus scannt durch den Puffer, bis kein Treffer mit dem Wörterbuch mehr erreicht wird. Sollte das passieren, wird die Position des Wortes im Wörterbuch – falls eine vorhanden ist – ausgegeben. Außerdem werden die Länge des Treffers und das Symbol, das den Fehler verursacht hat, ausgegeben. Das resultierende Wort wird dann dem Wörterbuch hinzugefügt.

Obwohl LZ78 am Anfang große Popularität erreichte, wurde einige Jahrzehnte nach seinem Erscheinen mehr auf LZ77 gesetzt, da in den USA bis 2003 und in Europa, Kanada und Japan bis ins Jahr 2004 Teile von LZ78 patentiert waren. Die bekannteste Form der LZ78-Kompression ist der LZW-Algorithmus, eine Modifikation des LZ78-Algorithmus durch Terry Welch.

Beispiel

Dieses Beispiel veranschaulicht die Arbeitsweise der am weitesten verbreiteten Variante des LZ78-Algorithmus, dem LZW. Es werden der Status der Ausgabe und das Wörterbuch in jedem Schritt angegeben. Um das Beispiel einfach zu halten, wird ein einfaches Alphabet verwendet, das sich nur aus Großbuchstaben zusammensetzt. Auf Leer- und Satzzeichen wurde verzichtet. Dieses Beispiel zeigt die Kompression einer sehr kurzen Nachricht. Bei echten Daten wird die Kompression erst ab einer bestimmten Länge deutlich sichtbar.

Die Nachricht, die in diesem Beispiel komprimiert wird, lautet:

   TOBEORNOTTOBEORTOBEORNOT#

Die Doppelkreuz („#“) markiert das Ende der Nachricht. Daraus folgt, dass das Wörterbuch zu Beginn 27 Einträge (26 Großbuchstaben und „#“) haben wird. Um das gesamte Wörterbuch darstellen zu können, sind 5 Bits nötig. Wenn das Wörterbuch wächst, werden mehr Bits benötigt um auf alle Elemente des Wörterbuchs zugreifen zu können. 5 Bits erlauben 32 mögliche Kombinationen von Bits. Deshalb werden ab dem 33. Eintrag 6 Bit lange Ketten verwendet. Der 33. Wörterbucheintrag wird als 32. gekennzeichnet, da die Zählung bei 0 beginnt.

Das Wörterbuch wird am Anfang folgendermaßen aussehen:

   # = 00000
   A = 00001
   B = 00010
   C = 00011
   …
   …
   …
   Z = 11010

Kodieren

Ohne LZ78-Algorithmus wäre die Nachricht 125 Bits lang (25 Zeichen × 5 Bits pro Zeichen). Nach dem Komprimieren werden wir die ursprüngliche Länge mit der neuen Länge vergleichen.

Noch mal die zu komprimierende Nachricht:

• TOBEORNOTTOBEORTOBEORNOT#

Zeichen:	Bit Code: (= Ausgabe)	Neuer Wörterbucheintrag:
T	20 = 10100	28: TO
O	15 = 01111	29: OB
B	2 = 00010	30: BE
E	5 = 00101	31: EO
O	15 = 01111	32: OR ← ab hier werden 6 Bits benötigt
R	18 = 010010	33: RN
N	14 = 001110	34: NO
O	15 = 001111	35: OT
T	20 = 010100	36: TT
TO	28 = 011100	37: TOB
BE	30 = 011110	38: BEO
OR	32 = 100000	39: ORT
TOB	37 = 100101	40: TOBE
EO	31 = 011111	41: EOR
RN	33 = 100001	42: RNO
OT	35 = 100011	43: OT#
#	0 = 000000

Nach der Kompression beträgt die Länge demnach nur noch 97 Bits (5×5 + 12×6). Die Ersparnis beträgt also 28 Bits, was eine Verkleinerung der ursprünglichen Nachricht um 22 % bedeutet. Wäre der Text länger, würde das Wörterbuch längere Einträge haben, die wiederholenden Wörter könnten also sehr kompakt gesendet werden.

Dekodieren

Um eine komprimierte Nachricht wieder rekonstruieren zu können, muss das Anfangswörterbuch bekannt sein. Die zusätzlichen Einträge können beim Lesen der komprimierten Nachricht nach und nach wiederhergestellt werden.

Bits:	Ausgabe:	Neuer Eintrag (Ganz):	Neuer Eintrag (Teil):
10100 = 20	T		28: T?
01111 = 15	O	28: TO	29: O?
00010 = 2	B	29: OB	30: B?
00101 = 5	E	30: BE	31: E?
01111 = 15	O	31: EO	32: O? ← ab hier 6 Bits lesen
010010 = 18	R	32: OR	33: R?
001110 = 14	N	33: RN	34: N?
001111 = 15	O	34: NO	35: O?
010100 = 20	T	35: OT	36: T?
011100 = 28	TO	36: TT (nur das erste Element des nächsten Wörterbucheintrags hinzufügen)	37: TO?
011110 = 30	BE	37: TOB	38: BE?
100000 = 32	OR	38: BEO	39: OR?
100101 = 37	TOB	39: ORT	40: TOB?
011111 = 31	EO	40: TOBE	41: EO?
100001 = 33	RN	41: EOR	42: RN?
100011 = 35	OT	42: RNO	43: OT?
000000 = 0	#

Probleme kann es geben, wenn der neu erstellte Wörterbucheintrag sofort verwendet wird. Im obigen Beispiel erreicht der Decoder das erste Zeichen, ein „T“, er weiß, dass das Zeichen 28 mit einem „T“ beginnt, aber womit endet es? Das Problem wird unten dargestellt. Wir dekodieren den Teil einer Nachricht, die wie folgt lautet:

• ABABA

Bits:	Ausgabe:	Neuer Eintrag (Ganz):	Neuer Eintrag (Teil):
…
011101 = 29	AB	46: (word)	47: AB?
101111 = 47	AB? ← Was machen wir hier?

Beim ersten Betrachten scheint es, als ob der Decoder das unmöglich dekodieren könnte. Wir wissen, dass der Eintrag 47 ABA sein soll, aber wie kann das der Decoder wissen? Der kritische Schritt besteht darin, dass 47 aus 29 plus dem, was danach kommt, besteht. 47 endet deshalb mit „was immer danach kommt“. Aber da es sofort gesendet wurde, muss es auch mit „was immer danach kommt“ beginnen und muss deshalb mit dem gleichen Zeichen aufhören, mit dem es anfängt, nämlich A. Dieser Trick erlaubt es dem Decoder festzustellen, dass 47 „ABA“ sein muss.

Allgemein ausgedrückt, tritt diese Situation immer auf, wenn der Encoder Eingabe der Form „cScSc“ liest, wobei „c“ für ein einzelnes Zeichen und „S“ für eine Kette von Zeichen steht und „cS“ bereits im Wörterbuch steht. Der Encoder gibt das Zeichen für „cS“ aus und fügt das neue Zeichen „cSc“ dem Wörterbuch hinzu. Danach erkennt er „cSc“ in der Eingabe und sendet ein Zeichen, das gerade dem Wörterbuch hinzugefügt wurde.