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