Anna und der Badestrand
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 ihren 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 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):
![Huffman Baum](/de/studium/bachelor/studienangebot/ingenieurwissenschaften/informatik/spielereien-bilder/AnnaundderBadestrand/_jcr_content/par/fullwidthimage/image.imageformat.930.165464141.jpg)
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
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.