Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZ77

zurück

5 Verlustfreie_Verfahren

5.2 Wörterbuchbasierte Verfahren

5.2.1 LZ77 - Lempel, Ziv (1977)

5.2.2 LZ78 - Lempel, Ziv (1978)

5.2.3 LZSS - Storer, Szymanski (1982)

5.2.4 LZW - Welch (1984)

5.2.5 LZPP - Pylak (2003)

5.2.6 LZFG - Fiala, Green

5.2.7 LZRW - Williams (1989-1991)

5.2.8 LZV - Vogt (1994)

5.2.9 LZMW - Miller, Wegman (1985)

5.2.10 LZC - ?

5.2.11 LZT - Tischer (1987)

5.2.12 LZJ - Jakobsson

5.2.13 LZR - Rodeh, Pratt, Even

5.2.14 LZB - Bell

5.2.15 LZH - Herd

5.2.16 LZO - Oberhumer

5.2.17 LZP/LZCB - Bloom (1996)

5.2.18 LZAP - Storer (1988)

5.2.19 LZY - Yabba

5.2.20

LZ77 - Lempel, Ziv 1977

Abraham Lempel und Jacob Ziv stellten 1977 ein einfaches und effizientes Verfahren zur Kompression von mehr oder minder beliebigen Inhalten vor. Das Verfahren wurde in einer Arbeit vorgestellt, die unter diesen beiden Titeln bekannt ist; mal mit, mal ohne das Wort 'sequential': "A Universal Algorithm for [sequential] Data Compression". Die Neuerung des Verfahrens besteht darin, dass nicht mehr einzelne Zeichen mit ihren Auftretenswahrscheinlichkeiten Entropie-codiert, sondern gezielt die Wiederholungen von Zeichenketten ausgenutzt werden.

Der Grundgedanke des Verfahrens besteht darin, einen zuvor gesehenen Datenstrom als Wörterbuch zu verwenden. Dieses verwendete Wörterbuch ist in seiner Größe begrenzt. Damit immer ein aktuelles Wörterbuch vorhanden ist, wird dieses durch einen einfachen Verschiebemechanismus realisiert, weshalb dieses Verfahren oft als "Sliding Window" bezeichnet wird. Das gleitende Fenster besteht aus zwei Teilen, einem Such-Puffer (search buffer) und einem Vorschau-Puffer der die nächsten zu codierenden Zeichen enthält (look-ahead buffer). Üblicherweise enthält der Such-Puffer mehrere tausend Zeichen und der Vorschau-Puffer für die zu codierenden Daten in etwa 100 Zeichen oder auch weniger.

Als Demonstrationsbeispiel für die LZ77 Kompression dient der folgende Zungenbrecher: "In Ulm, um Ulm, und um Ulm herum.".

Diese Tabelle zeigt das gleitende Fenster, in dem sich der zu komprimierende Datenstrom von Rechts hineingeschoben wird. Die vorhandenen Daten werden durch eine Verschiebung nach links aktualisiert. Das rote Feld markiert den Anfang des Vorschaupuffers. (Quelle: ThePacker)

12	11	10	9	8	7	6	5	4	3	2	1	0	1	2	3	4	5	6	7	8	9
leer												I	n		U	l	m	,		u	m
Suchpuffer												Vorschaupuffer

Wie man später erkennen kann, besitzt diese Form der Codierung einige exzellente Eigenschaften. Das LZ77-Verfahren ist besonders gut geeignet, um Wiederholungscodes zu erkennen und zu komprimieren.

Codierung

Die Codierung nach dem LZ77-Verfahren erfolgt nach dem folgenden Algorithmus.

LZ77 - Algorithmus

1. Das erste Zeichen im Vorschau-Puffer (in den Beispielen (1) und (2) rot markiert) wird im Suchpuffer gesucht. Dazu durchsucht (aufsteigender Index im Suchpuffer) man den gesamten Suchpuffer vom jüngsten zum ältesten Eintrag.
2. Findet der Codierer das erste Zeichen im Such-Puffer, versucht er zu überprüfen, ob das Folgezeichen des Vorschau-Puffers mit dem im Suchpuffer übereinstimmt. Wenn das Folgezeichen übereinstimmt, so wird dessen Folgezeichen überprüft, bis eine Länge $k\geq 2$ gefunden wurde. Der Treffer, bestehend aus Offset und Länge, wird gespeichert.
3. Jetzt versucht der Codierer eine Übereinstimmung zu finden, die länger ist als die bereits gefundene, indem er ältere Einträge des Wörterbuches zu der Suche heranzieht. Die Schritte 1 bis 3 werden so lange ausgeführt, bis der gesamte Suchpuffer durchsucht worden ist. Der beste Treffer (die längste Übereinstimmung) wird jeweils gespeichert.
4. Nach der Suche wird das Resultat als 3-Tupel gespeichert, wobei im Allgemeinen nur zwei Fälle eintreten können.
   1. Gibt es einen Treffer mit einer Länge $k\geq 2$, so werden der Offset, die Länge des Treffers und das Folgesymbol (kein Treffer) zu dem folgenden geordneten Paar zusammengefasst (Offset, Länge, Folgesymbol).
   2. Gibt es keinen solchen Treffer, so wird das folgende 3-Tupel ausgegeben (0,0,Symbol). Das auszugebende Symbol ist das erste Symbol aus dem Vorschaupuffer.
5. Die Schritte 1 bis 5 werden so lange ausgeführt, bis das Ende des Eingabestroms erreicht ist.

  while( !end_of_data )
  {
    best.index = 0;
    best.length = 0;
    /*
     * Den Suchpuffer nach der längsten Übereinstimmung durchforsten.
     */
    for(i=1 ; i<length_of(searchpuffer) ; i++)
    {
    }
    /*
     * Ausgabe des besten Treffers
     */
    if( (best.index !=0) && (best.length>=2 ) )
    {
      output_tripel( best.index, best.length, search_buffer[best.length] );
    } 
    else
    {
      output_tripel( 0,0, search_buffer[0] );
    }
  }
  // Quelle:ThePacker
 

Beispiel

Beispiel (1) für eine LZ77-Kompression (Quelle: ThePacker)

12

11

10

9

8

7

6

5

4

3

2

1

0

1

2

3

4

5

6

7

8

9

Ausgabe

(leer)

I

n

_

U

l

m

,

_

u

m

$\Longrightarrow$

(0,0,"I")

(leer)

I

n

_

U

l

m

,

_

u

m

_

$\Longrightarrow$

(0,0,"n")

(leer)

I

n

_

U

l

m

,

_

u

m

_

U

$\Longrightarrow$

(0,0,"_")

(leer)

I

n

_

U

l

m

,

_

u

m

_

U

l

$\Longrightarrow$

(0,0,"U")

(leer)

I

n

_

U

l

m

,

_

u

m

_

U

l

m

$\Longrightarrow$

(0,0,"l")

(leer)

I

n

_

U

l

m

,

_

u

m

_

U

l

m

,

$\Longrightarrow$

(0,0,"m")

(leer)

I

n

_

U

l

m

,

_

u

m

_

U

l

m

,

_

$\Longrightarrow$

(0,0,",")

(leer)

I

n

_

U

l

m

,

_

u

m

_

U

l

m

,

_

u

$\Longrightarrow$

(5,1,"u")

(leer)

I

n

_

U

l

m

,

_

u

m

_

U

l

m

,

_

u

n

d

$\Longrightarrow$

(4,1,"_")

I

n

_

U

l

m

,

_

u

m

_

U

l

m

,

_

u

n

d

_

u

$\Longrightarrow$

(8,6,"n")

,

_

u

m

_

U

l

m

,

_

u

n

d

_

u

m

_

U

l

m

_

h

$\Longrightarrow$

(0,0,"d")

_

u

m

_

U

l

m

,

_

u

n

d

_

u

m

_

U

l

m

_

h

e

$\Longrightarrow$

(12,7,"_")

_

u

n

d

_

u

m

_

U

l

m

_

h

e

r

u

m

.

(leer)

$\Longrightarrow$

(0,0,"h")

u

n

d

_

u

m

_

U

l

m

_

h

e

r

u

m

.

(leer)

$\Longrightarrow$

(0,0,"e")

n

d

_

u

m

_

U

l

m

_

h

e

r

u

m

.

(leer)

$\Longrightarrow$

(0,0,"r")

d

_

u

m

_

U

l

m

_

h

e

r

u

m

.

(leer)

$\Longrightarrow$

(10,2,".")

fertig

Erläuterungen zum Beispiel 1

Das Beispiel links wird zeilenweise von oben nach unten gelesen. Jede Zeile zeigt einen Codierschritt. In der Spalte Ausgabe befindet sich das Dreier-Tupel, das in diesem Schritt durch den Codierer ausgegeben wird. Das rote Feld stellt das erste zu codierende Zeichen aus dem Vorschaupuffer dar. Der Vorschaupuffer wird zu Beginn mit den ersten Buchstaben des zu codierenden Strings aufgefüllt. Da der Suchpuffer zunächst noch leer ist, ist es unmöglich, eine Übereinstimmung zu finden. Deshalb wird das Zeichen I direkt in die Ausgabe geschrieben, zusammen mit der Information, dass kein Treffer gefunden werden konnte (Offset 0 und Trefferlänge 0). Genauso verhält es sich mit den folgenden neun Zeichen "n", "_", "U", "l", "m" und ",".

• muss überarbeitet werden

Der Buchstabe "m" ist bereits im Suchpuffer auf der linken Seite enthalten, dennoch stimmen die auf das "m" im Suchpuffer folgenden Symbole nicht mit dem überein, das im Vorschaupuffer auf den Buchstaben "m" folgt. Aus diesem Grund wurden die Zeichen einzeln codiert.

Das folgende Symbol "_" (Leerzeichen) stellt jedoch einen Treffer dar (im Beispiel grün markiert), der mit dem Inhalt des Vorschaupuffers zu einer bestimmten Länge übereinstimmt. Anschließend folgt ein nicht übereinstimmendes Symbol ein "n" im Vorschaupuffer und ein "m" im Suchpuffer. Das "n" wird als Symbol ausgegeben, zusammen mit der Information, an welcher Stelle der gefundene Treffer zu finden ist (Offset 8) mit der Trefferlänge (7). Diese drei Informationen werden codiert ausgegeben. Wie diese Codierung im einzelnen erfolgt soll im Anschluss an dieses Beispiel erläutert werden.

• bis hier

Codierung des Ausgabestroms

Codierung eines Treffers/Nicht-Treffers

Länge				Offset												Folgezeichen
4	3	2	1	12	11	10	9	8	7	6	5	4	3	2	1	8	7	6	5	4	3	2	1
Byte 1 (8 Bit)								Byte 2 (8 Bit)								Byte 3 (8 Bit)

Für die Codierung der Trefferlänge wurde ein 4 Bit langer Wert reserviert. Damit sind alle Längenangaben zwischen 0 und 15 exakt codierbar. Längere Treffer wurden durch Aneinanderreihung mehrerer Treffer erreicht. Wie Sie sehen, werden Treffer und Nicht-Treffer gleichartig codiert. Sie sind nach der Codierung immer 24 Bits lang. Bei dieser Darstellung jedoch ergibt sich ein riesiges Sparpotential, welches in vielen später entwickelten Varianten ausgenutzt wurde. Für die Offsets wurden 12 Bits zur Verfügung gestellt, womit alle Werte zwischen 0 und 4095 darstellbar sind. Die beiden Werte für Länge und Offset können in einem Block aus 16 Bits zusammengefasst werden, das entspricht 2 Bytes. Das Folgezeichen wurde stets separat dazu ausgegeben und bildete so das dritte Byte. Pro Treffer oder Nicht-Treffer werden exakt 3 Bytes Daten ausgeben. Da der Offset 12 Bit lang ist, kann maximal ein 4 Kilobyte (minus ein Byte) langer Puffer adressiert werden.

Effizienz des Ausgabestroms

• (0,0,"X")

Lassen Sie uns nun die möglichen Codier-Fälle des LZ77-Algorithmus näher beleuchten. Zum einen kann es passieren, dass ein Zeichen noch nicht Teil des Suchpuffers ist (0,0,"X"), dann wird ein 24 Bit langer Wert ausgegeben, um ein 8 Bit langes Zeichen zu codieren. Dieser Fall ist bezüglich der Codiereffizienz nicht optimal (= Codierverlust). Es werden 3 mal so viele Bits benötigt wie für die ursprünglich Nachricht.

• (Offset,1,"X")

Nehmen wir an, das zu codierende Zeichen befindet sich bereits im Suchpuffer, aber das nachfolgende Zeichen ist noch nicht Teil des Suchpuffers oder es folgt nicht auf das zu codierende Zeichen. Es tritt also der Fall (Offset,1,"X") auf, so können zwei Zeichen codiert werden. Das erste Zeichen wird durch die Offset und Längenangabe codiert. Das Folgezeichen steht an der Stelle des Literals. Es können also 2*8 Bit (16 Bit) mit einem 24 Bit Wert dargestellt werden. Auch dieser Fall ist bezüglich der Codiereffizienz nicht hilfreich, da für jedes zu codierende statt 8 Bit im Mittel 12 Bit benötigt werden. Dieser Fall ist bereits besser (1,5 fach) als gar nicht vorhandene Zeichen (3 fach), dennoch führen sie nicht zu einem Codiergewinn (=Codierverlust). Es werden mehr Informationen zur Darstellung benötigt, als es zu codieren gilt.

• (Offset,2,"X")

Neutral bezüglich der Codiereffizienz gegenüber sind Treffer der Länge 2. Es werden 24 Bit ausgegeben, wenn 3*8 Bit codiert werden sollen. (Offset,2,"X") Bis zu dieser Treffer-Länge sind mit der LZ77-Codierung keinerlei Codiergewinne erzielbar. Die Hoffnung bei der Codierung ist, dass die Codierverluste durch die Codiergewinne der längeren Übereinstimmungen wettgemacht werden können. Weder Codiergewinn noch Codierverlust.

• (Offset,3..15,"X")

Jede Codierung der Form (Offset,3..15,"X") stellt einen Codiergewinn dar, da hiermit Zeichenketten der Länge 4 bis 16 mit durch ein 24 Bit langen Wert dargestellt werden können. Alle diese Zeichenketten sind durch eine Zeichenkette der Länge 3 codierbar.

Wenn die Codiergewinne die Codierverluste kompensieren können, ist die Gesamtausgabe des codierten Datenstroms kürzer als die Eingabe und stellt eine Kompression des Datenstroms dar.

Beispiel

Beispiel (2) für eine LZ77-Kompression (RLE-Modus) (Quelle: ThePacker)

5

4

3

2

1

0

1

2

3

4

5

Ausgabe

(leer)

a

a

a

a

b

$\Longrightarrow$

(0,0,a)

(leer)

a

a

a

a

b

$\Longrightarrow$

(1,3,b)

Das zweite Beispiel zeigt einen ganz speziellen Sonderfall bei der Codierung nach dem LZ77-Verfahren. In diesem Fall ist sowohl der Vorschaupuffer als auch der Suchpuffer Teil des Treffers. Das erfordert für den Fall "Offset < Länge" lediglich eine modifizierte Entpackoperation, die in diesem Fall Symbol-weise entpacken muss. Beachtet man dies nicht, so kann es zu Fehlern im decodierten Datenstrom kommen. Wie man links sehen kann, sind mit diesem Algorithmus identische aufeinanderfolgende Zeichen codierbar. Dieses Verfahren ist auch als Lauflängen-Codierung/Kompression (RLE - Run Length Encoding) bekannt.

Beispiel

Beispiel (3) für eine LZ77-Kompression (Wiederhol-Modus)

10

9

8

7

6

5

4

3

2

1

0

1

2

3

4

5

6

7

8

9

10

Ausgabe

(leer)

a

b

c

a

b

c

a

b

c

a

d

$\Longrightarrow$

(0,0,a)

(leer)

a

b

c

a

b

c

a

b

c

a

d

$\Longrightarrow$

(0,0,b)

(leer)

a

b

c

a

b

c

a

b

c

a

d

$\Longrightarrow$

(0,0,c)

(leer)

a

b

c

a

b

c

a

b

c

a

d

$\Longrightarrow$

(3,7,d)

b

c

a

b

c

a

b

c

a

d

(leer)

$\Longrightarrow$

fertig

Das Beispiel 3 zeigt eine Modifikation des Beispiels 2, bei dem nicht nur ein einfacher RLE-Code präsentiert wird, sondern zeigt einen Wiederholungscode, wobei sich dieser rein programmiertechnisch vom RLE-Modus nicht unterscheidet. Es sollte lediglich eine weitere Ausprägung gezeigt werden, mit der es möglich ist, sich wiederholende Zeichenkombinationen zu packen. Dieses Beispiel soll an der Zeichenkette "abcabcabcad" demonstriert werden. Es wurden 4 Tripel (12 Byte) für 11 Zeichen ausgegeben. Man kann in diesem Fall nicht von einer effizienten Codierung sprechen.

Der gesamte Codiervorgang besteht im Grunde genommen aus zwei Teilen, aus der Codierung und aus einer Anpassung an den zu codierenden Datenstrom. Je weniger Anpassung es gibt, desto schlechter ist die Codiereffizienz. Am Anfang des Codierprozesses ist keine Anpassung an die zu codierenden Daten vorhanden. Diese wird sukzessive vorgenommen. Mit weiterem Fortschritt der Codierung steigt die Wahrscheinlichkeit, einen Treffer zu erzielen, sofern es sich nicht um völlig zufällige Daten handelt.

Aufgaben

Aufgabe(n) - LZ77-Codierung

1. [M10] Welches Vorgehen würden Sie für den Fall empfehlen, dass die besten Treffer alle die gleiche Länge besitzen?
2. [M10] Welche Vor- oder Nachteile hat es, den letzten besten oder den ersten besten Treffer für die Codierung zu verwenden? Welche Folgen hätte die Auswahl des ersten besten Treffers? Kann sowohl das eine oder andere Verhalten ohne größeren Aufwand realisiert werden? (Fazit: Minimierung der Distanz)
3. [M10] Hat die Minimierung der Distanz einen Vorteil in der Codierung mit exakt diesem Verfahren? (Nein - keine variablen Längencodes. Empfehlung ist, dieses Verfahren mit einem VLC zu verbinden.) Welchen Vorteil hat die Minimierung? (Weniger weit entfernte Codes haben auf Grund der Priorisierung eine höhere Auftretenswahrscheinlichkeit.)
4. [M08] Welche Parameter können bei diesem Verfahren variiert werden, um eine höhere Trefferwahrscheinlichkeit zu erzielen? (Länge des Such-Puffers, Länge des Puffers der zu codierenden Informationen)
5. [M20] Welche Parameter können Sie als redundant identifizieren? Können diese Parameter verkürzt dargestellt werden? (Variable Codewortlänge für Offset + Längenfeld). Berechnen Sie die Einsparung, wenn Sie weiterhin eine feste Codewortlänge annehmen! Wie viele Bits kann man auf diese Weise einsparen?
6. [M30] Ist eine Entropie für diese Form der Offsetkodierung wirklich sinnvoll? Welche Probleme erkennen Sie, wenn Sie die gleichen Treffer mehrfach im Text haben, in Verbindung mit einem gleitenden Fenster? (Lösung: Problem ist der gleitende Offset - daraus folgt eine ungewollte Streuung der Treffer)
7. [M15] Ist es sinnvoll, eine Entropiecodierung der uncodierten Zeichen vorzunehmen? (Ja, denn die Entropiecodierung bringt einen Gewinn, wenn unterschiedliche Wahrscheinlichkeiten für die Zeichen gelten.)
8. [M10] Welche (asymptotische) maximale Kompressionsrate kann durch diesen Algorithmus erzielt werden? (5:1 - aber warum?)
9. [A20] Untersuchen Sie die Redundanz des Suchpuffers, was stellen Sie fest? (Redundanz des Textes identisch mit Redundanz des Suchpuffers). Was ist das Problem, wenn der Suchpuffer redundante Inhalte enthält. (Er wird nicht optimal genutzt) Überlegen Sie, wie dieses Phänomen reduziert werden kann.

Decodierung

Die Decodierung erfolgt in ähnlicher Weise. Dazu wird das oben besprochene Tripel ausgelesen, verarbeitet und interpretiert. Anschließend wird anhand der Trefferlänge ermittelt, ob der Codierer eine Übereinstimmung erzielt hat. Wenn der Codierer keine Übereinstimmung gefunden hat, so wird das Folgezeichen an die Ausgabe weitergeleitet. Sollte es sich um eine Übereinstimmung handeln, so wird zuerst die Zeichenfolge der gefundenen Übereinstimmung ausgegeben und anschließend das Folgezeichen. Die auszugebenden Zeichen der Übereinstimmung lassen sich aus der Information über die aktuelle Position des Dateiendes und dem Offset ermitteln, welcher von dieser Position abgezogen wird. Durch diese Rechnung erhält man eine Dateiposition, an der sich das gesuchte Zeichen befindet. Gibt es eine Trefferlänge größer als 1, so wird das Auslesen des Zeichens entsprechend oft wiederholt.

Mit jedem ausgegebenen Zeichen verändert sich die aktuelle Position des Dateiendes um ein Zeichen, aus diesem Grund wird der Offset statisch von der Position subtrahiert. Dazu können Sie den folgenden Pseudo-Code betrachten.

output_pointer = 0;
while(!end of data)
{
  (length, offset, followchar)=inputstream.leseTripel();

  if(length>0)
  {
    for(i=0;i<length;i++)
    {
      dateiposition=outputstream.Aktuelle_Position_Dateiende - offset;
      zeichen=outputstream.leseZeichen(dateiposition);
      outputstream.schreibe(zeichen);
    }
  }

  outputstream.schreibe(followchar);
}

Aufgaben

Aufgabe(n) - LZ77-Decodierung

1. Beurteilen Sie die Komplexität des Coders und des Decoders.
2. Was zeichnet den Codierer und Decodierer besonders aus ? (Single-Pass Encoding / schnelle Decodierung möglich / konstanter Speicherplatzbedarf)

Codierergebnisse mit dem Calgary Corpus

	Calgary Corpus - Resultate
	LZ77 2 Kbyte Puffer 5 Bit Längeninfo	LZ77 4 Kbyte Puffer 4 Bit Längeninfo	LZ77 8 Kbyte Puffer 3 Bit Längeninfo
bib
book1
book2
geo
news
obj1
obj2
paper1
paper2
progc
progl
progp
trans
Mittel

Hier finden Sie die Information, mit welchen objektiven Kompressionsleistungen dieser Algorithmus aufwarten kann, sowie die Interpretation der rechts angeführten Resultate.

Bewertung

Der LZ77-Algorithmus spiegelt alles in allem die Codiertechniken der späten 70er Jahre des 20. Jahrhunderts wieder. Er hat den Vorteil, dass viele Erweiterungen und Varianten nicht mit Patenten belegt sind oder diese in den nächsten Jahren ablaufen werden. Dieser Algorithmus ist jedoch sehr populär und dient heute nahezu immer als einer der Algorithmen, mit denen man beginnt, einen neuen Codierer und Decodierer zu entwerfen. Er stellt eine sehr gute erste Übung dar und lässt sehr viel Spielraum für Erweiterung. Die objektiven Ergebnisse, wie sie am Calgary Corpus erzielt werden, sind quasi die am leichtesten erzielbaren Ergebnisse. Ein Algorithmus, der schlechtere Resultate liefert als dieser Algorithmus, sollte nicht als Ausgangsmaterial dienen.

• Der Algorithmus ist einfach erlern- und programmierbar.
• Der Algorithmus ist einfach zu erweitern.
• Der Algorithmus ist einfach zu verbessern (viel Spielraum)
• Mit Variationen dieses Verfahrens lassen sich Ergebnisse erzielen, die komplexen Codierern (bspw. PPM) ebenbürtig sind.

In seiner Reinstform kann dieser Algorithmus jedoch mit keinem neueren Algorithmus konkurrieren. Wie gesagt, handelt es sich um einen Algorithmus der fast 30 Jahre alt ist. Aber er ist wiederum die Quelle aller wörterbuchbasierten Codiertechniken.

Citeseer-Link auf den Artikel

1. http://citeseer.ist.psu.edu/ziv77universal.html