1904519

Komprimierung: Die Mechanismen hinter ZIPs

26.08.2014 | 13:32 Uhr |

Große Daten zu schrumpfen ist ein Dauerthema in der digitalen Datenverarbeitung. ZIP, RAR und Co. erledigen den Job schon lange. Doch wie funktioniert das eigentlich?

Komprimierung findet sich überall im Alltag digitaler Datennutzung. Bewusst ist sie jedem PC-Anwender beim aktiven Einsatz eines Packprogramms wie Winzip, Winrar und 7-Zip oder auch der NTFS-internen Komprimierung unter Windows. Unbemerkt von den meisten Nutzern arbeiten aber viele Bildformate, Audioformate und Videoformate mit interner Komprimierung. Die dabei genutzten Komprimierungsmethoden unterscheiden sich stark, lassen sich aber auf einige wesentliche Basismethoden zurückführen.

Kürzen von redundanten Informationen

Packprogramme suchen in der Ausgangsdatei nach redundanten Informationen und ersetzen jede Wiederholung durch einen kürzeren Stellvertreter. So könnte etwa in einem Text, in dem mehrfach das Wort „Packprogramm“ auftritt, dieses durch „PP“ verkürzt werden. Eine 500 Mal wiederholte Bit-Folge (Buchstabe oder Farbpixel) könnte durch die einfache Angabe „500P“ abgekürzt werden. Das ist stark vereinfacht: Tatsächlich geht die digitale Komprimierung immer hinab zur Bit-Ebene. Trotzdem entspricht dies der prinzipiellen Arbeitsweise: Wenn Sie eine Textdatei, die eine Million Mal „P“ enthält, mit einem guten Packer verarbeiten, bleibt nur noch ein halbes Kilobyte übrig: Der Packer hat die extreme Redundanz erkannt und als Multiplikation codiert.

Im Normalfall werden wiederkehrende Bit-Muster durch Zeiger auf die Stelle des letzten Auftretens codiert. Die grundlegenden Algorithmen unterscheiden sich und sind je für bestimmte Datentypen spezialisiert; das Prinzip folgt aber immer noch dem bahnbrechenden Lempel-Ziv-Algorithmus LZ77 von 1977. Weiter verbessert wurde das Verfahren durch die sogenannte Entropie-Codierung: Da auch Zeiger Platz kosten, analysiert ein Packer zunächst die Häufigkeit der auftretenden Bit-Muster. Für die häufigsten Bit- Muster werden dann die kleinstmöglichen Zeiger eingesetzt, die seltensten erhalten die längsten Zeiger.

25 nützliche Packer zum Download

Während etwa Zip-Archive den genauen Originalzustand wiederherstellen, nehmen Audio- und Videokomprimierer große Signalverluste in Kauf, die bei der Analyse als irrelevant eingestuft wurden.
Vergrößern Während etwa Zip-Archive den genauen Originalzustand wiederherstellen, nehmen Audio- und Videokomprimierer große Signalverluste in Kauf, die bei der Analyse als irrelevant eingestuft wurden.

Progressive Kompression: Packprogramme wie RAR oder 7-Zip beherrschen außerdem die „progressive Kompression“ – ein Name, der über die Funktionsweise wenig aussagt: Es geht um die Fähigkeit, Redundanzen aller in einem Archiv befindlichen Dateien zu berücksichtigen. Ein gepacktes Archiv mit vielen Dateien sollte daher deutlich kleiner ausfallen als die Einzel-Archive derselben Dateien. Einfaches Windows-ZIP beherrscht diese Technik nicht, die allerdings auch einen Nachteil besitzt: Ist ein Archiv defekt, sind alle enthaltenen Dateien betroffen.
Verlustlose Kompression: Die bisher beschriebenen Methoden sind verlustlos: Aus dem komprimierten Archiv lässt sich das Original exakt rekonstruieren. Dies ist eine notwendige Voraussetzung für das Komprimieren von Binärdateien, also etwa für Programme oder Office-Dokumente, aber auch von puren Texten oder HTML-Dateien. Es gibt aber auch in anderen Bereichen verlustlose Kompression: So reduzieren die Audio- Codecs FLAC (Free Lossless Audio Codec) oder Apple Lossless ohne Signalverluste den Umfang von Wave-Audio-Daten um circa die Hälfte. Das Graphics Interchange Format (GIF) oder Portable Networks Graphics (PNG) wiederum sind verlustlose Komprimierungsstandards für Bilder.

Einstellbare Kompressionsstufen: Wie bei Audio- und Videokomprimierung lässt sich beim Bildformat JPG der Kompromiss zwischen Qualität und Datengröße frei wählen.
Vergrößern Einstellbare Kompressionsstufen: Wie bei Audio- und Videokomprimierung lässt sich beim Bildformat JPG der Kompromiss zwischen Qualität und Datengröße frei wählen.

Tilgen von irrelevanten Informationen

Komplizierter und wesentlich spezialisierter arbeiten Kompressionstechniken, die den Datenumfang dadurch verringern, dass sie irrelevante Daten entfernen. Dabei handelt es sich um verlustbehaftete Kompression: Der Vorgang ist nicht reversibel, und das Datenmaterial des Originals ist aus der komprimierten Datei nicht mehr zu rekonstruieren. Neben der Entfernung irrelevanter Daten nutzen aber fast alle Komprimierungstechniken zusätzlich die verlustfreie Redundanzbeseitigung.

Allgemein bekannte, verlustbehaftete Kompressionsformate sind etwa MP3 im Audiobereich oder DivX im Videobereich. Weniger bewusst ist vielen Nutzern, dass auch das Bildformat JPG die Datendichte unumkehrbar verringert. Alle diese spezialisierten, verlustbehafteten Methoden nutzen die Erkenntnisse der Wahrnehmungspsychologie und der Psychoakustik. Viele akustische Signale in Audiodaten und Farbabstufungen in Bilddaten nehmen Ohr und Auge gar nicht oder allenfalls nur bei bewusst analytischer Prüfung wahr.

So erweitern Sie das Packprogramm 7-Zip um weitere Formate

Beispiel JPG: Das Bildformat ist inzwischen älter als 20 Jahre und unangefochten das wichtigste Format in der Amateurfotografie und im Web. Ein erster Reduktionsschritt besteht darin, dass JPG-Bilder die Farbauflösung des Ausgangsmaterials verringern. Dies ist vor allem deshalb kaum wahrnehmbar, weil vorab die sensibleren Helligkeitswerte von den Farbwerten getrennt werden. In einem zweiten Schritt werden dann die Farben von nebeneinanderliegenden Bildpunkten vereinheitlicht. Das Ausmaß dieser Reduktion kann der Anwender selbst steuern – durch Kompressionsstufen, wie sie Bildbearbeitungen für JPG beim Speichern anbieten.

Beispiel MP3: MP3 (MPEG-2 Audio Layer III) ist der Klassiker der Audiokomprimierung und eine wesentliche Voraussetzung für den Siegeszug digitaler Musik. Das Gehör ist zwar kritischer als das Auge, andererseits hat es bekannte Schwächen: Der wahrnehmbare Frequenzbereich ist generell eingeschränkt auf etwa 20 bis 20.000 Hertz, praktisch etwa auf nur 50 bis 15 000. Ferner können leise Signale neben zeitgleichen lauten Signalen restlos gelöscht werden, weil das Ohr sie unter diesen Umständen nicht wahrnimmt. Tiefe Frequenzen kann das Ohr schlecht orten, so dass dort die Codierung auf einen Kanal (Mono) ausreicht. Neben dem Aussortieren solcher irrelevanter Signale kommt auch bei MP3 und ähnlichen Verfahren die klassische Redundanzkompression zum Zuge, etwa bei wiederholten Musikstellen. Aufgrund der notwendigen gründlichen Analyse benötigt die Audiokomprimierung mehr Zeit als die Datenkomprimierung mit einem Packer. Die verbleibende Ausgabequalität lässt sich bei MP3-Encodern wie dem Lame-Encoder in Format Factory oder CDEX vorab festlegen. Üblicherweise werden beim Rippen von CD oder beim Transcodieren aus einem anderen Format für MP3 192 KBit/s (24 KB pro Sekunde) empfohlen, um CD-ähnliche Qualität zu erzielen.

Beispiel DivX/Xvid: Für Videoformate gelten zunächst ähnliche Regeln wie bei der Bildkompression. So wird in sämtlichen Einzelbildern wie beim JPG-Bildformat die Farbauflösung reduziert. Die Analyse aufeinanderfolgender Bilder ergibt ferner eine zeitliche Redundanz: Wenn sich in Bildfolgen nur geringe Teile des Bildes ändern, können gleichbleibende Teile gelöscht werden (Bewegungskorrektur). Helligkeitsänderungen werden als relativer Wert codiert, ohne das Folgebild selbst zu übermitteln. DivX bringt mit diesen Methoden eine Film-DVD (4 GB) notfalls auf einer CD (700 MB) unter. Im Allgemeinen empfiehlt sich aber bei Video- wie bei Audiokomprimierung eine variable Bit- Rate, die meist zu höherem Platzbedarf führt: Dafür kann der Codierer hier aber von Fall zu Fall (je Frame) entscheiden, wie viel Verlust der aktuelle Frame verträgt.

Anders als beim aktiven Packen mit einer Software wie 7-Zip arbeiten Audio- und Videokomprimierer unbemerkt im Hintergrund. Die notwendige Software befindet sich in Codecs (Coder/Decoder), die das Betriebssystem und manche Player mitbringen. Fehlende Codecs führen zu mehr oder weniger eindeutigen Fehlermeldungen am Abspielgerät.

0 Kommentare zu diesem Artikel
1904519