Datenkompression und Dateiformate, erstellt von Johannes Uhlig

erstes Beispiel: abrakadabra

Bitte nicht wundern: Die entstehende Zeichenfolge ist länger als die Ausgangszeichenfolge - dies hängt aber mit dem kurzen Eingabewort zusammen, das Verfahren ist richtig beschrieben! Dieses erste Beispiel soll lediglich die Kodierung und die Dekodierung erklären.
Zuerst muss man ein Wörterbuch erstellen. Dieses ist zu Beginn immer leer, d.h. es gibt ein Element 0, welchem die Eigenschaft "nichts" zugeordnet ist - meist durch ein ε dargestellt:

Index	Wort
0	ε
1	a
2	b
3	r
4	ak
5	ad
6	ab
7	ra

Wie kommt man aber aber auf dieses Wörterbuch? Man beginnt mit dem ersten Buchstaben (hier ein "a") und vergleicht mit dem Wörterbuch ob dieser schon existiert. Da das Wörterbuch aber noch leer ist bekommt der buchstabe einen eigenen Index (in dem Fall den nächsten nach 0, also 1) und wird ins Wörterbuch übernommen. Geht man nun weiter im Eingabedatenstrom erhält man ein "b" und vergleicht dieses mit dem Wörterbuch. Dieses ist in unserem Beispiel noch nicht vorhanden also bekommt es einen Index und wird abgespeichert.Genauso wird mit dem "r" verfahren. Das vierte Zeichen ist (wieder) ein "a" und beim Abgleich mit dem Wörterbuch fällt auf, dass das "a" schon einmal vorhanden war, also nimmt man zu dem "a" den nächsten Buchstaben hinzu ("k") und vergleicht dieses Buchstabenpaar mit dem Wörterbuch. Da die Kombination "ak" in dem Beispiel noch nicht aufgetreten ist bekommt sie einen Index und wird ins Wörterbuch übernommen. So verfährt man nun noch mit dem Rest der Eingabe.

Hat man das Wörterbuch geht es ans Erzeugen des kodierten Datenstroms. Das Ergebnis muss 0a0b0r1k1d1b3a lauten. Wie kommt man aber dahin? Sollten Sie das jetzt beschriebene nicht verstehen, dann versuchen Sie parallel dazu die Dekodierung zu betrachten.
Diese Form des Datenstroms muss sein, da sonst die Dekodierung ohne übertragenes Wörterbuch nicht möglcih wäre. Erzeugung des Ausgabedatenstroms: Beginnen wir einfach vorn: Jede LZW-Kodierung beginnt mit der leeren Menge, also 0. Darauf folgt das erste Zeichen des Eingabewortes, also "a". Danach kommt das nächste Zeichen der Eingabe an die Reihe. Dieses ist ein "b". Da das "b" einen eigenen Eintrag im Wörterbuch hat bekommt es ebenfalls den Präfix 0 (also nicht zusammengesetzt aus mehreren Teilen des Wörterbuchs) und anschließend das "b". Ähnlich das "r", es hat einen eigenen Eintrag im Wörterbuch, also "0r" als nächste Zeichen. Jetzt kommen wir zur Zeichenkette "ak", die auch so im Wörterbuch vermerkt ist. Als Ausgabe wird sie folgendermaßen geschrieben: "1k" - warum? Ganz einfach. Sie ist aus dem Eintrag mit Index 1 (also "a") und "k" zusammengesetzt. Die Zeichenkette "ad" ergibt analog zu "ar" die Ausgabe "1d", "ab" ergibt "1b" und "ra" ergibt "3a" - hier darf das "a" nicht als 1 geschrieben werden, da ein neuer Eintrag gebildet wird, indem an einen bestehenden Eintrag ein Zeichen angehängt wird - dieses muss im Klartext stehn.

Betrachtet man nun das Ergebnis erkennt man, dass man das Gegenteil der Kompression erreicht hat. Dies hängt aber mit der gringen Datenmenge zusammen. Als zweites Beispiel möchte ich abrakadabra abrakadabra dreimal schwarzer kater kodieren, dies allerdings wesentlich kürzer gefasst.

zweites Beispiel: abrakadabra abrakadabra

Da hier nur Buchstaben zu der Eingabe aus Beispiel eins hinzukommen, die schon einmal im Wörterbuch eingetragen wurden dürfte jetzt die Kodierung relativ gut funktionieren. Versuchen wir es einmal:

Der erste Teil des Wörterbuchs (also für das erste abrakadabra) kann einfach übernommen werden, der Rest wird analog wie in Beispiel 1 erstellt. Grundsätzlich verwendet man das Hexadezimalsystem als Schlüssel - den dieser muss standardisiert sein. Ich ersetze der Übersichtlichkeit halber das " " durch "Space".

Index	Wort
0	ε
1	a
2	b
3	r
4	ak
5	ad
6	ab
7	ra
8	Space
9	abr
A	aka
B	d
C	abra

Wenn wir jetzt die kodierte Eingabe generieren ergibt sich 0a0b0r1k1d1b3a0Space6r4a0d9a. Machen wir einen Stellenvergleich:
abrakadabra abrakadabra
0a0b0r1k1d1b3a8 6r4a0d9a

Man kann erkennen, dass wir schon fast Eingabelänge erreicht haben. Deutlich sichtbar ist auch, dass das zweite mal abrakadabra schon wesentlich kürzer kodiert ist als das erste. Sind die Texte wesentlich länger, also zum Beispiel ganze Bücher, so wird man beispielsweise das Wort "und" viel häufiger als zwei- oder dreimal finden. Ein weiteres Beispiel: Die Anzahl von "Herr" in der Bibel ist auch sehr groß.

drittes Beispiel (Negativbeispiel): abrakadabra abrakadabra dreimal schwarzer kater

Längere Texte sind zwar immer gut für den LZW-Algorithmus, allerdings nur wenn nicht so viele unterschiedliche Zeichen enthalten sind. Bei diesem Beispiel erwarte ich einen wesentlich lägeren Kodierten Text als das Original, da fast nur Buchstaben hinzukommen, die noch nicht da waren und somit noch nicht im Wörterbuch augelistet sind. Probieren wir es aus:

Den ersten Teil des Wörterbuches können wir gleich aus Beispiel eins übernehmen. Wir müssen nur eine Änderung vornehmen: der Index muss zweistellig werden, da das Wörterbuch mehr als 10 Einträge bekommt. Den Rest des Wörtberbuches erstelle ich gleich ohne großartige Erklärung.

Index	Wort
00	ε
01	a
02	b
03	r
04	ak
05	ad
06	ab
07	ra
08	Space
09	abr
0A	aka
0B	d
0C	abra
0D	Space-d
0E	re
0F	i
10	Space-m
11	al
12	Space-s
13	c
14	h
15	w
16	ar
17	z
18	e
19	r-Space
1A	k
1B	at
1C	er

Kodiert ergibt das: 00a00b00r01k01d01b03a00Space06r04a00d09a08d03e00i08m01l08s00c00h00w01r00z00e03Space00k01t24r
Selbst hier ist die Eingabecode-Menge noch zu gering.

Dekodierung von LZW-Daten:

Das ganze funktionert relativ einfach, sodass ich das an dem Beispiel zwei erklären möchte (Beispiel eins funktioniert genauso, würde aber halt nach finden von Index 7 enden). Angenommen wir haben nur den Eingabestring (die jetzige Eingabe ist die Ausgabe vom Kodierer) 0a0b0r1k1d1b3a0Space6r4a0d9C und möchte wieder den Klartext, wie gehen wir nun vor?

Am Anfang enthält unser Wörterbuch nur einen Eintrag - Index 0 und Inhalt ist "nichts", also ε

Index	Wort
0	ε

Beginnen wir nun links am Eingabestring, so erkennen wir, dass der neue Eintrag für das Wörterbuch aus "leer" und "a" bestehen soll. Die Schlüssel werden fortlaufend nummeriert. Also sieht unser Wörterbuch dann so aus:

Index	Wort
0	ε
1	a

Der nächste Teil ist "0b" - d.h. der nächste Eintrag besteht aus "nichts" und "b", es ergibt sich das Wörterbuch

Index	Wort
0	ε
1	a
2	b

"0r wird genauso ins Wörterbuch übernommen - also ein neuer Eintrag aus "leer" und "r"

Index	Wort
0	ε
1	a
2	b
3	r

Nun kommt der Eintrag "1k" an die Reihe. Was ergibt der nun? Sicher ist, dass daraus ein neuer Eintrag im Wörterbuch erstellt wird. Logischerweise aus Eintrag "1" und dem Buchstaben "k", also ergibt sich "ak"

Index	Wort
0	ε
1	a
2	b
3	r
4	ak

Genauso verfahren wir mit "1d" und "1b"

Index	Wort
0	ε
1	a
2	b
3	r
4	ak
5	ad
6	ab

Das nächste Zeichen ist "3a" - und ergibt logischerweise einen Eintrag bestehend aus Eintrag 3 und einem a, also "ra". Den Eintrag "0Space" füge ich einfachso ein - hier sollte jedem klar sein wie es funktioniert.

Index	Wort
0	ε
1	a
2	b
3	r
4	ak
5	ad
6	ab
7	ra
8	Space

Als nächstes kommt "6r" an die Reihe - also ein Eintrag bestehend aus "ab" und einem "r", "4a" ergibt einen Eintrag aus "ak" und "a", "0d" ergibt einen Eintrag aus "leer" und "d" und "9d" ergibt einen neuen Eintrag aus "abr" und "a". Die Tabelle sieht dann so aus:

Index	Wort
0	ε
1	a
2	b
3	r
4	ak
5	ad
6	ab
7	ra
8	Space
9	abr
A	aka
B	d
C	abra

Will man nun den Originaltext wiederhaben muss man einfach alle Wörter im Wörtbuch nacheinanderschreiben:
abrakadabraSpaceabrakadabra - ersetzen wir "Space" wieder durch " " so erhalten wir unseren Ausgangstext: abrakadabra abrakadabra

LZW heute?

Der LZW-Algorithmus wird heute noch verwendet, allerdings wurde er immer weiter entwickelt und verbessert. Die bekanntesten Programme die noch heute nach LZW-Algorithmus verschlüsseln liefern ZIP und RAR-Datein.