Warum kann man mit weitverbreiteten Programmen, wie PKARC, LHARC, PKPAK, PKZIP überhaupt fast alle Daten komprimieren? Die traditionelle Antwort auf diese Frage lautet: die Text- und Programmdateien auf meinem Disk sind eben redundant. Durch Verringerung der Redundanz kann man den Speicherbedarf verkleinern. Tatsächlich ist es allerdings so, dass fast alle möglichen Dateien von PKZIP ein wenig vergrössert werden und nur aus diesem Grund einige wenige Dateien substanziell verkürzt werden können. Der Trick bei diesen Programmen besteht darin, dass die meisten Dateien auf meiner Festplatte zu diesen wenigen gehören, die verkürzt werden.

Um erfolgreich zu komprimieren ist man also darauf angewiesen, dass man häufig vorkommende von selten vorkommenden Dateien unterscheiden kann. Wenn alle möglichen Dateien gleich häufig aufträten, wäre keine Kompression möglich. Seit den Arbeiten von Shannon und Weaver¹, welche die Informationstheorie begründeten, ist bekannt, dass der Informationsgehalt einer Nachricht günstigerweise mit dem negativen Zweierlogarithmus ihrer Wahrscheinlichkeit wiedergegeben wird und dass der durchschnittliche Informationsgehalt, die Entropie der Nachrichtenmenge, die erreichbare mittlere Kompressionsrate angibt.

In diesem Sinne kann man nicht a priori vom Informationsgehalt einer Datei oder eines Textes reden. Dieser ist erst definiert, wenn wir ein Modell für die Wahrscheinlichkeit haben, dass auch ein anderer Text vorliegen könnte. Es gibt keine "natürlichen" Modelle für den Informationsgehalt von Dateien, ausser etwa dem "algorithmischen" Informationsgehalt², der aber für konkrete endliche Daten nicht berechenbar ist.

Im Laufe der Jahre sind eine Reihe von Kodierungsalgorithmen entwickelt worden. Am berühmtesten dürfte die Huffmann-Kodierung sein, wo den Symbolen eines Alphabets umso kürzere Kodes zugeordnet werden, je häufiger sie vorkommen. Die seltenen Symbole werden dafür in längeren Bitsequenzen kodiert. In den bekannte PC-Kompressionsprogrammen, wie etwa PKZIP, wird vor allem die LZW-Kompression von Lempel, Ziv und Welch³ verwendet, wo die früh vorkommenden Teilstrings kurze Kodes erhalten und später vorgefundene mit immer grösseren Kodenummern wiedergegeben werden. Rissanen und Langdon haben vor etwas mehr als zehn Jahren einen sehr allgemeinen Kompressionsalgorithmus entwickelt: die Arithmetische Kodierung⁴.

Die Grundidee der Arithmetischen Kodierung besteht darin, dass man Dateien als Bitketten betrachtet und diese hinter einem imaginären "0." als "Dezimalbruchentwicklung" einer rationalen Zahl zwischen 0 und 1 im Zweiersystem interpretiert (d.h. also als dyadische Entwicklung). Jede Datei entspricht bei dieser Interpretation genau einer rationalen Zahl zwischen 0 und 1. Die Verschiedenheit der Wahrscheinlichkeiten wird durch den Algorithmus der Arithmetischen Kodierung ausgeglichen. Die aus diesem Ausgleich resultierende Gleichverteilung lässt keine weitere Kompression mehr zu.

Etwas genauer funktioniert das folgendermassen: In jedem Zeitpunkt der Kompression wird das verarbeitete Teilstück von n Bits durch ein Teilintervall In des Bereichs [0,1) repräsentiert. Ein externes Wahrscheinlichkeitsorakel wird befragt, was die Wahrscheinlichkeit Pn+1(bn+1) des nächsten zu kodierende Bits bn+1 ist. Dieses Orakel basiert seine Angabe auf den schon verarbeiteten vorangegangenen Bits b1 ... bn. Technisch handelt es sich also um die "bedingte" Wahrscheinlichkeit Pn+1(bn+1) = P(bn+1|b1 ... bn). Das Intervall In wird im Verhältnis Pn+1(0):Pn+1(1) unterteilt. Je nachdem, ob das n+1-te Bit 0 oder 1 war, wird das entsprechende Teilintervall als Intervall In+1 verwendet. Dank der Aufteilung des Intervalls In im Verhältnis der Wahrscheinlichkeiten erreicht man eine uniforme Verteilung der Wahrscheinlichkeit im Einheitsintervall.

Gestartet wird der Algorithmus mit dem ganzen Einheitsintervall I0 = [0,1). Darauf wird das erste Bit b1 betrachtet. Die Summe der Wahrscheinlichkeiten aller Strings die mit dem Bit 0 anfangen, ist P1(0), die Wahrscheinlichkeit, eine 1 zuerst zu finden ist P1(1). Um die Wahrscheinlichkeit gleichmässig zu verteilen, unterteilen wir das Intervall [0,1) im Verhältnis P1(0) : P1(1) und arbeiten mit dem dem Bit b1 entsprechenden

Teilintervall I1 weiter. Dessen Länge ist gerade gleich der Wahrscheinlichkeit des ersten Bits P1(b1). Dieses Intervall wird weiter unterteilt gemäss der Wahrscheinlichkeit des zweiten Bits. Die Intervallänge des resultierenden zweiten Intervalls I2 ist also gerade gleich der Wahrscheinlichkeit, dass der zu kodierende String mit den Bits b1, b2 anfängt.

Manche Leser werden sich fragen, wo denn nun die komprimierten Daten stecken, da bisher nur von Teilintervallen des Einheitsintervalls die Rede war. Am Ende der Kompression wird der Algorithmus ein Intervall Iz erzeugt haben, dessen Länge gleich der Wahrscheinlichkeit des ganzen Strings ist. Um dieses Intervall zu übermitteln genügt es, eine dyadische Entwicklung einer rationalen Zahl mit möglichst wenigen Stellen anzugeben, die in diesem Intervall liegt. Diese Zahl k stellt den kodierten String dar. Ihre Länge entspricht gerade dem negativen Zweierlogarithmus der Intervallänge, d.h. der Wahrscheinlichkeit.

Der Dekoder macht einfach die beschriebenen Schritte rückgängig: Er startet auch mit dem Intervall [0,1). Er benützt dasselbe Wahrscheinlichkeitsorakel zu Unterteilung dieses Intervall. Je nachdem, ob die übermittelte Zahl k in der linken oder rechten Hälfte liegt, ermittelt er, dass das erste Datenbit eine 0 oder eine 1 war. Das entsprechende Teilintervall wird wieder unterteilt und darauf geprüft, in welchem Teil k liegt. Dies ergibt das zweite Bit. Da dieser Algorithmus die Beendigung ein bisschen kompliziert, ist es praktisch, als erstes die unkomprimierte Länge zu übermitteln. In allen praktischen Anwendungen werden 4 Bytes dazu hinreichend sein.

In der Praxis ist es natürlich mit normalen Programmiersprachen nicht möglich, immer genauere rationale Zahlen zu speichern, die immer mehr Bits zu ihrer Repräsentation benötigen. Weil aber meistens die obere und die untere Grenze des momentan betrachteten Intervalls in den führenden Bits übereinstimmen, kann man sich dadurch behelfen, dass man die oberen gemeinsamen Bits schon hinausshiftet. Da die dem kodierten Bitstrom entsprechende Zahl k zwischen der oberen und der unteren Grenze des Intervalls liegt, wird sie sicher diese führenden Bits mit den beiden Intervallgrenzen gemeinsam haben. Von den anschliessenden Bits, in denen sich die untere und die obere Grenze unterscheiden, können wir etwa die nächsten 16 Bit in ein Computerword stecken und die Unterteilung gemäss der Wahrscheinlichkeit innerhalb dieser 16-Bit-Arithmetik durchführen.

Diese Idee hat nur einen Haken: Es könnte sich ergeben, dass längere Zeit die obere Grenze knapp über 0.5 (0.1000...) liegt und die untere Grenze knapp darunter (0.0111...). Erst, wenn sich herausstellt, dass k grösser oder kleiner 0.5 ist, kann entschieden werden, ob zuerst eine 0 oder eine 1 hinausgeshiftet werden muss. Solche und ähnliche Fälle sind durch die Bitmuster 0111... (für low), 1000... (für high) charakterisiert. Da man weiss, dass hinter dem ersten (unentschiedenen) Bit lauter gegenteilige Bits kommen, kann man diese ohne zu speichern hinausshiften, und nur mitzählen, wieviele man "schuldet". Sobald sich entscheidet, ob das unentschiedene Bit eine 1 oder eine 0 ist, kann man die Schuld abtragen, indem man die entsprechende Anzahl 0en oder 1en nachschiebt. Anhand der hinten abgebildeten und besprochenen Implementation in Turbo PASCAL kann man diese etwas abstrakten Bemerkungen konkret nachvollziehen.

Da wir auf realen Maschinen immer mit Byteströmen und nicht mit Bitströmen arbeiten, ist es für die praktische Implementation auch nützlich, wenn die Unterteilung des Intervall gerade auf die Wahrscheinlichkeit des nächsten Bytes bezogen wird. Damit dies

bequem möglich ist, fordert man für das Byte b vom Wahrscheinlichkeitsorakel eine kumulative Wahrscheinlichkeit C(b) an, die angibt, wie wahrscheinlich es ist, dass das nächste Byte kleiner als b ist.

Gemäss den obigen Ausführungen ist die resultierende Intervallänge bis auf Rundungsfehler gerade gleich der Wahrscheinlichkeit P des ganzen Strings gemäss dem Wahrscheinlichkeitsorakel. Die Anzahl Bits, die für eine Zahl k in diesem Intervall benötigt wird, ist also gerade -log2(P). Damit haben wir (bis auf Rundungsfehler) das theoretische Optimum der Kompression erreicht, die auf diesem Wahrscheinlichkeitsmodell fusst. Tatsächlich kann man mit der Arithmetischen Kodierung jede bekannte Kompression unterbieten, oder zumindest gleichziehen, indem man das implizite Wahrscheinlichkeitsmodell verwendet.

Je nach Wahrscheinlichkeitsorakel wird aus der Arithmetischen Kodierung ein anderer Kompressionsalgorithmus. Dank der expliziten Trennung von Wahrscheinlichkeitsmodell und Kodierungsmechanismus ist man frei, zur Kompression das angemessenste Wahrscheinlichkeitsmodell auszuwählen. Der Algorithmus des Arithmetischen Kodierens garantiert dann die modell-optimale Kompression.

Man mag die Optimalität der Arithmetischen Kodierung anzweifeln, weil man sich dunkel erinnert, in der Informatikvorlesung einen Beweis gehört zu haben, dass die Kompression des Huffmann-Kodes nicht überboten werden könne. In der Vorlesung wurde allerdings davon ausgegangen, dass jedem Symbol im Alphabet eine ganze Anzahl Bits zugeordnet werde. Bei der Arithmetischen Kodierung können hingegen auch Bruchteile von Bits für die Kodierung eines Symbols verwendet werden, wenn die Intervallänge pro kodiertem Zeichen um weniger als die Hälfte abnimmt.

Die momentan hintersten 16 Bits der Intervallgrenzen speichern wir in den WORDs low und high. Anfänglich ist low = $0000 und high = $FFFF. Bei low stellt man sich die weiteren dyadischen Ziffern mit 0 aufgefüllt vor, bei high mit 1. Der Bereich zwischen low und high entspricht also high-low+1.

Beim Kodierschritt für ein Byte wollen wir die Invarianz erhalten, dass dieser Bereich grösser als $4000 bleibt. Wir nehmen an, dass die Wahrscheinlichkeiten als WORDs angeliefert werden, die mit einem Skalierungsfaktor ebenfalls vom Typ WORD behaftet sind. Damit die kumulativen Wahrscheinlichkeiten aufeinanderfolgender Zeichen auch bei der Unterteilung des Intervalls merkliche Unterschiede zurücklassen, muss der minimale Unterschied zweier aufeinanderfolgender kumulativer Wahrscheinlichkeitswerte grösser als 1/$4000 sein.

Um nun ein Byte zu kodieren, müssen wir das momentane Intervall entsprechend der Modellwahrscheinlichkeit unterteilen, wie dies in der Funktion cut implementiert ist. Die Grenzen cut(ch) und pred(cut(succ(ch)) bilden die nächsten Intervallgrenzen.

Die Funktion shiftedout muss nun low, high soweit wie möglich nach links shiften, um high-low+1 $4000 zu halten. Bei diesem Shift müssen für high Einsen hineingezogen werden. Wir führen Buch über die "geschuldeten" Bits, wenn die obersten Bits von

low und high nicht übereinstimmen und shiften in diesem Fall das zweitoberste Bit hinaus mit der Funktion shift15.

Zu jedem Zeitpunkt der Kodierung werden die Intervallgrenzen durch die WORDs low und high und das schon abgespeicherte Präfix repräsentiert. Das Präfix, das erste Bit von low bzw. high, die geschuldete Anzahl Bits des dem ersten Bit entgegengesetzten Typs und die restlichen 15 Bits bilden die dyadische Entwicklung der Intervallgrenzen. Wenn man diese Invarianz beachtet, sieht man, dass die Arithmetik korrekt bleibt und dass die Intervallänge immer grösser als $4000 gehalten werden kann.

Schliesslich bleiben noch Anfang und Schluss zu formulieren. Wir speichern als erstes die Länge der Datei als Vier-Byte-Integer, damit der Dekoder weiss, wo er zu stoppen hat. Am Ende des Kodiervorgangs wird die kleinste Anzahl Bits ausgegeben, die das momentane Ausgabebyte komplettiert als eine Zahl zwischen low und high. Ausserdem wird das Wahrscheinlichkeitsmodell in diesen Programmteilen initialisiert bzw. terminiert.

Die Dekodierung läuft fast identisch, ausser dass ein momentanes value mitgeführt wird, das die momentanen 16 Bits des komprimierten Inputs enthält. Mit Hilfe des wahrscheinlichkeitstheoretischen Modells wird das momentane Intervall in 256 Teilintervalle aufgeteilt. Wenn das i-te Teilintervall den Wert value enthält, so erkennt der Dekoder den Wert i als das nächste dekodierte Byte. Indem die Shifterei mit dem Schulden für den Wert value, wie für low und high durchgeführt wird, löst man die "Schuldenfrage" beim Dekodieren elegant.

Die Funktion shiftedin wird zwar einfacher als shiftedout, ist aber trotzdem immer noch ein wenig trickreich.

Damit wir den Algorithmus testen können, müssen wir ihn noch mit einem informationstheoretischen Modell ausstatten. Diese erscheint in der Liste des Hauptprogramms nur in Form einer in der uses-Klausel aufgeführten Unit und in fünf Prozedur-Aufrufen: modelinit, modelprob, modelscale, modelupdate, modelterm.

Der Wert modelprob(ch)/modelscale gibt jeweils an, wie wahrscheinlich es ist, dass das nächste Zeichen kleiner als ch ist. modelupdate(ch) ermöglicht dem Wahrscheinlichkeitsmodell, seine Schätzungen an die Tatsache anzupassen, dass man dem Zeichen ch begegnet ist.

Ein triviales Modell etwa zählt nur die Zeichenhäufigkeiten und behandelt aufeinanderfolgende Bytes als unabhängig. Um Overflows zu vermeiden, dividiert es periodisch alle Wahrscheinlichkeiten und den Skalierungsfaktor durch zwei. Damit ist auch ein gewisses "Vergessen" der Vergangenheit gewährleistet, da nach dieser Division neue Zeichen mit doppeltem Gewicht zu Buch schlagen.

Das nächst intelligentere Modell, das wir hier als Beispiel aufführen, berücksichtigt Abhängigkeiten erster Ordnung. Die Übergangswahrscheinlichkeit zum jeweils nächsten Buchstaben wird laufend mitgeführt. Mit diesem Ansatz einer Markoffkette erster Ordnung komprimiert unser Programm AC PASCAL-Quellkode schon fast so gut, wie der PKZIP. Genauere statistische Analysen der zu komprimierenden Dateien führen zu immer besseren Modellen mit höheren Kompressionsraten.

Der Algorithmus des Arithmetischen Kodierens hat sich nur mit Mühe durchgesetzt, da er eher langsam ist. Vor zehn Jahren war die Tatsache, dass einige Multiplikationen pro Kodierschritt verwendet werden, prohibitiv. Wenn man das abgebildete Programm AC laufen lässt, so stellt man fest, dass es tatsächlich nicht sonderlich schnell ist. Der Profiler zeigt aber, dass die meiste Zeit im Schritt modelupdate verloren geht, der hier nicht sehr optimal implementiert ist. Man könnte etwa die laufenden Statistiken erst nach jeweils 100 Schritten zu den kumulativen Wahrscheinlichkeiten dazuzählen, um hier Beträchtliches einzusparen ohne merkbaren Verlust.

Offensichtlich kann man das angeführte Beispiel nicht ohne weiteres zu einer Markoff-Kette zweiter Ordnung erweitern, da für die Speicherung der Übergangswahrscheinlichkeiten in diesem Fall statt 128 KByte rund 32 MByte Speicher benötigt würden. Man muss also für die Speicherung sequenzieller Daten (Texte, Programme) zu Verfahren Zuflucht nehmen, die wie der LZW-Algorithmus nur diejenigen Teilstrings speichern, die häufig vorkommen und all die vielen Zeichenkombinationen vernachlässigen, die nie in den Daten auftreten.

Fast in jedem Fall ist es angezeigt, lernende, d.h. adaptive Modelle zu verwenden. Diese treffen seltener völlig daneben als statische Verfahren. Wenn das Modell die Realität völlig falsch einschätzt, führt die Kompression zu einer Vergrösserung der Datenmenge. Auch bei diesem Algorithmus Fall führt die Anwendung informationstheoretischer Konzepte direkt auf das Problem, der adaptiven wahrscheinlichkeitstheoretischen Modellierung der Eingabedaten. Dank der formalen Trennung von Kode und Modell bei der Arithmetischen Kodierung, kann man sich bei der Suche nach optimaler Kompression auf die den Daten angemessene Modellierung konzentrieren, da man den optimalen Algorithmus für die Kodierung schon hat.

Mai 1991 Hartwig Thomas

Arithmetische Kodierung: ac.pas

Input-/Outputprozeduren: inout.pas

Markoff-Modell: markov1.pas

Turbo-Pascal-Switch-Settings: switches.inc

¹ C. E. Shannon und W. Weaver, The mathematical theory of communication, University of Illinois Press, Urbana 1949

² G. J. Chaitin, Algorithmic Information Theory, Cambridge Tracts in Theoretical Computer Science 1, Cambridge University Press, 1987

³ Terry A. Welch: A Technique for High-Performance Data Compression, in IEEE Computer, vol. 17, no. 6, Juni 1984

⁴ J. Rissanen und G. G. Langdon Jr., Universal Modelling and Coding, IEEE Trans. Inf. Theory, Vol. IT-27, No. 1, Jan. 1981

G. G. Langdon Jr. und J. Rissanen, Compression of Black-White Images with Arithmetic Coding,IEEE Trans. Comm., Vol. COM-29, No. 6, Juni 1981

G. G. Langdon Jr. und J. Rissanen, A Fast Binary Source Code, IBM Research Report RJ3201, Juli 1981

G. G. Langdon Jr., A Tutorial on Arithmetic Coding, IBM Research Report RJ3128, Juni 1981

Ian H. Witten, Radford M. Neal, John G. Cleary, Arithmetic Coding for Data Compression, Comm ACM, 1987, vol 30, nr 6, pp 520-540