LZ78

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.


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • LZ78 — LZ77 et LZ78 LZ77 et LZ78 sont deux algorithmes de compression sans perte de données publiés par Abraham Lempel et Jacob Ziv en 1977 et 1978. Ces deux algorithmes forment la base de la plupart des algorithmes LZ comme LZW et LZSS. LZ77 présente… …   Wikipédia en Français

  • LZ78-Datenkompression — LZ78 ist ein von Jacob Ziv und Abraham Lempel entwickeltes Verfahren zur Datenkompression. LZ78 ist der Nachfolger vom ein Jahr zuvor erschienen Algorithmus LZ77. Während der LZ77 Algorithmus mit alten Daten arbeitet, zielt LZ78 auf neue Daten ab …   Deutsch Wikipedia

  • LZ78 — …   Википедия

  • LZ78 — ● np. m. ►PACK algorithme de compression basé sur l utilisation d un dictionnaire. Lorsqu une phrase du dictionnaire est rencontrée, on la remplace dans le fichier compressé par son index dans le dictionnaire. LZW en est une variante …   Dictionnaire d'informatique francophone

  • LZ77 and LZ78 — are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. They are also known as LZ1 and LZ2 respectively [http://www.patentstorm.us/patents/5532693 description.html] .… …   Wikipedia

  • LZ77 et LZ78 — sont deux algorithmes de compression de données sans perte proposés par Abraham Lempel et Jacob Ziv en 1977 et 1978 (d où leurs noms). Ces deux algorithmes posent les bases de la plupart des algorithmes de compression par dictionnaire, à tel… …   Wikipédia en Français

  • LZ77 Et LZ78 — sont deux algorithmes de compression sans perte de données publiés par Abraham Lempel et Jacob Ziv en 1977 et 1978. Ces deux algorithmes forment la base de la plupart des algorithmes LZ comme LZW et LZSS. LZ77 présente certains défauts, en… …   Wikipédia en Français

  • LZ787 et LZ78 — LZ77 et LZ78 LZ77 et LZ78 sont deux algorithmes de compression sans perte de données publiés par Abraham Lempel et Jacob Ziv en 1977 et 1978. Ces deux algorithmes forment la base de la plupart des algorithmes LZ comme LZW et LZSS. LZ77 présente… …   Wikipédia en Français

  • Lz77 et lz78 — sont deux algorithmes de compression sans perte de données publiés par Abraham Lempel et Jacob Ziv en 1977 et 1978. Ces deux algorithmes forment la base de la plupart des algorithmes LZ comme LZW et LZSS. LZ77 présente certains défauts, en… …   Wikipédia en Français

  • LZ77 — и LZ78  алгоритмы сжатия без потерь, опубликованные в статьях Абрахама Лемпеля (англ.) и Якоба Зива (англ.) в 1977 и 1978 годах. Эти алгоритмы наиболее известные варианты в семействе LZ*, которое включает в себя также LZW, LZSS,… …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”