Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


22. Datenkomprimierung



Kodierung mit variabler Länge

Im vorliegenden Abschnitt betrachten wir ein Datenkompressionsverfahren, das in Textdateien (und vielen anderen Arten von Dateien) eine beträchtliche Platzeinsparung ermöglichen kann. Die Idee besteht darin, von der Methode abzuweichen, mit der Textdateien gewöhnlich gespeichert werden: Anstatt die üblichen sieben oder acht Bits für jedes Zeichen zu benutzen, werden für Zeichen, die häufig auftreten, nur wenige Bits verwendet, und mehr Bits für die, die selten vorkommen.

Es ist zweckmäßig, wenn wir anhand eines kleinen Beispiels betrachten, wie der Code benutzt wird, bevor wir beschreiben, wie er erzeugt wird. Nehmen wir an, daß wir die Zeichenfolge »ABRACADABRA« kodieren möchten. Eine Kodierung mittels unseres standardmäßigen binären Codes, bei dem die Binärdarstellung von i mit Hilfe von fünf Bits zur Darstellung des i-ten Buchstaben des Alphabets benutzt wird (0 für Leerzeichen), ergibt die folgende Bitfolge:

0000100010100100000100011000010010000001000101001000001

Um diese Meldung zu dekodieren, lese man einfach jeweils fünf Bits und wandle diese entsprechend dem oben definierten binären Code um. In diesem Standard-Code benötigt das nur einmal vorkommende D die gleiche Anzahl Bits wie A, welches fünfmal auftritt. Bei Verwendung eines Codes mit variabler Länge können wir eine Platzeinsparung erzielen, indem wir häufig verwendete Zeichen mittels möglichst weniger Bits verschlüsseln, so daß die Gesamtzahl der für die Zeichenfolge benutzten Bits minimiert wird.

Wir können versuchen, den am häufigsten verwendeten Buchstaben die kürzesten Bitfolgen zuzuweisen, indem wir A mit 0 kodieren, B mit 1, R mit 01, C mit 10 und D mit 11, so daß ABRACADABRA als

0 1 01 0 10 0 11 0 1 01 0

kodiert würde. Hier werden nur 15 Bits im Vergleich zu den oben erforderlichen 55 Bits benutzt, doch es ist kein wirklicher Code, da er von den Leerzeichen abhängt, die die Zeichen voneinander abgrenzen. Ohne die Leerzeichen könnte die Zeichenfolge 010101001101010 als RRRARBRRA oder eine Reihe weiterer Zeichenfolgen dekodiert werden. Trotzdem ist die Zahl von 15 Bits plus 10 Begrenzern viel kompakter als der Standard-Code, vor allem weil keine Bits verwendet werden, um Buchstaben zu kodieren, die in der Meldung nicht vorkommen. Von Rechts wegen müssen wir auch die Bits im Code selbst mitzählen, da die Meldung ohne ihn nicht dekodiert werden kann und der Code von der Zeichenfolge abhängt (andere Zeichenfolgen entsprechen anderen Buchstabenhäufigkeiten). Wir gehen auf diese Frage später ein; vorerst wollen wir sehen, wie kompakt wir die Zeichenfolge darstellen können.

Zunächst werden keine Begrenzer benötigt, wenn kein Zeichencode mit dem Anfang eines anderen übereinstimmt. Wenn wir zum Beispiel A mit 11 verschlüsseln, B mit 00, C mit 010, D mit 10 und R mit 011, so gibt es nur eine Möglichkeit, die aus 25 Bits bestehende Zeichenfolge

1100011110101110110001111

zu dekodieren.

Eine einfache Methode zur Darstellung des Codes ist die Verwendung eines Trie (siehe Kapitel 17). Tatsächlich kann jeder beliebige Trie mit M äußeren Knoten benutzt werden, um jede beliebige Zeichenfolge mit M verschiedenen Zeichen zu kodieren. Als Beispiel zeigt Abbildung 22.2 zwei Codes, die für ABRACADABRA verwendet werden könnten. Der Code für jedes Zeichen wird durch den Pfad von der Wurzel zu diesem Zeichen bestimmt, mit 0 für »nach links gehen« und 1 für »nach rechts gehen«, wie gewöhnlich in einem Trie. Demzufolge entspricht der links dargestellte Trie dem oben angegebenen Code, und der rechts dargestellte Trie entspricht einem Code, der die Zeichenfolge

Abbildung 22.2
Abbildung 22.2 Zwei Tries für die Kodierung von A, B, C, D und R.

01101001111011100110100

erzeugt, die um zwei Bits kürzer ist. Die Darstellung als Trie garantiert, daß kein Code für ein Zeichen mit dem Anfang eines anderen übereinstimmt, so daß sich die Zeichenfolge unter Benutzung des Trie auf eindeutige Weise dekodieren läßt. Bei der Wurzel beginnend bewege man sich entsprechend den Bits der Zeichenfolge im Trie abwärts; jedesmal, wenn ein äußerer Knoten angetroffen wird, gebe man das zu diesem Knoten gehörige Zeichen aus und beginne erneut bei der Wurzel.

Doch welchen Trie sollte man am besten benutzen? Es erweist sich, daß es einen eleganten Weg gibt, wie man für eine beliebige gegebene Zeichenfolge einen Trie berechnen kann, der zu einer Bitfolge minimaler Länge führt. Das allgemeine Verfahren zur Bestimmung dieses Codes wurde 1952 von D. Huffman entdeckt und wird Huffman-Kodierung genannt. (Die Implementation, die wir betrachten wollen, verwendet etwas modernere algorithmische Techniken.)


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]