Codieren und decodieren
Mit dem fertigen Baum ist Codieren ein Nachschlagen und Decodieren ein Wandern durch den Baum. Hier der Baum zu ANANASBANANE aus 7.2.1.
- Codetabelle:aus dem Baum ablesen: A 0, N 11, S 100, B 1010, E 1011.
- Codieren:Codewörter lückenlos aneinanderhängen: BANANE → 1010 0 11 0 11 1011.
- Decodieren:an der Wurzel starten, bei 0 links, bei 1 rechts; im Blatt Zeichen notieren und zurück zur Wurzel.
- Eindeutig:präfixfrei — an jeder Stelle gibt es nur eine passende Fortsetzung.
Ziehe den Lesekopf unter dem Bitstrom nach rechts — mit der Tastatur: Tab auf den Lesekopf, dann →. Der Baum zeigt den Weg des gerade gelesenen Codeworts; erreicht er ein Blatt, steht das Zeichen fest.
Halte fest: Nach jedem Blatt geht es zurück zur Wurzel. Weil kein Codewort Anfang eines anderen ist, braucht der Bitstrom keine Trennzeichen.
Wie viel gespart wird
Jedes Vorkommen eines Zeichens kostet so viele Bits, wie sein Codewort lang ist.
- Huffman:ANANASBANANE: \(5\cdot1+4\cdot2+1\cdot3+1\cdot4+1\cdot4=24\) Bit.
- Feste Länge:5 verschiedene Zeichen → 3 Bit, also \(12\cdot3=36\) Bit.
- Mittlere Länge:\(24\ \text{Bit} : 12\ \text{Zeichen}=2\) Bit je Zeichen statt 3.
- Verhältnis:\(k=\tfrac{24}{36}\approx66{,}7\,\%\) (7.1.3).
- Codetabelle:der Empfänger braucht den Baum — bei kurzen Texten kostet er mehr, als gespart wird.
Länge der Huffman-Codierung: \(L=\sum h(z)\cdot l(z)\) mit Häufigkeit \(h(z)\) und Codewortlänge \(l(z)\); mittlere Codewortlänge \(\bar l=\dfrac{L}{n}\)
Allgemeine Hinweise
Zurück zur Wurzel
Der häufigste Decodierfehler: nach einem Blatt einfach weiterlaufen. Jedes neue Codewort beginnt wieder oben.
Keine Lücken im Bitstrom
Leerzeichen zwischen Codewörtern dienen nur der Lesbarkeit. Übertragen wird 10100110111011 am Stück.
Probe mit der Formel
Die Länge des codierten Textes muss \(\sum h(z)\cdot l(z)\) ergeben. Weicht die Bitzahl ab, fehlt ein Codewort.