| |
| |
|
Im Algorithmus von Huffman wird die Menge M ständig verändert:
- Am Anfang besteht M aus den Zeichen des vorgegebenen Zeichensatzes Z.
- Die Elemente von M sind immer Bäume, deren Blätter die Zeichen aus Z sind.
- Das Gewicht eines jeden solchen Elements von M ist die Summe der Gewichte seiner Blätter.
|
| |
Begriffe
|
- Einen Codierungsbaum für den vorgegebenen Zeichensatz Z bezeichnen wir mit T(Z).
- Wir sprechen von einem Codierungsbaum für M, notiert als T(M), wenn wir jedes Element von M - dieses Element ist selbst ein Baum - als neues 'Zeichen' mit dem entsprechenden Gewicht auffassen.
- Zentral ist: Jeder Codierungsbaum T(M) induziert einen Codierungsbaum T(Z). Nämlich einfach dadurch, dass wir die Elemente von M als Bäume mit Blättern aus Z ansehen.
|
| |
Begründungen erhältst du, wenn du mit der Maus über die Zusicherung fährst.
|
Jetzt weisen wir nach, dass der Huffman-Algorithmus tatsächlich einen optimalen Codierungsbaum bestimmt. Dazu fügen wir in geschweiften Klammern { }  Zusicherungen in den Algorithmus ein.
|
| |
