Unterthema: Lauflängen-Kodierung
Unterthema: Huffman-Baum
Unterthema: Squeeze
Unterthema: Lempel-Ziv-Welch-Kompression
Unterthema: LZW mit fester Codelänge von 12 Bit (Crunchen)
Unterthema: LZW, variable Codelänge und Codewiederverwendung
Unterthema: Lempel-Ziv-Storer-Symanski
Unterthema: Arithmetische Kompression
Kompressionsverfahren bestehen aus zwei Teilen: einem Modell und einer Kodierung. Aufgabe des Modells ist es, die Charakteristik der Originaldaten zu erfassen. Das kann sich auf die Häufigkeiten von Bytes beschränken, aber auch das Vorkommen von Bytefolgen sein. Die Kodierung sorgt für die platzsparende Verschlüsselung der Daten. Ein Beispiel dazu: Das Hauptmodell des Squeezing geht nach der Häufigkeitsverteilung unabhängig voneinander betrachteter Bytes vor; als Kodierung dieses Modells kommt das Huffman-Verfahren zum Einsatz.
Bei der Implementierung der Algorithmen helfen Pseudocode-Listings in den entsprechenden Kästen. Der Übersichtlichkeit halber beschränken sich die Angaben auf den Kern des jeweiligen Algorithmus; Vor- und Nachbereitungsroutinen sind nicht enthalten. Der Datentyp Pointer bezeichnet eine Information, die als Zeiger verwendet werden kann; im allgemeinen ist das ein 16-Bit-Wert. Da die Kodierungen oft nicht nur auf Bytes, sondern auf beliebige Zeichenmengen (die Huffman-Kodierung ist für jede abzählbare Menge möglich) anwendbar sind, werden die Daten an den entsprechenden Stellen als Zeichen bezeichnet.
Wenn die Zeichen Bytes aus dem Bereich von 00h-7Fh sind, ist das für die Kodierung des Zählers nutzbar, indem man mehrfach vorkommende Bytes durch den Zähler mit gesetztem siebten Bit gefolgt vom eigentlichen Zähler kodiert. Dieses Verfahren ist besonders für Textdateien geeignet, in denen selten Bytes mit gesetztem siebten Bit vorkommen. Solche Sonderzeichen sind mit vorangestelltem Zähler 81h zu kodieren.
Die Standard-Lauflängenkodierung kodiert mehrfach vorkommende Bytes in drei Bytes: das ursprüngliche Byte, 90h, Zähler. Da der maximale Zählerstand 255 sein kann, müssen größere Vorkommen unterteilt werden. Weiterhin ist für 90h eine besondere Kodierung nötig, da dieses Byte normalerweise bedeutet: `Zähler folgt´. 90h wird daher als 90 00h kodiert.
Zur Festlegung der jeweiligen Bit-Kodierungen sind die Zeichenhäufigkeiten zu ermitteln. Dafür gibt es drei Wege:
Die Ermittlung der Codes aus den Häufigkeiten der Zeichen führt zu einem Baum (siehe Kasten `Huffman-Baum´). Dieser Baum dient zum Kodieren und Dekodieren nach Huffman: Das Kodieren geht vom Zeichen aus zur Wurzel hin und ergibt so den Binärcode, der für das Zeichen stehen soll; die Länge des Codes ist die Länge des zurückgelegten Weges.
Das Dekodieren beginnt an der Wurzel mit dem Einlesen eines Bits. Je nach Inhalt verzweigt man im Baum nach der einen (1b) oder anderen (0b) Seite, liest das nächste Bit und folgt wieder entsprechend der nächsten Verzweigung. Am Ende, gewissermaßen auf einem Blatt des Baumes, steht das gesuchte Zeichen.
Stehen die Häufigkeiten vorher fest (statisch), ist die Kodierung nur dann optimal, wenn die angenommenen Häufigkeiten genau passen. Dafür entfällt das vorherige Ermitteln und das Mitübertragen von Häufigkeitsverteilungen.
Für die dynamische Kodierung müssen erst einmal alle Zeichen gezählt werden, um deren Häufigkeiten zu ermitteln und daraus den geeigneten Baum für die Kodierung aufzubauen. Erst im zweiten Durchgang erfolgt die eigentliche Kodierung. Weiterhin müssen die ermittelten Häufigkeiten oder der daraus erstellte Baum an den Dekodierer mitgegeben werden.
Beginnt man die Kodierung mit einem Startwert für die Häufigkeiten und paßt sie mit jedem verarbeiteten Zeichen an (adaptierend), ist die Kodierung zwar zu Beginn nicht optimal, wird aber im Laufe der Zeit immer besser. Der Vorteil dieser Methode gegenüber der dynamischen ist, daß auch der Dekodierer die Häufigkeiten ermittelt und den Baum selbst aufbauen kann. Folglich brauchen bei dieser Art der Huffman-Kodierung weder die Zeichen vorher gezählt noch der Baum übertragen zu werden.
In einigen Fällen kann die adaptierende Huffman-Kodierung sogar besser als die dynamische sein: Ändert sich nämlich die Charakteristik der Daten, zum Beispiel weil sich Programm- und Textteile abwechseln, so paßt sich der adaptierende Huffman jeweils an die Maschinencode- und Textstruktur an.
Die Dekompression kann entweder den von Squeeze gelieferten Baum einlesen und bei jedem gelesenen Bit den entsprechenden Wert aus dem Baum auswerten (siehe Kasten `Squeeze´) oder, sicherlich schneller, aus dem Baum gleich die ensprechenden Maschinenbefehle aufbauen. Zu jedem Knoten des Baumes wird ein Stück Code erzeugt, der das nächste Bit einliest und entsprechend verzweigt, das heißt zu dem Stück Code springt, welches dem Unterbaum entspricht beziehungsweise das gefundene Zeichen ausgibt. Diese Methode ist sehr schnell, denn der Baum muß nur einmal interpretiert werden.
Das Squeeze-Modell geht ausschließlich anhand von Byte-Häufigkeiten vor. Aber schon Programm-Sources enthalten viele sich häufig wiederholende Zeichenfolgen. Die Idee von Lempel und Ziv war nun, vorkommende Zeichenfolgen mit eigenen Codes zu versehen. Bei auf Lempel-Ziv basierenden Kompressionen ist die Bitlänge der Codes zwar fest oder zumindest vorhersehbar, aber dafür können sich hinter einem solchen Code eine ganze Menge von Zeichen verbergen. Es gibt einige Kompressionsprogramme, die auf Lempel-Ziv aufbauende Algorithmen verwenden.
Das Gedächtnis ist eine Tabelle schon erkannter Zeichenfolgen. Die Originaldaten werden so lange gelesen, wie die Zeichen als Zeichenfolge in der Tabelle enthalten sind; das Lesen wird beim Auftreten einer neuen Zeichenfolge unterbrochen. Diese ist um ein Zeichen länger als eine schon gespeicherte, wird `gelernt´ und das neue Zeichen an die vorhandene Zeichenfolge gehängt. Dann geht es mit dem Lesen weiter, wobei das zuletzt gelesene Zeichen zum Ausgangspunkt der nächsten zu lernenden Zeichenfolge wird. Umgekehrt arbeitet die Dekompression: Sie hängt nach dem Dekodieren eines Codes das erste Zeichen der eben dekodierten Zeichenfolge an die vorhergehende.
Zu Beginn der Kompression und Dekompression enthält die Tabelle den gesamten Zeichenvorrat als Zeichenfolgen der Länge eins. Wenn es nun zum Beispiel die Zeichenfolge `ABCDEFGH´ zu lernen gibt, stehen hernach zusätzlich die Folgen `AB´, `ABC´, `ABCD´ und so weiter in der Tabelle. Die Einträge der Tabelle bestehen aus je einem Pointer namens Pred (kurz für Predecessor = Vorgänger) und einem Zeichen, genannt Suffix (Anhängsel). Im Beispiel enthält der Eintrag für die Zeichenfolge `ABCD´ als Suffix das Zeichen `D´ und als Pred einen Zeiger auf den Eintrag der Zeichenfolge `ABC´. Im folgenden stehen die Einträge der Tabelle als Paare der Form (Pred,Suffix).
Es gibt, abgesehen von Zeigern auf andere Tabelleneinträge, einige besondere Pred-Werte: `NoPred´ kennzeichnet Einträge, die den Anfang einer Zeichenkette bilden (No Pred = Kein Vorgänger). Nach der Initialisierung enthält die Tabelle nur Zeichenfolgen der Länge eins als (NoPred, Zeichen). `ImPred´ sperrt Einträge gegen Mißbrauch (Impossible Pred = Unmöglicher Pred), weil die zugehörigen Codes eine besondere Bedeutung haben. `Free´ schließlich signalisiert, daß der Eintrag in der Tabelle frei ist. Die Vergabe freier Tabellenplätze erfolgt durch Hashing, das heißt durch Rechnen mit (Pred, Suffix), damit die Suche nach einem bestimmten Eintrag schneller geht.
Diese Version des LZW verwendet immer 12-Bit-Tabellen-Zeiger (4k-Tabelle); größere Tabellen benötigen eine entsprechend erhöhte Codelänge. Die Tabelleneinträge erfolgen abhängig vom Inhalt (Pred, Suffix). Die Nummer des Tabelleneintrags besteht aus den mittleren 12 Bit des Quadrats der Summe aus Pred und Suffix. Ist der so errechnete Tabelleneintrag belegt, muß ein Ausweicheintrag herhalten. Der aktuelle Eintrag erhält einen entsprechenden Verweis. Dazu dient ein zusätzliches, Link (Verbindung) genanntes Pointer-Feld je Tabelleneintrag.
Die Suche nach dem Ausweicheintrag geschieht wie folgt: Erst wird der Tabelleneintrag, auf den Link zeigt, untersucht. Gibt es ihn, geht die Suche mit eben diesem weiter. Hat das auch nicht funktioniert, addiert man 101, eine Primzahl, auf die aktuelle Tabellenposition und sucht von dort an vorwärts den nächsten freien Tabelleneintrag; dabei wird nach dem letzten Tabellenplatz mit dem ersten weitergemacht. Ist er gefunden, wird dessen Position in Link eingetragen und der neue anschließend belegt. Im Rahmen der Initialisierung werden die Link-Werte als leer vorbelegt.
Der Grund für die Ermittlung des Tabelleneintrags für (Pred, Suffix): Die Suche nach einem bestimmten (Pred, Suffix) in der Tabelle ist erheblich schneller, als diese sequentiell abzugrasen. Deswegen werden auch die Ausweicheinträge vermerkt; schließlich wird bei der Kompression laufend in der Tabelle gesucht. Die Suche funktioniert damit dergestalt, daß erst aus (Pred,Suffix) der passende Tabelleneintrag errechnet wird; anschließend muß nur noch entlang der Link-Kette nachgesehen werden, um festzustellen, ob der gesuchte Eintrag in der Tabelle steht oder nicht. Ist die Tabelle voll, werden alle weiteren Zeichenfolgen auf Basis der bisherigen Eintragungen kodiert.
Die Suche nach einem bestimmten (Pred, Suffix) funktioniert entsprechend: Es wird der zugehörige Eintrag in Hash errechnet; dort steht die Adresse des in der Tabelle gesuchten (Pred, Suffix). Komprimieren und Dekomprimieren führen über die Anzahl der in der Tabelle belegten Einträge Buch und passen die Codelänge immer an, wenn ein weiteres Bit für die Adressierung erforderlich ist. Auf diese Weise ist es möglich, mit kurzen Codelängen anzufangen, ohne darauf verzichten zu müssen, die Adresse von Tabelleneinträgen errechnen und damit schneller finden zu können.
Wenn eine einmal gelernte Zeichenfolge nie mehr vorkommt, kann man sie aus der Tabelle entfernen und den freigewordenen Platz für eine andere Zeichenfolge verwenden. Der Dekompressionsablauf des erweiterten LZW unterscheidet sich vom einfachen, wenn die Gedächtnistabelle voll ist. Statt nur mit dem erworbenen Wissen weiterzumachen, versucht es, unnötiges zu vergessen und damit neues zu lernen. Für die Entscheidung, ob Tabelleneinträge vergessen werden dürfen, erhalten sie `referenziert´-Kennzeichnungen und sind damit löschgeschützt. Bei der Initialisierung werden die Einträge mit Pred = NoPred und mit Pred = ImPred ebenso geschützt.
Beim Crunchen werden die Daten anhand des LZW-Algorithmus komprimiert, wobei die Zeichenfolgen aus Bytes gebildet werden - und zwar je nach Version des Programmes mit fester Codelänge oder mit variabler Codelänge und Codewiederverwendung. Einige Crunch-Versionen haben reservierte Codes für besondere Funktionen. Um Problemen vorzubeugen, werden diese Codes bei der Initialisierung der Tabelle mit Pred = ImPred, also als gesperrt, eingetragen.
Beim Vergleich der Wissensbeschaffung von LZW und LZSS fällt folgender Unterschied auf: LZW baut eine Tabelle aus den Zeichenfolgen auf, die am Dateianfang stehen - anschließend ist diese Tabelle mit dem Wissen recht statisch. LZSS hingegen sucht die Zeichenfolgen im Puffer, in dem die letzten paar KByte gelesener Daten stehen. Ändern sich die Zeichenfolgen, die in der Datei vorkommen, paßt sich LZSS automatisch an. Das erinnert an den Unterschied zwischen dem dynamischen und dem adaptiven Huffman.
Beim LZSS-Algorithmus gibt es drei zentrale Konstanten: die Größe des Ringpuffers, die maximale Länge einer Zeichenfolge - mehr Zeichen werden beim Vergleichen einfach nicht herangezogen - und die Mindestlänge einer Zeichenfolge. Diese drei Konstanten heißen im folgenden Puffergröße, MaxLänge und MinLänge. Der Wert MinLänge-1 wird im allgemeinen als Schwelle (Threshold) bezeichnet.
Kompressionsprogramme reservieren für den Puffer meist einen Speicherbereich, der MaxLänge-1 Zeichen länger als die Puffergröße ist. Die zusätzlichen Zeichen hinten am Puffer haben dabei stets denselben Inhalt wie die ersten MaxLänge-1 Zeichen. Sie stehen hier ein zweites Mal, damit das Prüfen, ob eine Zeichenfolge im Puffer steht, am Pufferende schneller erfolgen kann.
Weiterhin erzeugt die Kompression entweder die Originaldaten oder eine Längenangabe, gefolgt von einer Adreßangabe. Damit der Dekompressor die erhaltenen Informationen auch verstehen kann, muß er zwischen einem normalen Zeichen und einer Längenangabe unterscheiden können. Dazu wird einfach die Zeichenmenge um Zeichen für die Längenangaben erweitert. Wie bei der Standard-Lauflängen-Kodierung wäre auch ein Zeichen für `Längenangabe folgt´ verwendbar; das ist aber eigentlich auch nichts anderes als eine Erweiterung der Zeichenmenge.
Üblicherweise sind die Zeichen, die der LZSS-Algorithmus verarbeitet, ganz normale Bytes, also Werte von 00h bis FFh. Die Längenangaben werden dann durch die nächsten möglichen Werte, also 100h, 101h, und so weiter dargestellt. Um aus einer Längenangabe den zugehörigen Zeichencode zu erhalten, addiert man dann 100h minus MinLänge dazu. Dieses neunte Bit ist auf den ersten Blick gewöhnungsbedürftig, doch für eine Kodierung wie Huffman ist die Art der Zeichen belanglos - Hauptsache, sie sind zählbar.
Eine ältere LZH-Implementation verwendet einen 4 kB langen Ringpuffer, so daß die Adreßangaben 12 Bit lang sind. Diese werden ebenfalls kodiert: Die oberen 6 Bit der Adresse werden über eine Tabelle in drei bis acht Bit kodiert. Dabei erhalten kleine Werte wenige Bit; da die Adreßangaben relative Adressen zur aktuellen Pufferposition sind, werden `junge´ Zeichenfolgen bevorzugt. Die unteren 6 Bit bleiben unverändert; insgesamt ist die Adreßangabe damit neun bis 14 Bit lang.
Beim Dekodieren einer Adreßangabe werden erst einmal acht Bit gelesen. Diese umfassen auf jeden Fall den Code für die oberen 6 Bit der Adreßangabe. Über eine Tabelle werden diese und die Länge des Codes, mit dem die oberen 6 Bit kodiert wurden, ermittelt. Ist diese Länge kleiner als acht, stehen in den unteren Bit des eben gelesenen Bytes schon acht minus Länge Bit der unteren 6 Bit der Adreßangabe. Da insgesamt Länge plus 6 Bit ausgegeben wurden und bislang 8 Bit gelesen wurden, müssen noch Länge minus 2 Bit nachgelesen werden, um alle Informationen zu erhalten.
In der arithmetischen Kodierung sind die Zeichen als Intervalle der Form [a, b) darzustellen, deren Längen den Häufigkeiten entsprechen und, beginnend bei Null, hintereinander- gelegt werden. Da die Summe der Häufigkeiten 1 ist, ergibt diese Kette von Intervallen das Intervall [0, 1). Für möglichst kurze Codes nimmt man natürlich die Zahl mit den wenigsten Stellen, die in dem Intervall des Zeichens liegt. Da alle vorkommenden Zahlen im Intervall [0, 1) liegen, sind sie der Form Null-Komma-Irgendwas; die Kodierung beschränkt sich folglich auf die Nachkommastellen.
Nimmt man das Beispiel mit den Buchstaben `A´ bis `D´ und den Häufigkeiten 0.5, 0.25, 0.15 beziehungsweise 0.1 für die einzelnen Zeichen, baut daraus die Intervalle [0, 0.5), [0.5, 0.75), [0.75, 0.9) und [0.9, 1) auf und ermittelt die passenden Binärcodes, so ergeben sich die vier Codes 0b, 1b, 11b und 1111b entsprechend den Dezimalbrüchen 0.0, 0.5, 0.75 und 0.9375.
Dies ist aber nur der erste Schritt der Kodierung. Bei der arithmetischen Kodierung werden nämlich Zeichenfolgen und nicht einzelne Zeichen in einen Code umgesetzt. Und das geschieht wie folgt: Das erste Zeichen einer Folge liefert ein Intervall. Dieses Intervall ist wiederum genauso wie zu Beginn das Intervall [0, 1) entsprechend der Häufigkeiten der Zeichen teilbar. Dann führt das zweite Zeichen wieder zu einem Intervall, welches im ersten liegt, und so weiter. `BBBB´ zum Beispiel wird über die Intervall-Folge [0.10b, 0.11b) - [0.1010b, 0.1011b) - [0.101010b, 0.101011b) - [0.10101010b, 0.10101011b) in die Zahl 0.10101010b und damit in den Code 10101010b umgesetzt.
Da die Intervallschachtelung nicht unendlich weitergehen kann, muß das Ende einer kodierten Zeichenfolge erkennbar sein. Dazu dient ein ansonsten ungenutztes Zeichen. Normalerweise sind Bytefolgen (Zeichen 00h bis FFh) zu kodieren. Also nimmt man einfach ein weiteres Zeichen als Endekennung - es kommt natürlich in einer Zeichenfolge nur einmal vor - und berechnet die 257 erforderlichen Häufigkeiten.
Die Ermittlung der Häufigkeiten einzelner Zeichen kann, wie bei Huffman, auf dreierlei Arten erfolgen: statisch, dynamisch und adaptierend. Bleiben noch ein paar Anmerkungen zur Implementierung:
Die hier beschriebenen Kompressionsalgorithmen sind nicht für bestimmte, sondern für beliebige Daten vorgesehen. Man kann sie auf diversen Systemen von CP/M bis DOS oder Unix finden. Je nachdem, wie die Daten wirklich aussehen, kann das eine oder andere Verfahren das bessere sein. Als Faustregel läßt sich jedoch sagen, daß die durchschnittliche Kompressionsrate von Squeeze über LZW, LZH bis LZAri immer besser wird. Es gibt auch Kompressionsprogramme wie zum Beispiel PKARC, die die Daten erst analysieren und dann entscheiden, welcher Algorithmus zur Anwendung kommt.
Eine andere Situation für die Entwicklung spezieller Algorithmen ergibt sich, wenn es mehr auf die Geschwindigkeit als auf die Kompressionsrate ankommt. Die hier beschriebenen Algorithmen sind im allgemeinen recht zeitintensiv, was nicht immer angebracht ist. Zum Beispiel bei der Speicherung und Übertragung von Bewegtbildern kommt es vor allem auf die Geschwindigkeit der Kompression und Dekompression an; teilweise sogar unter Verzicht auf die exakte Wiederherstellung der Daten. (un)
