LZ78-Datenkompression

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. 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 vom Wort 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 zum 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 von 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 Raute („#“) markiert das Ende der Nachricht. Daraus folgt, dass das Wörterbuch zu Beginn 27 Einträge (26 Großbuchstaben + „#“) 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 bei 0 zu zählen angefangen wird.

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:    Neuer Wörterbucheintrag:
           (= Ausgabe)

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 mehr 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:        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       37: TO? <-- für 36, nur das erste Element vom
011110 = 30     BE      37: TOB      38: BE?     nächsten Wörterbucheintrag hinzufügen
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:        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 — 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.… …   Deutsch Wikipedia

  • Datenkompression — oder Datenkomprimierung ist ein Verfahren auf digitaler Ebene, um Speicherplatz einzusparen oder um die Übertragungszeit von Daten zwischen zwei Computern (oder Teilnehmern) zu verkürzen. Die Organisation (Struktur) der Daten wird hierfür… …   Deutsch Wikipedia

  • Verlustbehaftete Datenkompression — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Verlustfreie Datenkompression — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • LZW-Datenkompression — Der LZW oder auch Lempel Ziv Welch Algorithmus ist ein häufig bei Grafikformaten zur Datenkompression, also zur Reduzierung der Datenmenge, eingesetzter Algorithmus. Ein Großteil der Funktionsweise dieses Algorithmus wurde 1978 von Abraham Lempel …   Deutsch Wikipedia

  • Dateiarchivierung — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Dateikompression — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Datenkomprimierung — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Datenreduktion — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Datenreduktionsverfahren — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

Share the article and excerpts

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