| |
| |
Decodieren
|
Bei der Codierung eines Textes aus vielen Zeichen möchte man keine 'Trennzeichen' verwenden, denn die machen die codierte Nachricht länger. Wie findet man dann das Ende der Codierung eines einzelnen Zeichens?
- bei einer Codierung mit fester Länge ist das einfach: Bei ASCII-Codierung entsprechen z.B. einfach immer 8 Bit einem Zeichen.
- bei Codierung mit variabler Länge muss man darauf achten, dass die Codierung eines Zeichens und der Anfang der Codierung eines anderen Zeichens nicht die Codierung eines weiteren Zeichens sind.
 Terminologie
Im zweiten Fall hilft ein Codierungsbaum.
|
| |
 Codierungsbäume |
|
| |
 alles klar? |
|
| |
|
Mit t(z) bezeichnen wir die Tiefe des Blattes z im Codierungsbaum.
Die letzte Aufgabe hat gezeigt:
Kennt man in einem Text T die Häufigkeit h(z) eines jeden Zeichens z und dessen Tiefe t(z) im Codierungsbaum, so ist die Länge der codierten
Nachricht
|
| |
die Aufgabe
|
Wenn man für einen gegebenen Text T also eine möglichst kurze Codierung haben möchte, so muss man folgende Aufgabe lösen:
Finde einen Codierungsbaum, für den L(T) minimal ist.
Die zugehörige Codierung nennt man Huffman-Code.
|
| |
Huffman-Algorithmus
|
Und diese Aufgabe löst der folgende Algorithmus von Huffman mit einer gierigen Strategie:
Algorithmus:
erzeuge für jedes Zeichen z einen einblättrigen Codierungsbaum
und gib ihm das 'Gewicht' h(z)
füge alle diese Codierungsbäume in eine Menge M ein [Bsp.]
solange M mehr als ein Element enthält
entnehme aus M die beiden Bäume mit dem kleinsten
und zweitkleinsten Gewicht [Bsp.]
hänge diese beiden Bäume an eine neue Wurzel [Bsp.]
gib dem neuen Baum als Gewicht die Summe
der Gewichte der beiden Teilbäume
füge den Baum in M ein [Bsp.]
|
| |
 Nach unten scrollen, bis die Schaltflächen sichtbar sind
Dank |
Hier kannst du
- den Ablauf des Algorithmus beobachten
- Huffman-Codierungen für eigene oder vorgegebene
(Knopf 'Zufallstext') Texte erstellen
Wir codieren nur die 26 'kleinen' Buchstaben des Alphabets. Großschreibung wird ignoriert, Umlaute, Satz- und Sonderzeichen werden nicht codiert.
Neu entstandene Bäume werden ihrem Gewicht entsprechend einsortiert.
|
| |
