Algorithmen zur Datenreduktion, Teil 2

Weniger ist mehr: Komprimierte Dateien und Programme schaffen Platz auf der Festplatte. Zu Risiken und Nebenwirkungen der Lempel-Ziv-Daten-Kompressoren starten Sie unser Programm oder lesen Sie diesen Artikel.

Wie die Informatik selbst, ist auch der bekannteste Komprimieralgorithmus noch recht jung. So stellten Lempel und Ziv 1977 eine Methode vor, die sich mit der Reduzierung sich wiederholender Zeichenketten (»Phrasen«) beschäftigt. Doch erst 1984 wurde ihre Theorie von Welch praktisch umgesetzt [1]. Während sich der Huffman-Code die Häufigkeitsverteilung einzelner Zeichen zunutze macht, beschäftigen sich die »LZW«-Kompressoren (Lempel-Ziv-Welch) mit dem Aufspüren von sich wiederholenden Zeichenfolgen. Diese Zeichenketten speichern sie in einem Wörterbuch ab und übergeben nur noch die Eintragsnummer im Wörterbuch dem komprimierten Datenstrom.

Zu Beginn enthält der LZW-Duden lediglich die erlaubten Buchstaben. Im Falle einer beliebigen Datei entsprechen die erlaubten Buchstaben den 256 ASCII-Zeichen. Die schwierigste Aufgabe besteht darin, das Wörterbuch sinnvoll zu füllen und nebenbei darauf zu achten, daß das Wörterbuch des Kodierers mit dem des Dekodierers identisch bleibt.

Der Einfachheit halber besteht unser Alphabet nur aus den vier Buchstaben »a«, »b«, »c« und »d«, womit also die ersten vier Wörterbucheinträge schon feststehen. Der Kodierer sucht nun im Wörterbuch das längste Wort, das mit dem Eingabestrom übereinstimmt, und übergibt die Nummer dieses Wortes. Danach fügt er ein neues Wort, das aus den beiden zuletzt ausgegebenen Wörtern besteht, dem Wörterbuch hinzu. Als Beispiel sei »abdcabcababca« zu komprimieren (siehe Tabelle 1).

Es läßt sich erahnen, welche Ausmaße das Wörterbuch bei einer entsprechend großen Datei erreicht. Kodierer und Dekodierer sollten also eine maximale Wörterbuchgröße vereinbaren. Ausschlaggebend für ein solches Limit ist lediglich der zur Verfügung stehende Speicher und die Rechenleistung des Computers. Um hier einen Anhaltspunkt zu geben, sei gesagt, daß die bekannten Packer wie »ZOO«, »PKzip« oder »LHarc«, in den letzten Jahren von einem Wörterbuch mit ursprünglich 4096 Einträgen zu einem mit 16384 Einträgen angelangt sind. Bei der steigenden Bedeutung von Packern und dem dadurch entstehenden Konkurrenzkampf untereinander, ist mit diesem Wert vermutlich noch nicht das Maximum erreicht.

Ist das Wörterbuch voll, benötigt man eine weitere Vorschrift, die Wörter aus dem Lexikon entfernt, um Platz für neue zu schaffen. Naheliegend ist die Entfernung der ältesten Wörter. Allerdings könnte man auch mitprotokollieren, welche der erzeugten Wörter schon für die Ausgabe gebraucht wurden. Diesen Wörtern räumen wir eine höhere Priorität ein und entfernen sie zu einem späteren Zeitpunkt.

Der leichteren Verwaltung wegen bestimmt man darüberhinaus eine maximal erlaubte Wortlänge. Dazu wieder ein Wert aus der Praxis. Bei Binär-Dateien (Objekt-Dateien, Programme, ...) liegt die durchschnittliche Wortlänge bei oben angesprochener Wörterbuchgröße zwischen drei und vier Zeichen. Bei ASCII-Texten ist exakter zu differenzieren. So liegen die durchschnittlichen Wortlängen, etwa bei Programmbeschreibungen oder bei diesem Artikel, bei etwa fünf Zeichen. Stark redundante Texte wie C-Quelldateien erreichen Durchschnittswerte bis zu sieben Zeichen. Noch dramatischer sieht die Sache bei unkomprimierten Bilddateien aus. Hier ist nahezu jede Wortlänge denkbar Da inzwischen alle besseren Bildverarbeitungsprogramme die Bilddaten in komprimierter Form speichern, ist die Berücksichtigung der unkomprimierten Bilddateien bei Packern und Archivierungsprogrammen irrelevant, zumal speziell für Bilder entwickelte Komprimierverfahren besser arbeiten als Allround-Packer.

Folglich liefern Wortlängen von mehr als 32 Zeichen in der Praxis keine nennenswerten Komprimiersteigerungen, dennoch erlauben die Profi-Packer Wortlängen von bis zu 512 Zeichen. Hier darf man wohl zu Recht vermuten, daß dies einzig und allein aus einem Grund geschieht; die Aufbesserung der theoretisch erreichbaren Komprimierrate. Kommt ein Tester bei einem Vergleichstest verschiedener Packer auf die Idee, eine 10-KByte-Datei - bestehend aus gleichen Zeichen - zu packen, könnte man schnell mit vielfach schlechteren Komprimierraten in Verruf geraten. Denn in solchen Dateien verdoppelt sich die Komprimierrate mit jeder Verdoppelung der maximalen Wortlänge. Zurück zur Methode der Wörterbuchergänzungen. Lempel-Ziv addierten ursprünglich nach jedem Schritt nur die zwei aufeinanderfolgenden Zeichen zu einem neuen Wort. Miller und Wegmann erhielten dann 1984 deutlich bessere Komprimierraten mit dem oben abgebildeten Verfahren (MW-Adapting), also dem Zusammenfügen der jeweils letzten zwei ausgegebenen Worte.

Analysiert man das Verfahren genauer, stellt man fest, daß die Methode keine bereits existierenden Wörter erzeugt, was bei einer Implementierung von Vorteil ist. Nebenbei besteht berechtigte Hoffnung, daß das neu erzeugte Wort in absehbarer Zeit im Eingabestrom auftaucht. Bedenkt man allerdings, daß bei einer durchschnittlichen Wortlänge von drei bis sieben Zeichen zwischen 12 KByte und 112 KByte Zeichen zu bearbeiten sind, ehe das Wörterbuch gefüllt ist, wäre ein schneller adaptiver Algorithmus sicher besser. Denn nur mit einem vollen Wörterbuch arbeitet der Komprimierer optimal. Was liegt also näher als das Wörterbuch zumindest in der Anfangsphase schneller zu füllen. Storer entwickelte 1988 dazu das AP-Adapting-Verfahren (»All Prefixes«, siehe Tabelle 2). Trotz gleicher Eingabe haben wir also 16 Wörter gegenüber 12 beim MW-Adapting im Lexikon, was sich auch schon in der Komprimierrate niederschlägt (7 zu 9 Wörter). Bei einer Implementation der AP-Adaption, ist bei jeder neuen Wortschöpfung zu prüfen, ob diese sich nicht schon im Wörterbuch befindet, denn anders als beim MW-Adapting können durchaus gleiche Wörter auftreten. Eine Überprüfung auf bereits vorhandene Wörter ist also unausweichlich.

Strickt man den Gedanken der schnellstmöglichen Adaption zu Ende, kommt man zum derzeit populärsten Verfahren: dem LZFG-Algorithmus (»Lempel-Ziv-Fiala-Greene«; siehe [2]). Der Gedanke, sämtliche Wortkombinationen der bisher eingelesenen Zeichen ins Wörterbuch aufzunehmen, ist zwar nicht neu, doch haben Fiala-Greene 1989 eine bemerkenswert einfache Implementation entwickelt, die bei den derzeitigen Wörterbuchgrößen nicht nur am schnellsten arbeitet, sondern auch die besten Komprimierraten liefert.

Ihr Algorithmus zieht ein Textfenster fester Größe (etwa 4096 Zeichen) den zuletzt eingelesenen Zeichen hinterher. In diesem Textfenster sucht man nun die längste Zeichenkette, die mit dem zu komprimierenden Eingabestrom übereinstimmt. Dann übergibt man die String-Position innerhalb des Textfensters und dessen Länge. Die Position des Strings zählt man vom zuletzt aufgenommenen Zeichen abwärts. Im Textfenster nicht vorhandene Zeichen übergibt man gesondert gekennzeichnet als Literals. Tabelle 3 zeigt ein Beispiel mit einem Textfenster der Größe 5. Die im Textfenster gefundenen Zeichenketten der Länge eins übergibt man, des kürzeren Codes wegen, ebenfalls als Literal.

Alle bekannten Packer arbeiten nach diesem Verfahren, weshalb wir an dieser Stelle auch genauer auf die verschiedenen Implementationen eingehen wollen. Vorher aber ein paar Punkte, die derzeit »noch« unbestritten sind:

Das Textfenster wird in einem Array gehalten und nach jeder Code-Ausgabe aktualisiert. Allerdings würde ein komplettes »shiften« des Textfensters mit »mem_move()« nach jeder Wortausgabe zuviel Zeit in Anspruch nehmen. Das Gleiche läßt sich schneller durch die Organisation des Textfensters in einem Ringpuffer mit dazugehörendem Positionszähler erreichen. Eine Funktion, die dann eine neue Zeichenkette in das Textfenster aufnimmt, könnte etwa so aussehen:

char TextFenster[FensterGroesse];
int TextPosition=0;
InsertString (char *str, int len)
{
	int i;
	for ( i = 0; i < len; i++ )
	{
		TextFenster[TextPosition] = *str++;
		TextPosition = (TextPosition+1) % FensterGroesse;
	}
}

Ein Verschieben des Textes entfällt gänzlich. Um die Stringsuche zu vereinfachen, wählt man eine Textfenstergröße, die um die maximal erlaubte Wortlänge größer ist. In diesem Bereich hält man dann eine Kopie der ersten Zeichen (von Position Null bis zur maximalen Wortlänge) im Feld. Dadurch muß man bei einem String, der am Ende des Feldes beginnt, nicht auf ein Überschreiten des Feldes achten, man braucht bei einem Ringbuffer nicht »ums Eck« schauen.

Um die Position eines gefundenen Strings in einen Abstand zur aktuellen Textposition zu wandeln, benötigt man noch eine Konvertierfunktion, die die Position innerhalb des Text-Arrays in den Abstand zur aktuellen Position berechnet:

int KonvertPosition (int ArrayPosition)
{
	int Offset;
	Offset = TextPosition - ArrayPosition;
	if (Offset < 0)
		Offset = Offset + FensterGroesse;
	return Offset;
}

Solange Kodierer und Dekodierer einen Ringpuffer verwenden, ließe sich die Array-Position eines gefundenen Strings auch direkt übergeben. Möchte man aber später die Stringpositionen mit einem Huffman-Code (siehe [3]) überarbeiten, sollte sowohl der Abstand zur aktuellen Textposition übergeben werden, wie auch die Suche nach der längsten übereinstimmenden Zeichenkette an der aktuellen Textposition beginnen. Zum einen läßt sich nämlich nicht ausschließen, daß sich mehrere gleiche Zeichenketten im Textfenster befinden. Wir nehmen aber die mit dem geringsten Abstand zur aktuellen Textposition. Und zweitens ist die Wahrscheinlichkeit größer, einen passenden String in den zuletzt eingelesenen Zeichen zu finden. Auf diese Weise treten häufiger kleine Positionsangaben auf, was einer Huffman-Codierung sehr entgegenkommt. Auch hierin besteht noch Einigkeit unter den Packer-Programmierern. Anders sieht die Sache aus, wenn es um das schnellste Verfahren zur Suche nach dem längsten übereinstimmenden String geht. Diese Aufgabe spaltet die Packerschreiber in zwei Lager; den Algorithmen-Fetischisten und den Minimalisten. Dieser Diskurs erhält seine Berechtigung schon allein deshalb, weil ca. 80% der Packzeiten auf das Konto der Stringsuche und den Aufbau hierfür eventuell benötigter Kontrollstrukturen geht.

Ein Konsens läßt sich nur noch beim Beginn der Suche finden. In jedem Fall beginnt man mit einer Hash-Tabelle, die dann auf die eigentlichen Kontrollstrukturen verzweigt. Da Strings erst ab einer Länge von zwei Zeichen interessant sind (andernfalls versendet man Literals), berechnet man aus den ersten beiden Zeichen des zu suchenden Strings einen Hash-Index, dessen Eintrag in der Hash-Tabelle auf die eigentlichen Kontrollstrukturen aller Wörter desselben Hash-Wertes zeigt Eine einfache Hash-Funktion könnte so aussehen:

int HashIndex (char *string)
{
	return (int) (unsigned char) string (0) ((int) (unsigned char) string(1) << 4)
}

In diesem Fall muß die Hash-Tabelle 2(8+4) 2x1 2 = 4096 Einträge umfassen. So reduziert sich die Anzahl der zu durchsuchenden Strings etwa um das 100fache. Trotzdem bleiben die meisten Tabelleneinträge leer. Begnügt man sich erst mit Zeichenketten ab einer Länge von drei und sendet andernfalls Literals, dann lassen sich die einzelnen Listen nochmals erheblich verkleinern, indem man die ersten drei Buchstaben zur Berechnung des Hash-Index einsetzt. Gemäß der Größe zeigt jeder Hash-Eintrag auf etwa 10 Zeichenketten mit gleichem Hash-Index,allerdings ist die Streuung recht groß.Die meisten Hash-Listen enthalten also nur wenige Zeichenketten, während die anderen durchaus mehrere hundert Strings gleichen Hash-Wertes verwalten müssen (siehe Bild 2). Das alleine wäre noch nicht so fatal, leider werden ausgerechnet Strings dieser Hash-Werte am häufigsten gesucht. Lohnt es sich, Strings gleichen Hash-Wertes in einem Binär-Baum zu organisieren oder sind einfach verkettete Listen praktikabler?

»ZOO« und »LHarc« organisieren ihre Zeichenketten in »Tries« (von »reTrieval, eine spezielle Form von Binär-Bäumen), wobei die hierfür nötigen Verwaltungsfunktionen (»Insert()«, »Delete()«, »Find()«) vom gleichen Autor stammen, während »PKzip« den einfach verketteten Listen den Vorrang gibt. Beide Verfahren haben ihre Vor- und Nachteile, doch sprechen die Komprimierzeiten der Packer eine deutliche Sprache:

PKzip ist rund doppelt so schnell wie LHarc und gar dreimal flotter als ZOO. Die ausschlaggebende Ursache für den Tempovorteil der einfach verketteten Listen: Da etwa fünfmal soviele Strings in die Strukturen eingefügt und wieder entfernt werden müssen wie schließlich gesucht werden, sind die Zeiten für das Einfügen und Löschen von Zeichenketten in die Strukturen gewichtiger als die Zeiten der Suchfunktion selbst. Im Falle von einfach verketteten Listen besteht das Löschen aus drei und das Einfügen aus fünf C-Quelltextzeilen, während die entsprechenden Funktionen für Binär-Bäume jeweils eine Bildschirmseite füllen, in denen noch ganze Schleifen abzuarbeiten sind.

Zwar verschiebt sich mit wachsender Wörterbuchgröße die Lage zu Gunsten der Bäume, da jedoch alle Packer auch unter MS-DOS verfügbar sind und zukünftige Versionen wahrscheinlich auch bleiben, diese Rechner mit 64-KByte-Segmenten aber bis an ihre Leistungsgrenze ausgereizt sind, übersteigen die Textfenstergrößen wohl kaum diesen magischen Wert.

Bild 1 zeigt, wie sich einfach verkettete Listen effizient realisieren lassen. Zu beachten ist, daß die Position der Kontrollstruktur (»Last«, »Next«) direkt mit der Position des korrespondierenden Strings im Textfenster übereinstimmt. Das Array »Last« ist eigentlich schon Luxus, erspart aber weitere Hash-Index-Berechnungen beim Suchen von Strings. Mit Einführung eines Sentinel (»Wachposten«), der das Ende jeder Kette bildet, erspart man sich weitere Abfragen beim Einfügen neuer Strings.

Auch beim Stringvergleich läßt sich durch einen geschickten Algorithmus viel Zeit einsparen. Das ausschlaggebende Stichwort heißt hier »lazy evaluation«. Hier findet der Vergleich nicht String für String statt, sondern wird anhand von Schwellwerten für brauchbar oder unbrauchbar bewertet. Die brauchbaren überprüft man dann genauer. Zwei Beispiele seien hier genannt: Man überprüft nur eine bestimmte Anzahl von Strings und wählt davon den besten, oder aber man begnügt sich mit dem ersten String, der mehr als zwei Zeichen länger ist, als der bisher beste gefundene String. Ein Nachteil dieser Methoden ist, daß mit geringerem Schwellwert auch die Komprimierraten sinken.

Verknüpft man diese Algorithmen noch mit der naheliegendsten Methode, erzielt man die besten Ergebnisse. So reduzieren sich die Suchzeiten nochmals deutlich, indem vor dem systematischen Stringvergleich eine Plausibilitätsprüfung stattfindet, ob der neue String denn überhaupt länger sein kann als der bisher längste. Stimmt zum Beispiel der bisher beste String in den ersten vier Zeichen überein, überprüft man beim nächsten String erst einmal, ob dieser länger ist. Dazu muß aber auf jeden Fall das fünfte Zeichen übereinstimmen.

Auf der TOS-Diskette befinden sich einige Bibliotheksfunktionen für Turbo/Pure C (inkl. C-Quelltexte) für die drei bekanntesten Komprimieralgorithmen (adaptive Huffman-Codierung, Huffman codierte Lauflängen-Codierung und Huffman codierte LZFG-Codes). Diese Funktionen dienen aber nicht nur, wie es sonst immer so schön heißt, »der Anschauung«, sondern können durchaus mit denen aus den mehrfach angesprochenen Packern mithalten. Der LZFG-(De-)Kodierer arbeitet zum Beispiel deutlich schneller als die Assemblerversion des »LHarc« trotz ähnlich guter Kompimierraten und weitaus geringerem Speicherbedarf. Um nicht erst ein eigenes Programm schreiben zu müssen, ist außerdem noch ein einfacher Datei(ent)packer dabei, der eben diese Bibliotheksfunktionen benutzt. (ah) Literaturhinweise:
[1] Welch, T.A., »A Technique für High-Performance Data Compression«, IEEE Computer Journal, 6/84 S.8
[2] Fiala, E.R., Greene, D.H., Data Compression with Finite Windows, Communications of the ACM, Vol 32, No.4, 4/89, S.490-595
[3] ÜBERSCHRIFT, Teil 1, Jürgen Lietzow, TOS-Magazin, Ausgabe xx/93, Seite xx
[4] Robert Sedgewick, „Algorithms Second Edition, Addison-Wesley
[5] D.A. Huffman, „A method for the construction of minimum-redundancy codes, Proceedings of the IRE, 40, (1952)
[6] Frank Bauernöppel, „Imploding..freezing..done“, Heise c‘t 10/91, S. 278ff
[7] Data Compression Engines, Dr. Dobbs Journal, 2/91, S.16, 32

Zeichen (Eingabe) Ausgabe (Wort) Ausgabe (Nummer) Aufnahme (neues Wort) Aufnahme (neue Nummer)
a a 1
b b 2 a-b 5
c c 4 b-d 6
d d 3 d-c 7
a
b ab 5 c-ab 8
c
a
b cab 8 ab-cab 9
a
b ab 5 cab-ab 10
c c 3 ab-c 11
d a 1 c-a 12

Tabelle 1: Das Wörterbuchverfahren nach Miller

Zeichen (Eingabe) Ausgabe (Wort) Ausgabe (Nummer) Aufnahme (neues Wort) Aufnahme (neue Nummer)
a 1
b b 2 a-b 5
d d 4 b-d 6
c c 3 d-c 7
a
b ab 5 c-a 8
c__ab 9
c
a
b cab 9 ab-c 10
ab-ca 11
ab-cab 12
a
b
c
a abca 11 cab-a 13
cab-ab 14
cab-abc 15
cab-abca 16

Tabelle 2: Schneller füllen mit dem AP-Verfahren nach Storer

Eingabe: Text Ausgabe: Position Länge Literal
a b d c a b c a b a b c a - - a
(a) b d c a b c a b a b c a 1 - - b
(a b) d c a b c a b a b c a 2 1 - - d
(a b d) c a b c a b a b c a 3 2 1 - - c
(a b d c) a b c a b a b c a 4 3 2 1 4 2 -
a (b d c a b) c a b a b c a 5 4 3 2 1 3 3 -
a b d c (a b c a b) a b c a 5 4 3 2 1 5 4 -
a b d c a b c a (b a b c a)

Tabelle 3: Schneller und besser: Das LZFG-Verfahren


Jürgen Lietzow
Aus: TOS 04 / 1993, Seite 62

Links

Copyright-Bestimmungen: siehe Über diese Seite