Anna und der Badestrand

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 losfahren 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 Kodierung

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: 22 = 4, also 00, 01, 10, 11). Mit drei Bits können wir acht (23 = 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-Kodierung

Anna kann sich folgendes überlegen: Buchstaben, die oft im Wort vorkommen, sollen einen kurzen Kode haben und solche, die selten vorkommen, einen langen. Das Verfahren, das wir anwenden, wird Huffman-Kodierung 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-Kodierung nicht besser als die oben beschriebene simple Kodierung.

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 Kodewort 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 Kode tatsächlich ein kürzeres Kodewort erhalten als die anderen vier Buchstaben.

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

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

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

LIEGEBETT entspricht nun

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

oder einfach

0000011001010011101111