27.
Effiziente Algorithmen und Strukturen 27.1 Datenkompression 27.1.1 Darstellung einer Zeichenkette im Binärkode
|
|
Raum und Zeit (und Geld) | Eines der
zentralen Probleme der Informatik ist die Beantwortung der Frage: Wie
optimiere ich Algorithmen und Daten?
Wir wollen uns in diesem Abschnitt mit der Kompression von Zeichenketten beschäftigen, die verlustfrei arbeitet. Dazu wollen wir uns noch einmal näher mit der Kodierung von Zeichenketten beschäftigen.
|
BinärKode von Zeichen
Download: |
Wie haben
schon früher
gesehen,
dass jedes Zeichen durch eine
Zahl (ASCII: 8 bit UniCode: 16 bit) repräsentiert wird. Der Einfachheit
halber beschränken wir uns auf die 8 bit-Darstellung , obwohl
char
in Java 16 bit tragen kann. So sind die Buchstaben M, I, S, und P durch die Zahlen 77, 73, 83, 80 kodiert Tatsächlich werden aber alle Daten
in einem BinärKode abgelegt. Um z.B. den BinärKode des Zeichens 'M'
zu erfahren, wandeln wir die Zahl 77 vom Dezimal- in den BinärKode um: Tatsächlich wird das höchste Bit nicht zum eigentlichen Kodieren benutzt. Das höchste Bit wird als Prüfbit gesetzt. Wir erinnern uns, es wird s gesetzt, dass die Anzahl der 1en in 8 Bit gerade ist. Die Kodierung der Buchstaben ist also: Code(M) =
01001101 Im folgende Applet gibt man in das linke Textfeld einen Buchstaben ein. Nach dem Drücken des Codiere-Buttons erscheint der ASCII-Kode in dezimal und in binärer Schreibweise (ohne gesetztes Prüfbit!).
Schreibt man in eine Zeichenkette das Wort MISSISSIPPI so wird dazu im Speicher des Rechners folgender BinärKode abgelegt. (Die Hervorhebung durch die Farbe dient lediglich zur leichteren Lesbarkeit, die Trennung der einzelnen Zeichen erfolgt durch Abzählen von jeweils 8 bit, der "Rechner muss also wissen" dass es sich bei dem Kode um eine Zeichenkette handelt. Code(MISSISSIPPI) =
Da jedes Zeichen (0 bzw. 1) in einem BinärKode die Datenmenge 1 bit besitzt, sind für das Wort 88 bit belegt. Wir wollen nun zeigen, wie man durch Datenkompression den Platz, den das Wort "MISSISSIPPI" im Speicher belegt stark reduzieren kann.
|
zu | 27.1.2 Huffman-Algorithmus |
zur Startseite | www.pohlig.de (C) 2006 MPohlig |