Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZW

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

LZW - Welch (1984)

In den Jahren 1981 bis 1984 entwickelte Terry A. Welch einige signifikate Verbesserungen für das LZ78 Verfahren, welches Lempel und Ziv im Jahre 1978 und die Welch in der Arbeit "A technique for high-performance data compression" vorstellte. Ihm gelang es, das Folgesymbol, welches im Verfahren von Lempel und Ziv eingebettet war, vollständig zu eliminieren. Damit besteht der zu komprimierende Datenstrom ausschließlich aus Tabellenindexen. Das hat den Nachteil, dass die Symbole selbst immer genauso groß sind, wie der Tabellenindex. Das bedeutet, dass wenn der Tabellenindex 10 Bit umfasst, dass ein uncodiertes Symbol ebenfalls 10 Bit benötigt, obwohl es bspw. ursprünglich 8 Bit waren.

Dieses Verfahren ist durch die Verwendung im GIF87/GIF89 - Format sehr bekannt geworden und sorgte in den Neunziger Jahren des zwanzigsten Jahrhunderts für hitzige Diskussionen, als für das Verfahren Patentgebühren erhoben wurden. In den kommenden zwei Jahren werden die auf dieses Verfahren eingereichten Patente auf der ganzen Welt abgelaufen sein. Dennoch ist das LZ78 Verfahren mit seinen vielfältigen Variationen bis teilweise in die folgende Dekade patentiert und lizenzpflichtig und damit wohl auch für die nächsten Jahre tabu. Einerseits aufgrund der unübersichtlichen Patentlage bezüglich aller Variationen des LZ78-Algorithmus. Teilweise sind die gleichen Techniken zwei verschiedenen Firmen patentiert worden.

Die Grundidee des LZW-Algorithmus lässt sich mit Hilfe einer Tabelle wohl am besten vermitteln. Die Tabelle besteht aus einem Tabellenindex in Form einer Zahl und einer zugeordneten variabel langen Zeichenkette als Inhalt. Sowie einer ausschließlich in der Tabelle vorhandenen Längeninformation, die angibt, wie lang die zugeordnete Zeichenkette ist. Statt also die Längeninformation zu übertragen, kann diese mit Hilfe eines Algorithmus bestimmt werden. Der Codierer verarbeitet die Eingabesymbole einzeln und konkateniert sie zu einer Zeichenkette. Für diese Zeichenkette wird überprüft, ob es bereits einen Eintrag in der Tabelle gibt, die diese Zeichenkette enthält. Ist sie vorhanden, dann wird ausschließlich der Tabellenindex übertragen. Das Ziel ist es, die maximale Übereinstimmung einer Eingabesymbolkette mit dem Wörterbuch zu ermitteln. Logischerweise gibt es irgendwann aber keinen Treffer mehr. An diesem Punkt gibt der Codierer den Tabellenindex in den Ausgabestrom aus und erzeugt einen neuen Wörterbucheintrag, an der nächsten freien Stelle in der Tabelle.

Ein weiterer Vorteil dieses Verfahrens besteht darin, dass es sich an die Daten anpasst, wie auch das LZ78 Verfahren. Das Wörterbuch muss nicht zur Nachrichtensenke übertragen zu werden. Statt dessen wird das Wörterbuch, das zur Codierung verwendet wird, auch während des Decodiervorgangs aus den decodierten Daten erzeugt. Wenn also Codierer und Decodierer das gleiche Wörterbuch benutzen, so sind die codierten Daten korrekt decodierbar.

LZW Algorithmus

Hier der Algorithmus...

Das Kompressionsverfahren wird erneut am Satz "In Ulm, um Ulm, und um Ulm herum." demonstriert. Das Beispiel 1 wird dabei Schritt für Schritt zeigen, wie das Wörterbuch (Dictionary) mit jedem Schritt gefüllt und die codierten Information ausgegeben werden.

Beispiel 1 zum LZW Algorithmus. (Quelle: ThePacker)

Schritt	Index	String	Länge		Ausgabesymbol
Initialisierung	0	0x00	1	$\rightarrow$
Initialisierung	...
Initialisierung	255	0xFF	1	$\rightarrow$
1.	256	In	2	$\rightarrow$	"I"
2.	257	n_	2	$\rightarrow$	"n"
3.	258	_U	2	$\rightarrow$	"_"
4.	259	Ul	2	$\rightarrow$	"U"
5.	260	lm	2	$\rightarrow$	"l"
6.	261	m,	2	$\rightarrow$	"m"
7.	262	,_	2	$\rightarrow$	","
8.	263	_u	2	$\rightarrow$	"_"
9.	264	um	2	$\rightarrow$	"u"
10.	265	m_	2	$\rightarrow$	"m"
11.	266	_Ul	3	$\rightarrow$	<258>
12.	267	lm,	3	$\rightarrow$	<260>
13.	268	,_u	3	$\rightarrow$	<262>
14.	269	un	2	$\rightarrow$	"u"
15.	270	nd	2	$\rightarrow$	"n"
16.	271	d_	2	$\rightarrow$	"d"
17.	272	_um	3	$\rightarrow$	<263>
18.	273	m_U	3	$\rightarrow$	<265>
19.	274	Ulm	3	$\rightarrow$	<259>
20.	275	m_h	3	$\rightarrow$	<265>
21.	276	he	2	$\rightarrow$	"h"
22.	277	er	2	$\rightarrow$	"e"
23.	278	ru	2	$\rightarrow$	"r"
24.	279	um.	3	$\rightarrow$	<264>
25.	280	.<EOI>	2	$\rightarrow$	"."

Erläuterungen zum Beispiel 1

Links können Sie sehen, wie die LZW-Codierung funktioniert. Die blau eingefärbten Felder zeigen Tabellenindizies, die bereits während der Initialisierungsphase vor dem eigentlichen Codiervorgang erzeugt werden. Die gelb eingefärbten Felder, zeigen einen Codierschritt, der zu einem neuen Ausgabesymbol führt. Das Ausgabesymbol innerhalb der Anführungszeichen wird in der Regel durch den, zu dem Zeichen gehörenden, ASCII Wert repräsentiert. Es wird demzufolge eine Zahl ausgegeben. Zur Verdeutlichung dessen, was eine Referenz auf einen Tabellenindex ist, wird die Ausgabe durch eine Zahl dargestellt, die von zwei spitzen Klammern umgeben ist (bspw. <266>). In Wirklichkeit wird eine Zahl ausgegeben (bspw. 266) genauso, wie für das "uncodierte" Symbol eine Zahl zwischen 0 und 255 ausgegeben wird. Für einen Tabellenindex wird eine Zahl gewählt, die größer ist als 255. Man kann eine codierte Zeichenfolge von einem einzelnen Zeichen demnach anhand dieser Zahl unterscheiden. Die Grün markierten Felder im Beispiel stellen die während des Codiervorgangs benutzten Tabellenindizies dar. Sie dienen lediglich der Orientierung. Die beiden magenta-gefärbten Felder zeigen, zwei gleiche Tabellenverweise und sollen veranschaulichen, wie sich das auf die in der Tabelle codierten Zeichenfolgen auswirkt.

Die Schritte 1 bis 10 verlaufen identisch. Es werden keine passenden Treffer im Wörterbuch gefunden. Aus diesem Grund werden die Zeichen uncodiert in den Ausgabestrom ausgegeben und neue Zeichenketten im Wörterbuch abgelegt. Dabei wird das zu codierende Symbol zusammen mit seinem Folgesymbol konkateniert und am ersten freien Platz im Wörterbuch abgelegt. Die Länge der tabellarisch archivierten Zeichenkette beträgt 2. Der erste freie Tabellenplatz befindet sich für das erste zu codierende Symbol ("I") am Tabellenindex 256, wo es zusammen mit dem Folgesymbol ("n") eingetragen wird. Das nächste zu codierende Symbol ist das "n", das mit seinem Folgesymbol (Leerzeichen) zusammen dem Tabellenindex 257 zugeordnet wird. Die Ausgabe im zweiten Schritt ist das noch nicht codierte Symbol "n". Analog zu diesen beiden Schritten, wird bis zum Schritt 10 Verfahren.

Der 11. Schritt hingegen führt zu einem Treffer. Ein Treffer ist ein Tabellenindex, dessen Zeichenkette mit der zu codierenden Zeichenkette übereinstimmt und sich durch einen Tabellenindex darstellen lässt, der größer ist als 255. Es wird außerdem die Zeichenkette gesucht, die die maximale Übereinstimmung liefert. Hierbei handelt es sich um den Tabellenindex 258. Es können in diesem Schritt bereits zwei Zeichen mit Hilfe eines Tabellenindexes codiert werden (258). Der Tabellenindex 266 muss jedoch mit einer weiteren Zeichenkette gefüllt werden. Dazu wird der Inhalt des Tabellenindexes 258 mit dem Folgezeichen (l) konkateniert. Die Gesamtlänge der Zeichenkette die am Tabellenindex 266 abgelegt wird, beträgt 3.

Die Schritte 12 bis 19 verlaufen analog zu den bereits präsentierten Schritten 1-11. Der Schritt 20 stellt insofern etwas besonderes dar, dass hier zu sehen ist, wie eine weitere Variante des Tabellenindexes 265 an die Tabellenposition 275 wird verglichen mit der, die an der Tabellenposition 273 eingetragen wurde. Der Tabellenindex 273 wurde im Schritt 20 nicht ausgegeben, da es sich bei dem Inhalt des Tabellenindex 273 nicht um eine exakte Übereinstimmung mit der zu codierenden Symbolfolge handelt. Sie Stimmen exakt an den beiden ersten beiden Positionen überein, jedoch nicht in der dritten. Die einzig exakte und längstmögliche Übereinstimmung befindet sich an der Tabellenposition 265, so wie sie auch in den codierten Datenstrom ausgegeben wird. Alle weiteren Codierungen erfolgen analog. Das Zeichen EOI ist ein Platzhalter und steht für End of Input (Ende der Eingabe). Dieser braucht nicht zwangsläufig mit codiert zu werden. In einigen Implementationen wird dieser mit codiert, bei dem Originalverfahren von Welch wurde dieses Meta-Symbol nicht codiert.

Aufgaben

Decodierung

Aufgaben