29.
Datenkompression 29.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 (vgl. dazu 21.2 ASCII-Code, und
22 Datenströme) 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 codiert 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: entsprechend lassen sich die
BinärKodes der restlichen Buchstaben I, S und P finden. (Aufgabe) 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.
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 | 29.2 Huffman-Algorithmus |
zur Startseite | www.pohlig.de (C) 2004 MPohlig |