Datenkompression: Verfahren und ihre Grenzen

Ein Text schrumpft beim Packen auf ein Drittel. Ein Foto auf ein Zwanzigstel. Eine bereits gepackte Datei dagegen wird durch nochmaliges Packen sogar größer.

Das Letzte wirkt wie ein Fehler des Programms und ist keiner. Es ist beweisbar unvermeidlich, und der Beweis dafür passt in wenige Zeilen.

In diesem Kapitel geht es um die Frage, woher die Einsparung eigentlich kommt, um zwei konkrete Verfahren und um die Grenze, an der jedes Verfahren haltmacht.

Vorausgesetzt wird aus Datenkompression: verlustfrei und verlustbehaftet die Unterscheidung beider Arten und die Grundidee, Wiederholungen auszunutzen.

Neu sind hier die Verfahren selbst, ihre Begründung und ihre beweisbare Grenze.

Kompression ist keine Zauberei. Sie beruht auf einer einzigen Beobachtung:

Reale Daten sind nicht zufällig. Sie enthalten Wiederholungen, Muster und ungleich häufige Zeichen, kurz: Redundanz.

Beispiele:

• In deutschem Text kommt das $\texttt{e}$ etwa hundertmal so oft vor wie das $\texttt{q}$.
• In einem Foto sind benachbarte Bildpunkte fast immer ähnlich.
• In einer Tabelle wiederholen sich Werte.

Kompression ersetzt Redundanz durch eine kürzere Beschreibung. Wo keine Redundanz ist, gibt es nichts einzusparen, und genau darauf läuft die Grenze am Ende dieses Kapitels hinaus.

🔴 Die Wahl ist keine Geschmacksfrage. Bei einem Programm ändert ein einziges gekipptes Bit möglicherweise einen Befehl; die Datei ist unbrauchbar. Bei einem Foto ist ein minimal verschobener Farbton für das Auge unsichtbar.

Die Leitfrage lautet: Ist eine Abweichung wahrnehmbar oder folgenlos? Bei Texten, Programmen und Messwerten nein. Dort ist nur verlustfrei zulässig. Bei Bild, Ton und Video ja, dort nutzt man aus, dass die menschliche Wahrnehmung ohnehin nicht alles erfasst.

Verlustbehaftete Verfahren lassen deshalb gezielt weg, was kaum wahrgenommen wird: Bei MP3 sind das Töne, die von lauteren überdeckt werden, bei JPEG feine Helligkeitsunterschiede, die das Auge nicht auflöst.

Das einfachste Verfahren. Statt jedes Zeichen einzeln zu speichern, notiert man Zeichen und Anzahl:

AAAAAAABBBCCCCCCCCCC   (20 Zeichen)
→  7A 3B 10C           (6 Zeichen)

Die Kompressionsrate ist hier

$$\frac{20}{6} \approx 3{,}3$$

Wo es gut funktioniert: Bei Bildern mit großen einfarbigen Flächen, etwa Symbolen, Zeichnungen oder gescannten Schwarz-Weiß-Seiten. Bei einem Faxbild bestehen ganze Zeilen aus Weiß.

🔴 Wo es scheitert: bei Daten ohne Wiederholungen.

ABCDEFGH             (8 Zeichen)
→  1A 1B 1C 1D 1E 1F 1G 1H   (16 Zeichen)

Die „komprimierte" Fassung ist doppelt so groß. Das ist kein Einzelfall, sondern ein erster Hinweis auf die allgemeine Grenze am Ende des Kapitels.

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Die Lauflängencodierung nutzt nur Wiederholungen nebeneinander. Häufigkeiten nutzt sie gar nicht.

Die Idee der Huffman-Codierung ist deshalb eine andere:

Häufige Zeichen bekommen kurze Codes, seltene lange.

Das ist derselbe Gedanke wie beim Morsealphabet, wo das häufige $\texttt{E}$ ein einzelner Punkt ist und das seltene $\texttt{Q}$ vier Zeichen braucht.

Aufbau des Codes für den Text $\texttt{ABRACADABRA}$ (11 Zeichen):

Häufigkeiten: $\texttt{A}$: 5, $\texttt{B}$: 2, $\texttt{R}$: 2, $\texttt{C}$: 1, $\texttt{D}$: 1.

Schritt 1: Für jedes Zeichen einen Knoten mit seiner Häufigkeit anlegen. Schritt 2: Die beiden kleinsten zusammenfassen; der neue Knoten trägt die Summe. Schritt 3: Wiederholen, bis nur ein Knoten übrig ist. Schritt 4: Von der Wurzel aus jeder linken Kante eine 0 und jeder rechten eine 1 zuordnen; der Code eines Zeichens ist der Weg zu ihm.

                (11)
              /      \
          A(5)       (6)
                    /    \
                 (2)      (4)
                /   \    /   \
             C(1)  D(1) B(2) R(2)

Daraus:

Gesamtlänge: $5 \cdot 1 + 1 \cdot 3 + 1 \cdot 3 + 2 \cdot 3 + 2 \cdot 3 = 23$ Bit.

Zum Vergleich: Mit fester Länge bräuchte man bei fünf verschiedenen Zeichen 3 Bit je Zeichen, also $11 \cdot 3 = 33$ Bit. Die Einsparung beträgt rund 30 %.

Warum das eindeutig decodierbar ist. Die Codes haben verschiedene Längen, und trotzdem braucht man keine Trennzeichen. Der Grund ist die Baumkonstruktion: Alle Zeichen sitzen in den Blättern, nie in inneren Knoten. Deshalb ist kein Code der Anfang eines anderen; man nennt das präfixfrei.

Beim Decodieren läuft man vom Wurzelknoten aus die Bits entlang und gibt ein Zeichen aus, sobald man ein Blatt erreicht. Dann beginnt man wieder an der Wurzel. Eine Verwechslung ist ausgeschlossen.

Prüfe es an $\texttt{0110}$: Die 0 führt sofort zum Blatt $\texttt{A}$. Zurück zur Wurzel, dann $1 \to 1 \to 0$ führt zu $\texttt{B}$. Also $\texttt{AB}$, und eine andere Lesart gibt es nicht.

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Nun zu der Beobachtung aus der Einleitung. Man könnte sich ein Verfahren wünschen, das jede Datei verkleinert. Ein solches kann es nicht geben, und der Beweis ist elementar.

Annahme: Ein verlustfreies Verfahren verkleinere jede Datei um mindestens ein Bit.

Schritt 1: Betrachte alle Dateien der Länge $n$ Bit. Davon gibt es $2^n$.

Schritt 2: Nach Annahme wird jede auf höchstens $n-1$ Bit abgebildet. Dateien mit höchstens $n-1$ Bit gibt es aber nur

$$2^{n-1} + 2^{n-2} + \ldots + 2^1 + 2^0 = 2^n - 1$$

Schritt 3: Es sollen also $2^n$ Dateien auf $2^n - 1$ mögliche Ergebnisse abgebildet werden. Nach dem Schubfachprinzip müssen zwei verschiedene Dateien dasselbe Ergebnis liefern.

Schritt 4: Dann kann das Entpacken nicht mehr entscheiden, welche der beiden gemeint war. Das Verfahren ist nicht verlustfrei.

Widerspruch. Also verkleinert jedes verlustfreie Verfahren manche Dateien und vergrößert zwangsläufig andere.

🔴 Das ist keine technische Unzulänglichkeit, sondern eine Folge des Abzählens, und du erkennst dasselbe Argument wieder, das bei den Kollisionen der Streuspeicherung und beim Nachweis nichtregulärer Sprachen auftrat.

Was daraus folgt: Packprogramme funktionieren, weil reale Daten eben nicht zufällig sind. Sie sind auf Texte, Bilder und Programme zugeschnitten und verkleinern genau diese zuverlässig. Eine bereits gepackte Datei enthält kaum noch Redundanz; ein zweiter Durchgang bringt nichts und fügt nur Verwaltungsdaten hinzu. Deshalb wird sie größer.

$$\text{Rate} = \frac{\text{ursprüngliche Größe}}{\text{komprimierte Größe}}$$

Eine Rate von 4 bedeutet, dass die Datei auf ein Viertel geschrumpft ist. Manchmal gibt man stattdessen die Ersparnis in Prozent an; bei Rate 4 sind das 75 %.

Bei verlustbehafteten Verfahren ist die Rate einstellbar: Man wählt zwischen Größe und Qualität. Ein JPEG mit hoher Rate zeigt sichtbare Blockmuster, eines mit niedriger ist kaum von der Vorlage zu unterscheiden.