Wie die Dateikomprimierung funktioniert

In unserem vorherigen Beispiel haben wir alle sich wiederholenden Wörter herausgesucht und diese in ein Wörterbuch aufgenommen. Für uns ist das die offensichtlichste Art, ein Wörterbuch zu schreiben. Aber ein Komprimierungsprogramm sieht das ganz anders: Es hat kein Konzept von einzelnen Wörtern – es sucht nur nach Mustern. Und um die Dateigröße so weit wie möglich zu reduzieren, wählt es sorgfältig aus, welche Muster es in das Wörterbuch aufnimmt.

Wenn wir uns dem Satz aus dieser Perspektive nähern, erhalten wir ein völlig anderes Wörterbuch.

Wenn das Kompressionsprogramm Kennedys Satz scannen würde, wäre die erste Redundanz, auf die es stoßen würde, nur ein paar Buchstaben lang. In „ask not what your“ gibt es ein sich wiederholendes Muster des Buchstaben „t“, gefolgt von einem Leerzeichen – in „not“ und „what“. Wenn das Komprimierungsprogramm dies in das Wörterbuch schreiben würde, könnte es jedes Mal eine „1“ schreiben, wenn ein „t“ von einem Leerzeichen gefolgt würde. Aber in diesem kurzen Satz kommt dieses Muster nicht oft genug vor, um es zu einem lohnenden Eintrag zu machen, also würde das Programm es schließlich überschreiben.

Das nächste, was dem Programm auffallen könnte, ist „ou“, das sowohl in „your“ als auch in „country“ vorkommt. Wäre dies ein längeres Dokument, könnte das Schreiben dieses Musters in das Wörterbuch eine Menge Platz sparen – „ou“ ist eine ziemlich häufige Kombination in der englischen Sprache. Aber als das Komprimierungsprogramm diesen Satz durcharbeitete, würde es schnell eine bessere Wahl für einen Wörterbucheintrag entdecken: Nicht nur „ou“ wird wiederholt, sondern die ganzen Wörter „your“ und „country“ werden beide wiederholt, und sie werden sogar zusammen wiederholt, als die Phrase „your country“. In diesem Fall würde das Programm den Wörterbucheintrag für „ou“ mit dem Eintrag für „your country“ überschreiben.

Die Phrase „can do for“ wird ebenfalls wiederholt, einmal gefolgt von „your“ und einmal gefolgt von „you“, was uns ein wiederholtes Muster von „can do for you“ gibt. Dies lässt uns 15 Zeichen (einschließlich Leerzeichen) mit einem Zahlenwert schreiben, während wir für „Ihr Land“ nur 13 Zeichen (mit Leerzeichen) mit einem Zahlenwert schreiben können, so dass das Programm den Eintrag „Ihr Land“ einfach mit „r Land“ überschreiben und dann einen separaten Eintrag für „kann für Sie tun“ schreiben würde. Das Programm geht auf diese Weise vor, nimmt alle sich wiederholenden Informationen auf und berechnet dann, welche Muster es in das Wörterbuch schreiben soll. Diese Fähigkeit, das Wörterbuch neu zu schreiben, ist der „adaptive“ Teil des adaptiven wörterbuchbasierten LZ-Algorithmus. Die Art und Weise, wie ein Programm dies tatsächlich tut, ist ziemlich kompliziert, wie Sie aus den Diskussionen auf Data-Compression.com ersehen können.

Unabhängig davon, welche spezifische Methode Sie verwenden, können Sie mit diesem tiefgreifenden Suchsystem die Datei viel effizienter komprimieren, als wenn Sie nur Wörter herauspicken würden. Mit den Mustern, die wir oben herausgesucht haben, und dem Hinzufügen von „__“ für Leerzeichen, erhalten wir dieses größere Wörterbuch:

Und dieser kleinere Satz: „1not__2345__–__12354“

Der Satz belegt jetzt 18 Speichereinheiten, und unser Wörterbuch nimmt 41 Einheiten ein. Wir haben also die Gesamtgröße der Datei von 79 Einheiten auf 59 Einheiten komprimiert! Dies ist nur eine Möglichkeit, den Satz zu komprimieren, und nicht unbedingt die effizienteste. (Versuchen Sie, einen besseren Weg zu finden!)

Wie gut ist also dieses System? Die Dateireduktionsrate hängt von einer Reihe von Faktoren ab, darunter Dateityp, Dateigröße und Komprimierungsschema.

In den meisten Sprachen der Welt kommen bestimmte Buchstaben und Wörter oft in demselben Muster zusammen vor. Aufgrund dieser hohen Redundanzrate lassen sich Textdateien sehr gut komprimieren. Eine Reduktion von 50 Prozent oder mehr ist typisch für eine Textdatei guter Größe. Die meisten Programmiersprachen sind ebenfalls sehr redundant, weil sie eine relativ kleine Sammlung von Befehlen verwenden, die häufig in einem bestimmten Muster zusammenkommen. Dateien, die viele einzigartige Informationen enthalten, wie z. B. Grafiken oder MP3-Dateien, können mit diesem System nicht viel komprimiert werden, da sie nicht viele Muster wiederholen (mehr dazu im nächsten Abschnitt).

Wenn eine Datei viele sich wiederholende Muster hat, steigt die Reduktionsrate typischerweise mit der Dateigröße. Sie können das an unserem Beispiel sehen – wenn wir mehr von Kennedys Rede hätten, könnten wir häufiger auf die Muster in unserem Wörterbuch verweisen und so mehr aus dem Speicherplatz jedes Eintrags herausholen. Außerdem könnten in längeren Arbeiten mehr durchdringende Muster auftauchen, was uns erlaubt, ein effizienteres Wörterbuch zu erstellen.

Diese Effizienz hängt auch von dem spezifischen Algorithmus ab, den das Kompressionsprogramm verwendet. Einige Programme sind besonders geeignet, um Muster in bestimmten Dateitypen aufzuspüren, und komprimieren sie daher möglicherweise prägnanter. Andere haben Wörterbücher innerhalb von Wörterbüchern, die vielleicht größere Dateien effizient komprimieren, kleinere jedoch nicht. Während alle Kompressionsprogramme dieser Art mit der gleichen Grundidee arbeiten, gibt es tatsächlich eine Menge Variationen in der Art der Ausführung. Programmierer versuchen immer, ein besseres System zu bauen.