Algorithmen zur Datenreduktion, Teil 1
Während man gemeinhin die Leistungsfähigkeit von Kompressoren in »qm/h« und »bar« mißt, hat sich im EDV-Sektor noch eine weitere Maßeinheit etabliert - die der Kompressionsrate. Wir zeigen Ihnen, wie Sie zu möglichst hohem »Datenüberdruck« gegangen.
Eine Aufgabe, mit der sich jeder Computeranwender früher oder später auseinandersetzen muß, ist der Kapazitätsgrenze der Massenspeicher seines Rechners entgegenzuwirken. Über kurz oder lang bleibt der Kampf gegen überfüllte Festplatten hoffnungslos, dennoch neigt man dazu, ihn wegen der Kosten für ein neues Speichermedium längere Zeit auf sich zu nehmen. Ein bewährtes Mittel, um das nahende K.O. noch eine Weile vor sich her zu schieben, ist der Einsatz von »Pack-Programmen« wie etwa »PKZIP«, »LHarc« oder »ZOO«. Diesen Packprogrammen gelingt es, überflüssige Informationen in Dateien zu erkennen, um sie im gepackten Zustand auszusparen. Platz für neue Dateien ist geschaffen.
Eine erfolgreiche Größenreduzierung setzt natürlich voraus, daß sich ein Überfluß an Daten oder Informationen (»Redundanz«) in den zu packenden Dateien befindet. Ähnlich wie sich stundenlange Ansprachen von Politikern in zwei, drei Sätzen erschöpfend zusammenfassen lassen, lassen auch die Packer Überflüssiges weg. Gilt es den Inhalt einer Vorlesungsstunde möglichst knapp wiederzugeben, wird die Sache schon schwieriger. Um sicher zu gehen, daß man alle wichtigen Informationen beibehält, ist es sinnvoll, unverständliche Teile wörtlich zu übernehmen. Gleiches gilt für die Komprimieralgorithmen: Erkennen sie den Unterschied zwischen Text- und Bilddateien, können sie für den erkannten Datentyp das optimale Komprimierverfahren einsetzen.
Null-Diät
Muß der Professor in der Vorlesung noch irgendwelche unqualifizierten Zwischenfragen beantworten oder erzählt er gar Witze, würde man diese in einer Zusammenfassung wohl weglassen. Die Zusammenfassung würde dann aber nicht wiederspiegeln, ob die Vorlesung eher interessant oder gähnend langweilig war. Je nach späterer Verwendung, fällt die Zusammenfassung unterschiedlich aus.
Analog stellt sich die Frage, ob ein Packer einen »Lossy«-Algorithmus verwenden soll oder nicht. Ein Lossy-Algorithmus komprimiert sehr gut aber ungenau - die entpackte Datei weist Unterschiede zum Original auf. Für die Komprimierung von Bilddaten gibt es zwei Standards, getrennt für Standbilder (»JPEG«, Joint Photographics Experts Group, Kompressionsrate 15:1) und bewegte Bilder (»MPEG«, Motion Picture Experts Group, Kompressionsrate 100:1). Beide Verfahren gehören zu den »Lossy«-Komprimierern, liefern aber trotz der bemerkenswert hohen Komprimierraten sehr gute Wiedergaben. Da Motorola die DSP56000-Quelltexte für beide Algorithmen veröffentlicht hat, sind diese gerade für den Falcon030 interessant.
Jeder Komprimieralgorithmus eignet sich immer nur für bestimmte Datenmengen. Liefern Packprogramme bei verschiedenen Datenmengen dennoch ähnlich gute Komprimierraten, liegt das weniger am verwendeten Algorithmus als vielmehr daran, daß viele Packprogramme unter mehreren Kodierverfahren auswählen. Oft reicht es schon, ein Kodierverfahren nur mit anderen Parametern arbeiten zu lassen, um eine bestimmte Datenmenge optimal zu komprimieren. Weiter gilt, daß sich für jeden Komprimierer Daten finden lassen, deren kodierte Ausgaben vom Umfang gleich oder sogar größer sind als die Ursprungsdaten. Deshalb überprüfen alle professionellen Packer, ob ihr Ergebnis wirklich kleiner ausgefallen ist und übergeben die Dateien gegebenenfalls unkomprimiert. Hieraus läßt sich eine weitere Konsequenz ziehen: Das Komprimieren bereits gepackter Daten führt nicht zwangsweise zur erneuten Datenreduktion.
Alle hier vorgestellten Algorithmen arbeiten sequentiell, bearbeiten also Datensatz für Datensatz. Dies gilt sowohl für den Kodierer als auch für den Dekodierer. Einzig die Kodierung und die Wahl eines geeigneten Datensatzes unterscheidet die Algorithmen. Bei Bilddaten betrachtet man zum Beispiel Pixel, bei Samples 8- oder 16-Bit-Werte und bei Texten die einzelnen Zeichen als einen Datensatz. Allerdings läge es auch nahe, bei Textdateien ganze Zeichenketten (»Phrasen«) als Datensatz zu verwenden. Wie wir im zweiten Teil sehen werden, eignet sich dieser Ansatz nicht nur für Textdateien.
Bei der Implementation unterscheidet man zwischen drei Verfahren: »statisch«, »dynamisch« und »adaptiv«. Beim statischen Verfahren steht sowohl die Code-Größe wie auch die Code-Repräsentation von vornherein fest und ändert sich auch nicht mehr im Verlauf des Komprimierens. Diese Verfahren sind zwar sehr schnell, allerdings passen sie sich nicht an die zu bearbeitenden Daten an. Sie »wissen« bereits, weiche Art von Daten zu packen sind (zum Beispiel IMG-Format für Grafiken).
Lauflängenkodierung
Ein sehr einfaches Verfahren ist die Lauflängenkodierung (»Run-Length-Coding«). Dieses Verfahren ist zwar nicht besonders effizient, arbeitet dafür aber sehr schnell. Bekanntes Beispiel ist das IMG-Format. Bei mehreren sich wiederholenden gleichfarbigen Pixeln, speichert man nur einmal das Pixel plus einen Zähler ab. Die einzige Arbeit, die dann noch bleibt, ist die Unterscheidung einer Pixel-Zähler-Kombination und eines einzelnen Zeichens. Beim IMG-Format entschied man sich für folgende Lösung:
Eine längere Pixelfolge wird in einem Byte abgespeichert. Das oberste Bit signalisiert, ob es sich um ein gesetztes Bit (Bit = 1) oder um ein gelöschtes Bit (Bit = 0) handelt. Die restlichen 7 Bits enthalten dann den Byte-Zähler. Es lassen sich Pixelfolgen also nur bis zu einer Byte-Grenze kodieren. Bildmuster, also sich öfter ändernde Bits, speichert man als Musterfolgen (»Pattern Run«) ab. Eine Musterfolge besteht aus einem einleitenden Null-Byte (also eine Null-Pixelfolge der Länge Null), gefolgt von einem Byte, das den Musterzähler enthält. Anschließend kommt noch das eigentliche Muster. Wieviele Bytes zu einem Muster gehören, legt man im Datei-Header fest. Liefert keine der beiden Methoden das gewünschte Ergebnis, übernimmt man einfach die nächsten Bytes direkt. Einen solchen »Bit-String« leitet man mit einem 0-Byte (also einer Eins-Pixelfolge der Länge Null) gefolgt von einem Zähler-Byte ein.
Adaptiv kontra ...
Das adaptive Verfahren macht sich die sequenzielle Abarbeitung zu Nutze. Kodierer und Dekodierer merken sich immer die zuletzt bearbeiteten Daten und passen nach Abarbeitung einer bestimmten Datenmenge ihre Regeln und/oder Codes an die vorangegangenen Daten an, in der Hoffnung, daß die nächsten Daten den vorangegangenen ähneln. Ein- und Auspacker fangen also erst einmal mit statischen Regeln an und wechseln diese dann in bestimmten Abständen. Die schwierigste Aufgabe ist dabei die Synchronisation von Dekodierer und Kodierer. Hierfür ließen sich spezielle Steuercodes in den Datenstrom hinzufügen. Da diese jedoch wieder Platz benötigen, bevorzugt man feste Absprachen zwischen dem Komprimierer und Dekomprimierer. Eine solche Absprache könnte etwa so lauten: »Nach jeweils 100 gesendeten Daten sind die Regeln anhand der letzten 100 gesendeten Daten neu aufzubauen.« Eine gute Implementierung des adaptiven Verfahrens erzielt in größeren Dateien die besten Ergebnisse, allerdings ist der Aufwand sowohl für den Komprimierer wie für den Dekomprimierer recht hoch.
Bei der »dynamischen« Implementation übernimmt der Komprimierer die meiste Arbeit, womit der Dekomprimierer besonders schnell arbeitet. Hier erzeugt der Komprimierer in einem ersten Durchlauf nur die Regeln für die Code-Erzeugung, die - auf die gesamte Datei bezogen - die besten Ergebnisse erzielen. Diese Regeln sendet der Komprimierer an den Dekodierer. In einem zweiten Pass wendet der Komprimierer zur Kodierung der Daten die soeben erstellten Regeln an. In der Praxis findet man die dynamische Variante selten und dann meist nur als Option. Der Packer »PKZIP« berechnet die Länge der komprimierten Datei für das adaptive und dynamische Verfahren und wählt dann die bessere Methode.
... dynamisch
Allerdings lassen sich Anwendungen finden, die das dynamische Verfahren prinzipiell begrüßen. Bei Applikationen mit einem Hypertext-Hilfesystem (Beispiel: Pure C), lohnt es sich, die großen Textmengen in komprimierter Form zu speichern. Hier sollte der Dekomprimierer recht einfach gehalten sein, aber dennoch schnell dekodieren können. Außerdem spielt der Komprimieraufwand keine Rolle, da die Hilfetexte ja nur einmal zu komprimieren sind. Ein einfaches Beispiel, das man hauptsächlich in der dynamischen Variante findet, ist die Nachfolger-Kodierung, die in älteren Versionen von PKZIP unter dem Namen »Reduce« auftaucht. Hier macht man sich die Tatsache zu Nutze, daß einzelne Zeichen in Texten nicht autark sind, sondern kontextabhängig: Auf ein vorangegangenes Zeichen folgen vorzugsweise immer nur bestimmte Zeichen. Die Zeichenkombinationen »en«, »ei« oder »er« treten sicherlich häufiger in Texten auf als zum Beispiel »ez«. In einem ersten Pass ermittelt der Komprimierer zu jedem Zeichen die 16 häufigsten Nachfolgezeichen. Diese Liste schickt er den eigentlich kodierten Daten voraus. Das erste Bit eines kodierten Zeichens signalisiert, ob es sich um ein Zeichen aus der Nachfolgerliste handelt. Darauf folgt entweder ein 4-Bit-Wert, der die Nummer des Nachfolgerzeichens enthält oder aber ein 8-Bit-Wert, der das Zeichen (»literal«) selbst enthält.
Huffman-Kodierung
Kontextunabhängig und nur auf die Zeichenhäufigkeit aufbauend arbeitet der Huffman-Algorithmus. Dieser Algorithmus teilt häufig vorkommenden Zeichen kürzere und selten vorkommenden Zeichen längere Bitfolgen zu. Für die Entwicklung der Bitfolgen bedient sich Huffman eines Binärbaumes. Ausgehend von einer Liste der einzelnen Werte mit ihren Häufigkeiten, wählt man die zwei Werte mit den kleinsten Häufigkeiten aus und verbindet sie mit einem Knoten. Der Knoten zeigt dann mit einem rechten und einem linken Zeiger auf die beiden Elemente. Außerdem erhält der Knoten noch die Summe der beiden Häufigkeiten. jetzt fügt man diesen Knoten zur Liste und markiert die zwei Elemente als ungültig. Dieses Verfahren setzt man solange fort, bis alle Elemente bzw. Knoten in der Liste als ungültig markiert sind. Bei n Listeneinträgen sind das n-1 Schritte. Der letzte hinzugefügte Knoten repräsentiert die Wurzel des Baumes. Von diesem Knoten arbeitet man sich über die rechten und linken Zeiger zu den Blättern vor, die die Werte repräsentieren. Dabei fügt man ein gelöschtes Bit zur Bitfolge hinzu, wenn man einen linken Zeiger benutzte, andernfalls ein gesetztes Bit (siehe Bild 1). Wie man sieht, läßt sich der Baum beim Dekodieren direkt benutzen. Für das Kodieren bietet es sich an, den Listeneinträgen einen weiteren Zeiger hinzuzufügen, der auf das Vaterobjekt oder - um beim Baum zu bleiben - auf die nächste Astgabel in Richtung Wurzel zeigt. So kann man sich vom Blatt zur Wurzel vorarbeiten und dabei jedesmal mitprotokollieren, ob man von einem rechten oder linken Zweig kommt. Bei der Wurzel angekommen darf man dann nicht vergessen, die so entstandene Bitfolge noch umzudrehen. Da bei n zu kodierenden Werten die Bitfolgenlänge im Bereich von 1 bis n - 1 liegt, bei 256 Zeichen also eine Bitfolge bis zu 255 Bits betragen kann, lassen sich die Bitfolgen nicht in einer Long-Variablen mit zusätzlichen Bit-Zähler halten, was die Kodierung erheblich beschleunigen würde. Es bleibt also die Abarbeitung des Baumes für jeden Wert unumgänglich, obwohl bei durchschnittlichen Texten die maximale Bitfolge selten mehr als 16 Bit beträgt, also die seltensten Zeichen eines Textes nur in Ausnahmefällen mit mehr als 16 Bit kodiert sind.
Shannon-Fano-Kodierung
Ein weiterer Algorithmus, der den gleichen Grundgedanken verfolgt, nämlich häufig vorkommenden Zeichen einen kürzeren Bit-Code zuzuweisen, ist der »Shannon-Fano-Algorithmus«. Dabei handelt es sich um eine Näherungslösung des Huffman-Algorithmus. Auch hier dient ein Baum zur Code-Entwicklung, allerdings wird der Baum von der Wurzel aus erzeugt. Eine nach der Häufigkeit sortierte Liste der Werte wird in zwei Bereiche aufgeteilt, wobei die Summen der Häufigkeiten beider Intervalle etwa gleich groß sein müssen. Ein neu zu erzeugender Knoten zeigt mit seinem rechten und linken Zeiger auf die beiden Intervalle. Nun wendet man dieses Verfahren auf die beiden Intervalle an, bis die Intervallgröße Eins beträgt, also bei einem einzelnen Wert angekommen ist.
Warum das Shannon-Fano-Verfahren nur eine Näherung ist, verdeutlichen Bild 1 und 2. Wie man sieht, erlaubt das Shannon-Fano-Verfahren keine Überkreuz-Verbindungen, die unter bestimmten Voraussetzungen geeignetere Code-Längen erzeugen würden. Das »Imploding-Verfahren« von »PKZIP« benutzt zum Beispiel den Shannon-Fano-Algorithmus zum Nachkodieren von »Lempel-Ziv-Index-Werten« (mehr dazu im zweiten Teil des Artikels). Allerdings paßt man hier die Intervallgrößen so an, daß die kodierten Werte die Länge von 16 Bit nicht übersteigen. Damit lassen sich dann alle Codes in 16-Bit Integer-Variablen mit einem weiteren Bit-Zähler halten, was die Kodiergeschwindigkeit deutlich anhebt, aber der Komprimierrate nur wenig abträglich ist. Mit den Rechenkapazitäten heutiger Computer kann es sich praktisch kein professioneller Packer mehr leisten, seine komprimierten Daten nicht mit dem Huffman- oder Shannon-Fano-Verfahren nachzukodieren. So wandte »LHarc« bis zur Version 2.0 einen statischen Huffman-Code zur Nachbearbeitung an und ab der Version 2.0 einen adaptiven Huffman-Code, der sich nach je 4000 Werten neu aufbaut. Das »Squeeze-Verfahren« älterer »ARC«-Packer ist ein mit dem Huffman-Code nachbehandelter Lauflängenkodierer.
Im nächsten Teil, der ausführlich die verschiedenen Implementationen des Lempel-Ziv-Algorithmus behandelt, befinden sich dann noch einige Bibliotheksfunktionen mit Quelltext für Pure C auf der TOS-Diskette. (ah)
Jürgen Lietzow