Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZSS

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

LZSS - Storer, Szymanski (1982)

Die beiden Forscher James A. Storer und Thomas G. Szymanski stellten im Jahr 1982 einige erhebliche Verbesserungen für das von Lempel und Ziv im Jahre 1977 vorgestellte LZ77-Verfahren vor. Der Titel der Arbeit ist "Data compression via textual substitution". Die Hauptverbesserung von Storer und Szymanski beschränkt sich auf die Idee, das gleitende Fenster durch einen Zirkularpuffer zu ersetzen. Dieser hat Vorteile, die sich auf die Codiergeschwindigkeit positiv auswirken. Als zweite Verbesserung hat man die Redundanz der Ausgabe dadurch verringert, dass Treffer und Nicht-Treffer gesondert behandelt werden. Die Unterscheidung, ob eine Übereinstimmung vorliegt oder nicht, wurde durch das Voranstellen eines einzelnen Bits erreicht:

1. Das Tripel ("0"(12 Bit),"0"(4 Bit),"W" (8 Bit)) wurde durch ein Tupel ("0" (1 Bit),"W" (8 Bit)) ersetzt. Das führt zu einer Einsparung von 15 Bit für einen Nicht-Treffer (bzgl. LZ77).
2. Ein Wiederholungscode wurde durch ein Tripel ("1" (1 Bit), Offset(12 Bit), Länge (4 Bit)) ersetzt. Es kommt zu einer Einsparung von 7 Bit. (bzgl. LZ77) Hierbei ist zu berücksichtigen, dass das Folgezeichen nicht mehr Teil der resultierenden Codierung ist, sondern Element des Folgesymbols bzw. der Folgezeichenkette ist. Beachten Sie den Abschnitt zur Codiereffizienz des Ausgabestroms.

Codierung

Die Verwendung eines Zirkularpuffers hat folgende Vorteile: Einerseits haben die gesuchten Daten für eine bestimmte Zeit feste Adressen im Speicher. Diese festen Adressen erlauben es, die zu durchsuchenden Daten zu indizieren, da sie für eine Weile an der gleichen Stelle im Speicher abgelegt sind. Dadurch kann ein Suchbaum angelegt und benutzt werden, der eine gezielte Suche möglich macht. Der Aufwand wird dadurch von O(n) auf etwa O(c log n) reduziert.

Der Suchbaum muss jedoch mit jedem neuen Zeichen im Zirkularpuffer teilweise aktualisiert werden, was einen höheren Verwaltungsaufwand während der Codierung zur Folge hat. Es müssen einige Teile des Baumes entfernt und neue Ergebnisse hinzugefügt werden.

Algorithmus

LZSS Algorithmus

1. Für jede Zeichenkette im Vorschaupuffer
2. Suche in der Baumstruktur den Offset mit der längstmöglichen Trefferlänge, die mit dem Vorschaupuffer übereinstimmt.
3. Nach der Suche wird das Resultat als 2- oder 3-Tupel gespeichert. Welcher Fall vorliegt, ergibt sich aus dem Resultat der Suche.
   1. Gibt es einen Treffer mit einer Länge $k\geq 3$, so wird der Offset und die Länge des Treffers zu dem folgenden geordneten Paar zusammengefasst (1, Offset, Länge).
   2. Gibt es keinen solchen Treffer, so wird das folgende 2-Tupel ausgegeben (0,Symbol). Das auszugebende Symbol ist das erste Symbol aus dem Vorschaupuffer.
4. Die Schritte 1-4 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( 1, best.index, best.length );
    } 
    else
    {
      output_zweitripel( 0, search_buffer[0] );
    }
    update_searchindex();
  }
  // Quelle:ThePacker
 

Auch hier soll das Beispiel des LZ77 Verfahrens verwendet werden, damit ein direkter Vergleich möglich ist. Im folgenden wird der Zungenbrecher "In Ulm, um Ulm, und um Ulm herum." codiert.

Beispiel (1) für eine LZSS 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,"I") 9bit

(leer)

I

n

_

U

l

m

,

_

u

m

_

$\Longrightarrow$

(0,"n") 9bit

(leer)

I

n

_

U

l

m

,

u

m

_

U

$\Longrightarrow$

(0,"_") 9bit

(leer)

I

n

_

U

l

m

,

u

m

_

U

l

$\Longrightarrow$

(0,"U") 9bit

(leer)

I

n

_

U

l

m

,

u

m

_

U

l

m

$\Longrightarrow$

(0,"l") 9bit

(leer)

I

n

_

U

l

m

,

u

m

_

U

l

m

,

$\Longrightarrow$

(0,"m") 9bit

(leer)

I

n

_

U

l

m

,

u

m

_

U

l

m

,

_

$\Longrightarrow$

(0,",") 9bit

(leer)

I

n

_

U

l

m

,

_

u

m

_

U

l

m

,

_

u

$\Longrightarrow$

(0,"_") 9bit

I

n

_

U

l

m

,

_

u

m

_

U

l

m

,

_

u

n

$\Longrightarrow$

(0,"u") 9bit

I

n

_

U

l

m

,

_

u

m

_

U

l

m

,

_

u

n

d

$\Longrightarrow$

(0,"m") 9bit

I

n

_

U

l

m

,

_

u

m

_

U

l

m

,

_

u

n

d

_

$\Longrightarrow$

(1,8,7) 17bit

m

,

_

u

m

_

U

l

m

,

_

u

n

d

_

u

m

_

U

l

m

_

$\Longrightarrow$

(0,"n") 9bit

,

_

u

m

_

U

l

m

,

_

u

n

d

_

u

m

_

U

l

m

_

h

$\Longrightarrow$

(0,"d") 9bit

_

u

m

_

U

l

m

,

u

n

d

_

u

m

_

U

l

m

_

h

e

$\Longrightarrow$

(1,12,7) 17bit

,

_

u

n

d

_

u

m

_

U

l

m

_

h

e

r

u

m

.

(leer)

$\Longrightarrow$

(0,"_") 9bit

_

u

n

d

_

u

m

_

U

l

m

_

h

e

r

u

m

.

(leer)

$\Longrightarrow$

(0,"h") 9bit

u

n

d

_

u

m

_

U

l

m

_

h

e

r

u

m

.

(leer)

$\Longrightarrow$

(0,"e") 9bit

n

d

_

u

m

_

U

l

m

_

h

e

r

u

m

.

(leer)

$\Longrightarrow$

(0,"r") 9bit

d

_

u

m

_

U

l

m

_

h

e

r

u

m

.

(leer)

$\Longrightarrow$

(1,10,2) 17bit

u

m

_

U

l

m

_

h

e

r

u

m

.

(leer)

$\Longrightarrow$

(0,".") 9bit

204 bit

Erläuterung zum Beispiel

Links sehen Sie ein Beispiel zu Kompression nach dem LZSS-Algorithmus. Die ersten 10 Schritte sind alle identisch und sollen deswegen gemeinsam besprochen werden. Man beginnt mit einem leeren Suchbereich und einem vollen Vorschaupuffer. Das erste zu codierende Zeichen ist das I - dieses ist leider nicht im Suchpuffer enthalten. Die Trefferlänge beträgt also 0; somit wird ein Einzelzeichen (Literal) codiert. Vor dem Literal wird zusätzlich eine Information ausgegeben, dass es sich um ein Literal handelt (Match-Flag ist 0). Außerdem werden alle Treffer in diesem Beispiel mit einer Trefferlänge von kleiner als 2 als nicht Treffer behandelt, sondern einzeln codiert (anders als beim LZ77-Verfahren, wo es bereits sinnvoll ist ab einer Übereinstimmungslänge von 1 zu codieren).

Im 11. Schritt kann man einen grün markierten String sehen, der mit dem Vorschaupuffer 7 Zeichen lang übereinstimmt. Dieser befindet sich an Position 8 und wird nun als Tripel codiert. Die Information, dass ein Treffer Erzielt wurde (Match-Flag ist 1), die Position und die Trefferlänge.

Auch die beiden folgenden Schritte haben eine Trefferlänge von weniger als 2 und werden erneut einzeln codiert. Ansonsten werden alle weiteren Schritte wie Schritt 12 oder Schritt 11 behandelt. In Schritt 14 und 19 werden erneut zwei Treffer erzielt, der eine hat die Länge 7 und der andere die Länge 2. Alle anderen Schritte werden wie Schritt 1 bis 10 behandelt.

Sehen Sie sich den Abschnitt zur Codierung des Ausgabestroms genauer an, um zu überprüfen, welche Trefferlängen sinnvoll sind und welche als Literale codiert werden sollten. Für das Beispiel links wurde eine Mindest-Trefferlänge von 2 angesetzt. Prinzipiell können auch größere Mindest-Trefferlängen definiert werden.

Codierung des Ausgabestroms

Codierung des Literals

9	8	7	6	5	4	3	2	1
0	Literal

Der Ausgabestrom wird durch zwei verschiedene n-Tupel dargestellt. Damit der Decodierer sie unterscheiden kann, gibt der Codierer mit dem ersten Bit (links: das Bit 9) aus, ob es sich um einen Treffer (Match) handelt oder nicht. Ist die Markierung 0, so wurde kein Treffer erzielt. Ist das Flag 1, so wurde ein Treffer erzielt. Bei der Ausgabe eines Literals wurde kein Treffer erzielt, was durch die 0 signalisiert wird. Die folgenden 8 Bit codieren das uncodierte Literal.

Codierung des Treffers

17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1
1	Offset												Länge

Links kann man sehen, wie ein Treffer (eine Übereinstimmung) codiert wird. Als erstes wird eine Information in Form eines Bits übertragen, welches anzeigt, dass es sich um eine Übereinstimmung handelt. Diese Funktion übernimmt das Bit 17, es ist auf 1 gesetzt. Anschließend folgen die Informationen über die Trefferlänge und den Offset. Es wird genau wie beim LZ77 Algorithmus verfahren. Auch dort werden diese beiden Informationen in 16 Bits codiert und mit Hilfe von 2 Bytes ausgegeben. Jedoch gibt es hier bereits einen kleinen Unterschied: Während beim LZ77-Verfahren eine Trefferlänge von 0 als Indikator galt, wurde dieser Indikator in das erste Bit verlagert, weswegen sich die Längenangabe um 1 verschiebt. Damit sind Längenangaben von 1 bis 16 möglich. Doch betrachten wir die Längenangabe 1 konkreter, ein Treffer der Länge 1 kann als Literal effizienter codiert werden (mit nur 9 Bits statt 17) Somit ist ein Treffer der Länge 1 reine Platzverschwendung. Erst ab 2 Zeichen Übereinstimmung ist es effizienter, diese mit 17 Bits darzustellen als mit Hilfe zweier Literale (2*9 Bit=18 Bit). Somit sind Trefferlängen ab 2 Zeichen Länge sinnvoll. Damit können Übereinstimmungen der Länge 2 bis 17 Zeichen codiert werden. Der Offset mit 12 Bit Länge ist in der Lage, Positionen von 0 bis 4095 zu codieren

Codiereffizienz des Ausgabestroms

Statistische Überlegung:

Meist werden jedoch Übereinstimmungen der Länge 3 bis 18 Zeichen Länge codiert. Das ergibt sich aus der Statistik. Bei der Codierung von 2 Zeichen Länge kann man ein ganzes Bit einsparen. Verzichtet man auf diesen Vorteil, so können durch einen Treffer der Länge 18 statt 17 insgesamt 8 Bit eingespart werden. Es selbst wenn Treffer der Länge 18 relativ selten sind, so brauchen sie nur etwas häufiger als im Verhältnis (Treffer der Länge 2) 8:1 (Treffer der Länge 18) aufzutauchen. So lange, wie Treffer der Länge 2 nicht 8 mal häufiger vorkommen als Treffer der Länge 18, so lange ist es effizienter, mit der Längenangabe Längen von 3 bis 18 zu codieren.

Aufgaben

Aufgabe(n) - LZSS-Codierung

1. [M10] Überlegen Sie, wie die Datenstruktur (Tokens) besser zusammengefasst werden kann. (Gruppierung der Tokens)
2. [M19] Welche Einträge müssen im Baum aktualisiert werden, wenn ein Treffer mit der Länge von bspw. 7 oder 8 gefunden und codiert wurde?
3. [M21] Ist es bei diesem Verfahren möglich, mit einer Minimaldistanz zu arbeiten? Wie müsste die Modifikation des Codierers aussehen?
4. [M20] Ist es möglich, dieses Verfahren um einen Huffman-Code zu erweitern? Lohnt es sich? (Ist die Annahme richtig, dass gleiche Worte nahe bei einander liegen?)
5. [M25] Entwickeln Sie eine Adaption des LZSS-Algorithmus, um die gefundenen Treffer und den Inhalt der Tabellen so abzulegen, dass Sie in der Lage sind, verschiedene Statistiken anzufertigen. Vergleichen Sie alle Symbolwahrscheinlichkeiten in Abhängigkeit von der aktuellen Codierposition. Was stellen Sie fest? Stellen Sie die Anzahl der Treffer der Treffer-Länge gegenüber. Welche Schlussfolgerungen können sie ziehen ?

Decodierung

Algorithmus

• Pseudocode

Aufgaben:

Resultate mit dem Calgary Corpus

	Calgary Corpus - Resultate
bib
book1
book2
geo
news
obj1
obj2
paper1
paper2
progc
progl
progp
trans
Mittel

Bewertung

Dieser Algorithmus war insofern ein Meilenstein, als dass er das er die Suche im LZ77-Verfahren durch einen Suchbaum ersetzte, der die Suche nach einem Treffer vereinfachte. Selbst größere Suchpuffer waren durch die indizierte Suche kein Problem mehr. Beim LZ77-Algorithmus hat sich durch die Verdoppelung der Größe des Suchpuffers auch die Laufzeit der Kompression mehr als verdoppelt. Dieses Verhalten ist beim LZSS-Verfahren nicht zu beobachten. Dieser Algorithmus ist relativ leicht zu erlernen, und etwa genauso leicht zu verstehen wie das LZ77-Verfahren. Das erschwerende Element besteht darin, dass der Verwaltungsaufwand, der mit diesem Algorithmus in Kauf genommen wird, nicht einfach zu programmieren ist, da stets Zeichen aus dem Zirkularpuffer überschrieben werden und so der Suchbaum aktualisiert werden muss.

Auch dieser Algorithmus ist gut geeignet, um als Lehrmaterial zu dienen, da er genügend Raum für Verbesserungen bietet. Das sind beispielsweise effiziente Suchstrategien (Laufzeitoptimierung), verbesserte Kompression durch Verwendung von Variablen-Längen-Codes (Optimierung des Codiergewinns) und weitere Optimierungsstrategien.

Was aber auch diesem Verfahren fehlt, ist eine effiziente Kontextmodellierung, weswegen es den meisten modernen Verfahren hoffnungslos unterlegen ist. Diese schaffen im Vergleich zum LZSS-Algorithmus eine über 40% bessere Kompressionsleistung.

Der Algorithmus ist ebenfalls schon mehr als 20 Jahre alt. Die mit einem Baum optimierte Suche wurde jedoch patentiert, und das teilweise mehrfach, weswegen auf die dafür erteilten Patente geachtet werden sollte.

Die Decodierung unterscheidet sich nicht wesentlich von der des LZ77-Verfahrens und stellt somit eine relativ leichte Übung dar, diesen an das LZSS-Verfahren anzupassen.