Robert Sedgewick: Algorithmen

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


22. Datenkomprimierung



Bei den meisten der bisher betrachteten Algorithmen wurde vor allem das Ziel verfolgt, möglichst wenig Zeit aufzuwenden, und erst in zweiter Linie ging es darum, Platz zu sparen. Im vorliegenden Kapitel untersuchen wir einige Algorithmen mit der entgegengesetzten Zielsetzung: Methoden, die primär dazu bestimmt sind, den benötigten Platz zu reduzieren, ohne zu viel Zeit zu verbrauchen. Das Eigenartige dabei ist, daß die Techniken, die wir mit dem Ziel der Platzeinsparung betrachten werden, »Kodierungsmethoden« aus der Informationstheorie sind, die entwickelt wurden, um die in Kommunikationssystemen benötigte Informationsmenge zu minimieren, und die demzufolge ursprünglich dazu bestimmt waren, Zeit (und nicht Platz) einzusparen.

Im allgemeinen besitzen die meisten Dateien einen hohen Grad an Redundanz. Die Verfahren, die wir untersuchen werden, sparen Platz ein, indem sie die Tatsache ausnutzen, daß die meisten Dateien einen relativ geringen »Informationsgehalt« haben. Techniken zur Komprimierung (Verdichtung) von Dateien werden oft für Textdateien (in denen gewisse Zeichen wesentlich häufiger auftreten als andere), »Raster«-Dateien für die Kodierung von Bildern (die große homogene Flächen haben können) und Dateien für die digitale Darstellung von akustischen und anderen analogen Signalen (bei denen umfangreiche Wiederholungen von Mustern auftreten können) verwendet.

Wir werden einen elementaren (aber dennoch sehr nützlichen) Algorithmus für dieses Problem und eine fortgeschrittene »optimale« Methode betrachten. Die Platzeinsparung variiert bei diesen Methoden in Abhängigkeit der Dateimerkmale. Einsparungen von 20% bis 50% sind typisch für Textdateien, und für binäre Dateien können Einsparungen von 50% bis 90% erzielt werden. Bei manchen Dateitypen, zum Beispiel bei Dateien, die aus zufälligen Bits bestehen, kann nur wenig erreicht werden. Tatsächlich ist es interessant festzustellen, daß jedes beliebige Mehrzweck-Komprimierungsverfahren gewisse Dateien verlängern muß (andernfalls könnten wir das betreffende Verfahren wiederholt anwenden und dadurch eine beliebig kleine Datei erzeugen).

Einerseits könnte man vermuten, daß Datenkomprimierungstechniken weniger wichtig sind als einstmals, da sich die Kosten für Computerspeicher aller Art drastisch verringert haben und dem typischen Anwender bedeutend mehr Speicherplatz zur Verfügung steht als in der Vergangenheit. Andererseits kann man jedoch sagen, daß Datenkomprimierungstechniken eine größere Bedeutung haben als je zuvor, da die durch sie ermöglichten Einsparungen aufgrund der Tatsache, daß so viel gespeichert wird, größer sind. Komprimierungstechniken sind auch für Speichergeräte geeignet, die einen äußerst schnellen Zugriff gestatten und von Natur aus relativ teuer (und daher meist klein) sind.


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