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. LZ78 wird als nachfolgendes LZ-Verfahren auch LZ2 genannt.
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#
Das 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 wird die ursprüngliche Länge mit der neuen Länge verglichen.
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.