Eine Übung

Anna möchte an den Badestrand gehen. Dafür möchte sie vier Gegenstände mitnehmen: Eine Luftmatraze, einen Wasserball, ein Badetuch und ihr Bikini. In ihrem Zimmer legt sie alles auf einen Haufen. Sie merkt, dass der Haufen richtig gross geworden ist und dass sie diese Gegenstände niemals auf ihrem Velo transportieren kann. Irgendwie muss sie nun das Volumen reduzieren!

Komprimierung

Sie stopft als erstes ihr Badetuch und den Bikini in den Rucksack. Diese Dinge braucht sie ja unbedingt, hier ist nichts reduzierbar. Beim Wasserball und bei der Luftmatraze allerdings schon: Sie lässt die Luft ab, und die beiden Dinge passen nun auch in den Rucksack. Nun kann Anna endlich los fahren und baden gehen.

Am See angekommen, kann Anna den Ball und die Luftmatraze wieder aufpumpen. Die Gegenstände haben nun wieder ihre ursprüngliche Form.

Was Anna hier gemacht hat, nennt man "Komprimieren".

In der Informatik werden häufig grössere Datenmengen über ein Kabel transportiert. Dabei möchte man die Datenmenge so gering wie möglich halten, damit die Übertragung schneller geht. Vor dem Versand komprimiert man also die Daten: Man lässt sozusagen die Luft heraus, um sie am anderen Ende der Leitung wieder hineinzupumpen, so dass sich die Daten wieder in ihrer ursprünglichen Form präsentieren.

Komprimierung wird sehr oft für die Übertragung und Darstellung von Musik (mp3), Bildern (JPG, GIF) oder Videos (z.B. divx) benützt.

Wie geht das konkret?

Anna möchte das Wort LIEGEBETT über das Internet an Beat schicken. Es soll möglichst wenig Platz in Anspruch nehmen. Nun kennt ein Computer keine Buchstaben - er kennt nur die Zahlen '1' und '0'.

Im Wort LIEGEBETT kommen 6 verschiedene Buchstaben vor: L, I, E, G, B und T. Diese müssen nun in '0' und '1' übersetzt werden, damit der Computer sie über das Internet übertragen kann. Der Computer macht dies normalerweise automatisch, wenn per Tastatur Buchstaben eingegeben werden. Anna möchte das aber von Hand machen.

Simple Codierung

Jeder Buchstabe wird mit drei Bits codiert. Ein Bit ist die kleinste Informationseinheit und kann entweder '0' oder '1' sein. In unserem Beispiel LIEGEBETT brauchen wir mindestens drei Bits. Mit zwei Bits können wir nähmlich nur vier verschiedene Zeichen beschreiben (zwei Bits an zwei Möglichkeiten: 2² = 4, also 00, 01, 10, 11). Mit drei Bits können wir acht (2³ = 8) verschiedene Zeichen darstellen, wir brauchen aber nur sechs. 110 und 111 verwenden wir nicht.

L --> 000
I --> 001
E --> 010
G --> 011
B --> 100
T --> 101

Somit entspricht LIEGEBETT dem Code

    000|001|010|011|010|100|010|101|101

oder einfach

    000001010011010100010101101.

Es werden also insgesamt 9x3 = 27 Bits benötigt.

Zum Entschlüsseln auf der anderen Seite braucht Beat die genaue Zuordnung von Buchstaben zu Codewörtern. Hat er die von Anna bekommen, so kann er nun aus der langen Bitreihe von links her Dreiergruppen bilden und die einzelnen Buchstaben entschlüsseln.

Nun haben wir das Wort aber erst für den Computer in Nullen und Einsen übersetzt, jedoch noch nicht komprimiert. Irgendwie muss Anna nun, wie bei der Luftmatratze, Luft rauslassen.

Die Huffman-Codierung

Anna kann sich folgendes überlegen: Buchstaben, die oft im Wort vorkommen, sollen einen kurzen Code haben und solche, die selten vorkommen, einen langen. Das Verfahren, das wir anwenden, wird Huffman-Codierung genannt.

Es funktioniert vor allem dann gut, wenn es gewisse Buchstaben gibt, die viel häufiger als andere vorkommen. Wenn alle Buchstaben gleich häufig vorkommen, ist die Huffman-Codierung nicht besser als die oben beschriebene simple Codierung.

Als erstes erstellen wir eine Tabelle mit den Häufigkeiten der Buchstaben:

L: 1 Mal
I: 1 Mal
E: 3 Mal
G: 1 Mal
B: 1 Mal
T: 2 Mal

Das Vorgehen ist nun folgendes:

Die beiden Buchstaben mit der geringsten Häufigkeit werden immer miteinander verbunden. Der entstandene Punkt erhält als Häufigkeit die Summe der beiden Buchstaben. Dies wird nun so oft wiederholt, bis nur noch ein Punkt übrig bleibt. Haben mehrere Punkte die gleiche Häufigkeit, so können zwei beliebige Punkte gewählt werden (im Beipiel werden immer zuerst die linken genommen):

Es entsteht ein Baum. Um das Codewort für einen Buchstaben abzulesen, geht man von der "Wurzel" (zuoberst am Baum) nach unten. Eine Kante nach links bedeutet eine '0', eine nach rechts eine '1'.

L --> 000
I --> 001
E --> 10
G --> 010
B --> 011
T --> 11

Betrachten wir nochmals die Häufigkeiten, so sehen wir, dass 'E' und 'T' am Häufigsten vorkommen (3 bzw. 2 Mal). Beide haben nun bei unserem Code tatsächlich ein kürzeres Codewort erhalten als die anderen vier Buchstaben.

Nun wollen wir die Anzahl Bits berechnen, die mit den neuen Codewörtern benötigt werden:

(Häufigkeit)x(Länge des Codes)
(L)1x3 + (I) 1x3 + (E) 3x2 + (G) 1x3 + (B) 1x3 + (T) 2x2 = 22

Mit der Huffman-Codierung braucht unser Text also nur noch 22 anstelle der 27 Bits mit der simplen Codierung!

LIEGEBETT entspricht nun

000|001|10|010|10|011|10|11|11

oder einfach

0000011001010011101111

Entschlüsselung

Beat bekommt nun also diese Reihe von Nullen und Einsen. Damit er diese entschlüsseln kann, muss er wieder die Codierung der Buchstaben kennen. Anna muss ihm diese irgendwie mitteilen, damit er den oben beschriebenen Baum aufzeichnen kann. Da die Codewörter nun nicht mehr alle drei Buchstaben lang sind, kann er nicht mehr einfach drei Bits zusammenfassen wie vorher beim simplen Code.

Er geht so vor:

Er nimmt den Huffman-Baum zu diesem Codewort und beginnt bei der "Wurzel". Schickt ihm Anna eine '0', so geht er nach links, schickt sie ihm eine '1', so geht er nach rechts. Das macht er solange bis er zu einem Buchstaben kommt. Dann Beginnt er wieder bei der Wurzel.

Bei unserem Beispiel geht er dreimal nach links (da nur Nullen kommen) und kommt zu 'L'. Dann beginnt er wieder oben, geht zweimal nach links (zwei Nullen) und einmal nach rechts (eine Eins) und kommt zu 'I', usw.

Könnte man das Wort noch weiter komprimieren?

Nein! Man kann beweisen, dass der Huffman-Code optimal ist. Das heisst, es gibt keinen anderen Code, der weniger Bits braucht. Der Beweis ist nicht ganz so einfach. Interessierte können mal mit Google suchen...
Der Huffman-Code ist nur für die jeweils zugrunde liegenden Daten optimal. Der Code, den wir berechnet haben, funktioniert also nur für das Wort LIEGEBETT. Wollen wir ein anderes Wort komprimieren, so muss der Code wieder neu berechnet werden.

Probiers an einem anderen Beispiel aus!

Klicke im Menu links auf selber ausprobieren

Weitere Informationen gibt es zum Beispiel hier.