Math
Huffman-Code
Eine sortierte Häufigkeitswarteschlange wird zum Präfixcodebaum. Ein Symbol auswählen, seine Bits verfolgen und Verbindungen schrittweise prüfen.
Was passiert
Jeder Schritt verbindet die zwei kleinsten Gewichte. Die Zweige 0 und 1 ergeben den Code auf dem Weg von der Wurzel zum Symbol. Die Auswahl eines Buchstabens hebt diesen Weg hervor. L ist die mittlere Codelänge, H die Entropie. Huffman minimiert L unter binären Präfixcodes einzelner Symbole, auch bei L > H. Gleichheit gilt für Wahrscheinlichkeiten 2^(-k). Die Bitzahl enthält weder Codetabelle noch Dateikopf.
Gleichungen des Moduls
Gleichungen Aufbau: die beiden leichtesten Knoten verschmelzen, n−1 Mal; der Code eines Symbols ist sein Pfad von der Wurzel, links 0, rechts 1 L = Σ p(i)·l(i) (Bits pro Symbol); H = −Σ p(i)·log₂ p(i); die Codelänge l(i) ist die Tiefe des Blatts Kraft: Jeder Präfixcode hat Σ 2^(−l(i)) ≤ 1, und jeder solche Vektor ist ein Baum; Huffmans Baum ist voll, daher ist die Summe genau 1 H ≤ L < H + 1 immer; L = H genau dann, wenn jedes p(i) eine Zweierpotenz ist Die Optimalität wird gegen eine Suche über ALLE Kraft-zulässigen Längenvektoren geprüft - die Suche weiß nichts vom Algorithmus gleiche Häufigkeiten: 2(n − 2^k) Symbole erhalten den langen Code, wobei 2^k die größte Zweierpotenz unter n ist Fibonacci-Häufigkeiten 1, 1, 2, 3, 5, … ergeben den schiefsten Baum: Längen n−1, n−1, n−2, …, 1
