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.