Datenkompression: verlustfrei und verlustbehaftet

Ein unkomprimiertes Foto aus einer Handykamera belegt rund 36 Megabyte. Auf deinem Handy liegen vielleicht 3000 Fotos, und der Speicher ist trotzdem nicht voll. Irgendjemand muss also getrickst haben.

Es gibt zwei völlig verschiedene Tricks. Der eine schreibt dieselbe Information nur geschickter auf und verliert dabei nichts. Der andere wirft absichtlich etwas weg, von dem man annimmt, dass es niemandem auffällt. Beide sind richtig, aber nur für jeweils ihren Zweck, und wer sie verwechselt, zerstört Daten.

Sieh dir diese Zeichenfolge an:

$$\texttt{AAAAAAAABBBCCCCCCCCCC}$$

Das sind 21 Zeichen. Man kann dieselbe Aussage kürzer aufschreiben, indem man notiert, was wiederholt wird und wie oft:

$$\texttt{8A3B10C}$$

Das sind 7 Zeichen. Aus 21 wurden 7, also ein Drittel. Und der entscheidende Punkt: Aus $\texttt{8A3B10C}$ lässt sich die ursprüngliche Folge exakt wiederherstellen. Es ist nichts verloren gegangen, nur die Schreibweise war vorher verschwenderisch.

Dieses Verfahren heißt Lauflängencodierung. Es ist der einfachste Fall einer verlustfreien Kompression.

Rechnen wir gegen. Nimm die Folge $\texttt{ABCABCABC}$, ebenfalls kurz. Lauflängencodiert ergibt das:

$$\texttt{1A1B1C1A1B1C1A1B1C}$$

Aus 9 Zeichen wurden 18. Das Verfahren hat die Datei verdoppelt.

Daraus folgt eine Regel, die für jedes Kompressionsverfahren gilt: Ein Verfahren nutzt genau die Struktur aus, für die es gebaut wurde. Lauflängencodierung braucht lange Wiederholungen. Bei Bildern mit großen einfarbigen Flächen, etwa Zeichnungen oder Bildschirmfotos, funktioniert sie gut; bei einem Foto mit feinen Farbverläufen fast gar nicht.

Im ASCII-Code ist jedes Zeichen gleich lang, nämlich ein Byte. In einem deutschen Text kommt das $\texttt{e}$ aber viel häufiger vor als das $\texttt{q}$. Beiden gleich viel Platz zu geben ist Verschwendung.

Also gibt man häufigen Zeichen kurze Codes und seltenen lange. Das ist derselbe Gedanke wie beim Morsealphabet: Das häufige E ist ein einzelner Punkt, das seltene Q ist vier Zeichen lang.

Damit das eindeutig bleibt, muss eine Bedingung erfüllt sein: Kein Code darf der Anfang eines anderen sein. Wäre $\texttt{0}$ der Code für A und $\texttt{01}$ der für B, wüsste der Empfänger bei $\texttt{01}$ nicht, ob dort ein B steht oder ein A gefolgt vom Anfang eines weiteren Zeichens. Verfahren wie die Huffman-Codierung bauen genau solche Codes systematisch auf; sie lernst du in der Qualifikationsphase im Einzelnen kennen.

Diese Aussage klingt zunächst überraschend, lässt sich aber mit reinem Abzählen begründen.

Wie viele verschiedene Dateien mit 3 Bit gibt es? $2^3 = 8$. Und wie viele mit weniger als 3 Bit, also mit 1 oder 2 Bit? $2^1 + 2^2 = 2 + 4 = 6$.

Ein Kompressionsverfahren müsste jede der 8 Dateien auf eine der 6 kürzeren abbilden. Das geht nicht ohne Doppelbelegung: Mindestens zwei verschiedene Ausgangsdateien bekämen dasselbe Ergebnis. Beim Entpacken wüsste man dann nicht, welche der beiden gemeint war, und das Verfahren wäre nicht mehr verlustfrei.

Also gilt: Jedes verlustfreie Verfahren verkleinert manche Dateien und vergrößert andere. Es lohnt sich nur, weil die Dateien, die wir tatsächlich speichern, viel Struktur haben. Zufällige Bitfolgen lassen sich nicht komprimieren, und eine bereits komprimierte Datei ein zweites Mal zu packen bringt so gut wie nichts.

Bei Fotos, Musik und Videos ist die Sachlage anders. Dort muss das Ergebnis nicht Bit für Bit stimmen, sondern nur für Auge und Ohr gleich wirken.

Das nutzt die verlustbehaftete Kompression aus:

• Bei Bildern werden feine Farbunterschiede zusammengefasst, weil das Auge Helligkeitsunterschiede viel genauer wahrnimmt als Farbunterschiede.
• Bei Musik werden Töne weggelassen, die von lauteren Tönen ohnehin überdeckt werden.

Damit sind Verkleinerungen auf ein Zehntel und weniger möglich, und trotzdem sieht oder hört man kaum einen Unterschied.

Der Preis ist unumkehrbar: Das Weggelassene ist weg. Wer eine verlustbehaftet komprimierte Datei erneut speichert, verliert erneut. Nach mehreren Runden werden Kanten fleckig und Klänge blechern. Deshalb bearbeitet man Fotos in einem verlustfreien Format und speichert erst am Ende einmal verlustbehaftet.

Sie ist kurz und lässt sich immer anwenden:

Muss jedes einzelne Bit erhalten bleiben? Dann verlustfrei. Genügt es, dass es gleich wirkt? Dann darf es verlustbehaftet sein.

Bei einem Programm, einem Text, einer Tabelle oder einer Messreihe ist ein einziges falsches Bit ein Fehler. Bei einem Urlaubsfoto ist ein minimal anderer Blauton keiner.