Datenkompression (Kurzvortrag)


Alle Daten bestehen aus Zeichenfolgen, alle Zeichen sind durch ein Alphabet definiert, solch ein Zeichensatz wird mit einer festen Anzahl von Bits dargestellt.

ASCII: jedem Zeichen wird eine Folge von 7 Binärzeichen zugeordnet = 128 mögl. Zeichen, pro Zeichen 7 Bit, Text mit 100.000 Zeichen verbraucht 700.000 Bits.

Weiß man das nur Texte zu komprimieren sind könnte man die Sonderzeichen weglassen. Das würde bedeuten man könnte ein kleineres Alphabet benutzen, und somit Speicherplatz sparen.

Würde man variable Wortlängen für die Binärcodes einführen könnte man häufig vorkommende Zeichen kürzere Wörter zuordnen.

'nicemississippi'

Normalerweise -- pro Zeichen 8 Bit: 15 * 8 = 120 Bit

Verkürztes Alphabet -- pro Zeichen 3 Bit: 15 * 3 = 45 Bit

Nach Huffmann: (kürzere Codewörter für häufiger auftretene Zeichen)

Alphabet: p c m e n s i
Häufigkeit: 2 1 1 1 1 4 5
Code: 00 0100 0101 0110 0111 10 11
Binärcode: 0111|11|0100|0110|0101|11|10|10|11|10|10|11|00|00|11 = 38 Bit

Um aber eindeutige Decodierbarkeit zu gewähleisten muß jeder Code irreduzibel sein, das heißt kein Code darf mit einem anderem beginnen.

Wie aber kommt man auf die Codes?

Codebaum nach Huffman

Mit diesem Baum läßt sich die Codierung und Decodierung stark vereinfachen.

Das Codewort eines eines Zeichens wird durch den Pfad von der Wurzel des Codebbaumes zu diesem Zeichen bestimmt, und zwar mit 0 für einen Schritt nach links und 1 für einen Schritt nach rechts.

Zur Erstellung des Codebaumes werden jeweils die Zeichen mit der kleinsten Häufigkeit ( größten Auftrittswarsch. ) miteinander verbunden. Der nun entstandene Knoten trägt die Summe der beiden Häufigkeiten und tritt nun an die Stelle der beiden Buchstaben( er wird weiterhin wie ein Zeichen mit der neuen Häufigkeit behandelt ). Das Alphabet ist also um ein Zeichen reduziert. Dieser Vorgang wird wiederholt bis das Alphabet nur noch aus einem Zeichen, der Wurzel, besteht.

Bei Texten kann man natürlich auch ganze Wörter Codieren

Die Leistung dieser Methode ist um so größer, je größer der Quotient aus Datenlänge und Alphabetlänge ist.

Nachteile:

Der Baum muß mitgespeichert werden.Das heißt, die codierte Datei kann größer sein als die Ausgangsdatei.


Der Kurzvortragshalter... :-)