Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZMW

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

LZMW - Miller, Wegman (1985)

Victor S. Miller und Mark N. Wegman stellten eine Modifikation des LZW-Verfahrens vor. Ihre Arbeit wurde unter dem Titel "Variations on a theme by Ziv and Lempel." im Jahr 1985 vorgestellt und erschien im Springer-Verlag.

Die Veränderungen sind im Grunde genommen keine große Sache. Wenn Sie sich den Algorithmus von Terry A. Welch genauer ansehen, werden sie feststellen, dass es keine klare Handlungsanweisung gibt, was zu tun ist, wenn das Dictionary voll ist. Außerdem adaptiert sich das Verfahren relativ langsam an den Content. Beispielsweise muss ein n Zeichen langes Wort, mindestens n-1 mal codiert werden, damit es mit voller Länge im Wörterbuch auftaucht. Meist sogar häufiger, da die Codierung dieses Wortes nicht immer exakt mit dem Wortanfang selbst zusammenfällt.

Aus diesem Grund wurde ein kombinatorischer Algorithmus implementiert, der das Wörterbuch mit den wahrscheinlichsten Codiervarianten auffüllt. Diese kombinatorische Vorgehensweise hat dieser Algorithmus mit den folgenden beiden Varianten LZY und LZAP gemeinsam.

LZMW Algorithmus

...

Beispiel 1 zum LZW Algorithmus. (Quelle: ThePacker)

Schritt	Index	String	Länge		Ausgabesymbol
1				$\rightarrow$	"I"
2	256	'In'	2	$\rightarrow$	"n"
3	257	'n_'	2	$\rightarrow$	"_"
4	258	'_U'	2	$\rightarrow$	"U"
5	259	'Ul'	2	$\rightarrow$	"l"
6	260	'lm'	2	$\rightarrow$	"m"
7	261	'm,'	2	$\rightarrow$	","
8	262	',_'	2	$\rightarrow$	"_"
9	263	'_u'	2	$\rightarrow$	"u"
10	264	'um'	2	$\rightarrow$	"m"
11	265	'm_U'	3	$\rightarrow$	<258> = ('_U')
12	266	'_Ulm'	4	$\rightarrow$	<260> = ('lm')
13	267	'lm,_'	4	$\rightarrow$	<262> = (',_')
14	268	';_u'	3	$\rightarrow$	"u"
15	269	'un'	2	$\rightarrow$	"n"
16	270	'nd'	2	$\rightarrow$	"d"
17	271	'd_u'	3	$\rightarrow$	<263> = ('_u')
18	272	'_um_U'	5	$\rightarrow$	<265> = ('m_U')
19	273	'm_Ulm'	5	$\rightarrow$	<260> = ('lm')
20	274	'lm_'	3	$\rightarrow$	"_"
21	275	'_h'	2	$\rightarrow$	"h"
22	276	'he'	2	$\rightarrow$	"e"
23	277	'er'	2	$\rightarrow$	"r"
24	278	'rum'	3	$\rightarrow$	<264> = ('um')
25	279	'um.'	3	$\rightarrow$	"."

Erklärungen zum Beispiel 1

...

Wie man am Beispiel sehr deutlich erkennen kann, passt sich dieses Verfahren sehr viel schneller an die Eingabe an, was sich eindeutig in den längeren Zeichenfolgen in den Tabellenindizies widerspiegelt. Die maximale Länge eines Tabelleneintrages hat beim LZW-Algorithmus den Wert 3 für das Beispiel 1. Im LZMW Verfahren beträgt die maximale Länge sogar 5. Für die wenigen zu codierenden Zeichen ergibt sich kein Codiergewinn. Werden aber größere Dateien codiert, so ist die Codiereffizienz dieses Verfahrens deutlich höher.

Aufgaben

Decodierung

Aufgaben