Robert Sedgewick: Algorithmen

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


22. Datenkomprimierung



Lauflängenkodierung

Der einfachste Typ einer Redundanz in einer Datei sind lange Folgen sich wiederholender Zeichen, die wir Läufe (runs) nennen wollen. Betrachten wir zum Beispiel die folgende Zeichenfolge:

AAAABBBAABBBBBCCCCCCCCDABCBAAABBBBCCCD

Diese Zeichenfolge kann in einer kompakteren Form kodiert werden, indem jede Serie sich wiederholender Zeichen durch eine einmalige Angabe des sich wiederholenden Zeichens und einer Angabe der Anzahl der Wiederholungen ersetzt wird. Wir würden sagen, daß diese Zeichenfolge aus 4 A besteht, denen 3 B folgen, denen 2 A folgen, denen 5 B folgen usw. Das Komprimieren einer Zeichenfolge in dieser Weise nennt man Lauflängenkodierung (run-length encoding). Wenn lange Läufe auftreten, können die Einsparungen ganz erheblich sein. Es gibt - in Abhängigkeit von den durch Anwendung vorgegebenen Bedingungen - verschiedene Methoden zur Umsetzung dieser Idee. (Sind die Läufe gewöhnlich relativ lang? Wie viele Bits werden verwendet, um die zu kodierenden Zeichen zu kodieren?) Wir betrachten ein spezielles Verfahren und erörtern dann weitere Möglichkeiten.

Wenn wir wissen, daß unsere Zeichenfolge nur Buchstaben enthält, können wir die Anzahl einfach kodieren, indem wir Ziffern zwischen die Buchstaben setzen. Demzufolge könnte unsere Zeichenfolge wie folgt kodiert werden:

4A3BAA5B8CDABCB3A4B3CD

Hierbei steht »4A« für »vier Buchstaben A« usw. Wir bemerken, daß es sich nicht lohnt, Läufe der Länge eins oder zwei zu kodieren, da für die Kodierung zwei Zeichen benötigt werden.

Für binäre Dateien wird gewöhnlich eine verfeinerte Variante dieser Methode benutzt, mit der drastische Einsparungen erzielt werden können. Die Idee besteht einfach darin, die Lauflängen zu speichern und dabei die Tatsache auszunutzen, daß sich Läufe zwischen 0 und 1 abwechseln, so daß auf das Speichern der Werte 0 und 1 selbst verzichtet werden kann. Dies setzt voraus, daß wenig kurze Läufe auftreten (wir sparen bei einem Lauf nur dann Bits ein, wenn die Länge des Laufs größer ist als die Anzahl der Bits, die benötigt werden, um diese Länge als Binärzahl darzustellen), doch kein Verfahren der Lauflängenkodierung funktioniert gut, wenn nicht die meisten Läufe lang sind.

Abbildung 22.1 ist eine »Raster«-Darstellung des auf der Seite liegenden Buchstaben »q«; dies ist typisch für die Art von Information, die mit Hilfe eines Satz-Systems (wie z.B. dem System, das zum Druck des vorliegenden Buches benutzt wurde) verarbeitet wird. Rechts befindet sich eine Liste der Zahlen, die verwendet werden können, um den Buchstaben in einer komprimierten Form zu speichern. Das bedeutet, daß die erste Zeile aus 28 Nullen besteht, denen 14 Einsen folgen, denen weitere 9 Nullen folgen usw. Die 63 Zahlenangaben in dieser Tabelle enthalten zusammen mit der Anzahl der Bits pro Zeile (51) genügend Information, um das Bit-Feld zu rekonstruieren (insbesondere betonen wir, daß kein »Zeilenende«-Indikator benötigt wird). Wenn sechs Bits für die Darstellung jeder Zahlenangabe benutzt werden, wird die gesamte Datei mit Hilfe von 384 Bits dargestellt, was gegenüber den 975 Bits, die notwendig sind, um sie explizit zu speichern, eine beträchtliche Einsparung ist.

Abbildung 22.1
Abbildung 22.1 Ein typisches Bitraster, mit Informationen für die Lauflängenkodierung.

Die Lauflängenkodierung erfordert unterschiedliche Darstellungen für die Datei und ihre kodierte Variante, so daß sie nicht für alle Dateien möglich ist. Dies kann sehr störend sein: Beispielsweise ist die oben vorgeschlagene Methode zur Komprimierung von Zeichendateien nicht für Zeichenfolgen geeignet, die Ziffern enthalten. Wenn andere Zeichen verwendet werden, um die Zahlenangaben zu kodieren, so ist sie nicht für Zeichenfolgen anwendbar, die die betreffenden Zeichen enthalten. Um eine Möglichkeit zur Kodierung einer beliebigen Folge von Zeichen aus einem feststehenden Zeichen-Alphabet unter ausschließlicher Verwendung der Zeichen dieses Alphabets zu illustrieren, wollen wir annehmen, daß uns nur die 26 Buchstaben des Alphabets (und Leerzeichen) zur Verfügung stehen, mit denen wir arbeiten können.

Wie können wir erreichen, daß einige Buchstaben Ziffern und andere Buchstaben Teile der zu verschlüsselnden Zeichenfolge darstellen? Eine Lösung besteht darin, ein Zeichen, das im Text wahrscheinlich nur selten erscheint, als sogenanntes Escape-Zeichen zu verwenden. Jedes Auftreten dieses Zeichens besagt, daß die folgenden beiden Buchstaben ein Paar (Zähler, Zeichen) bilden, wobei Zähler dargestellt werden, indem der i-te Buchstabe des Alphabets zur Darstellung der Zahl i benutzt wird. Demzufolge könnte unser Beispiel einer Zeichenfolge mit Q als Escape-Zeichen wie folgt dargestellt werden:

QDABBBAAQEBQHCDABCBAAAQDBCCCD

Die Kombination des Escape-Zeichens, des Zählers und der einen Kopie des sich wiederholenden Zeichens wird Escape-Sequenz genannt. Wir bemerken, daß es sich nicht lohnt, Läufe zu verschlüsseln, die weniger als vier Zeichen umfassen, da für die Verschlüsselung eines beliebigen Laufs mindestens (siehe unten) drei Zeichen erforderlich sind.

Doch was ist zu tun, wenn das Escape-Zeichen selbst in den Eingabedaten auftritt? Wir dürfen diese Möglichkeit nicht einfach ignorieren, da es kaum zu gewährleisten ist, daß irgendein spezielles Zeichen nicht auftreten kann. (Zum Beispiel könnte jemand versuchen, eine Zeichenfolge zu kodieren, die bereits kodiert worden ist.) Eine Lösung für dieses Problem besteht in der Benutzung einer Escape-Sequenz mit einem Zähler Null zur Darstellung des Escape-Zeichens. Demzufolge könnte in unserem Beispiel das Leerzeichen die Null darstellen, und die Escape-Sequenz »Q<Leerzeichen>« würde jedes Auftreten von Q in den Eingabedaten bezeichnen. Es ist interessant anzumerken, daß nur Dateien, die Q enthalten, durch dieses Komprimierungsverfahren verlängert werden. Wenn eine bereits komprimierte Datei nochmals komprimiert wird, vergrößert sie sich um eine Anzahl von Zeichen, die wenigstens gleich der Anzahl der benutzten Escape-Sequenzen ist.

Sehr lange Läufe können mit Hilfe mehrerer Escape-Sequenzen kodiert werden. Zum Beispiel würde ein aus 51 As bestehender Lauf unter Verwendung der obigen Vereinbarungen als QZAQYA kodiert. Wenn viele sehr lange Läufe zu erwarten sind, könnte es lohnenswert sein, für die Kodierung der Zähler mehr als ein Zeichen zu reservieren.

In der Praxis empfiehlt es sich, sowohl das Komprimierungs- als auch das Expandierungsprogramm in gewissem Maße fehlersensitiv zu machen. Dies läßt sich erreichen, indem eine gewisse Redundanz in die komprimierte Datei eingebaut wird, so daß das Expandierungsprogramm eine unbeabsichtigte geringfügige Änderung in der Datei zwischen der Komprimierung und ihrer Expandierung ausgleichen kann. Zum Beispiel lohnt es sich sicher, in die obige komprimierte Variante des Buchstaben »q« Zeilenendezeichen einzusetzen, so daß sich das Expandierungsprogramm im Falle eines Fehlers wieder synchronisieren kann.

Für Textdateien ist die Lauflängenkodierung nicht besonders effizient, da das einzige Zeichen, bei dem Wiederholungen wahrscheinlich sind, das Leerzeichen ist, und es für die Kodierung sich wiederholender Leerzeichen einfachere Methoden gibt. (Diese wurden in der Vergangenheit sehr erfolgreich angewandt, um Textdateien zu komprimieren, die durch das Einlesen von Lochkartenstapeln erzeugt wurden, die notwendigerweise viele Leerzeichen enthielten.) In modernen Systemen werden Zeichenfolgen aus sich wiederholenden Leerzeichen niemals eingegeben und niemals gespeichert: Leerzeichenfolgen am Zeilenanfang werden als »Tabs« kodiert, und Leerzeichen an den Zeilenenden werden durch die Benutzung von Zeilenendezeichen vermieden. Eine Implementation der Lauflängenkodierung ähnlich der oben angegebenen (doch dahingehend modifiziert, daß alle darstellbaren Zeichen behandelt werden können) ergibt bei Anwendung auf die Textdatei für das vorliegende Kapitel Einsparungen von nur ungefähr 4% (und diese Einsparungen ergeben sich alle aus Abbildung 22.1!)


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