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?
  • Zum ersten bedeutet dies, den Algorithmus zur Lösung einer Aufgabe so zu formulieren, dass der Aufwand, d.h. die zu seiner Abarbeitung notwendige Zeit, minimiert wird.
  • Zum zweiten soll der Speicherplatz, der zur Aufnahme der Daten dient, minimiert werde, ohne dass es dabei zu einem Verlust an Daten kommt (verlustfreie Kompression).
  • Schließlich ist es wichtig, Datenübertragung möglichst kostengünstig zu machen. Hier werden neben den verlustfreien Kompressionen auch solche Verfahren verwendet, die nicht mehr verlustfrei sind, der Verlust aber in Kauf genommen werden kann. (MP3, jpg etc.)

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:
JCode.java

[berechnet zu einem Zeichen den ASCII und den Binärkode]

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:

Code(M)= B(77) = 0*128+1*64+0*32+0*16+1*8+1*4+0*2+1*1 = 01001101

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
Code(I) = 11001001
Code(S) = 01010011
Code(P) = 01010000

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) =
01001101
110010010101001101010011110010010101001101010011
11001001010100000101000011001001

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