🌳 Huffman-Codierung

Die Standardimplementierung nutzt einen Min-Heap (Prioritätswarteschlange), der nach Knotenhäufigkeit sortiert ist. Jede der n Verschmelzungsoperationen kostet O(log n) für Heap-Einfügung und -Extraktion, was eine Gesamtkonstruktionszeit von O(n log n) ergibt. Für ein 256-Symbol-Alphabet ist dies in der Praxis effektiv konstant.

Huffman weist eine ganzzahlige Anzahl von Bits pro Symbol zu, kann also für Symbole mit sehr hoher Wahrscheinlichkeit nicht besser als ein Bit pro Symbol sein. Arithmetische Codierung codiert ganze Nachrichten als einzelnen Bruch und erreicht erwartete Längen, die beliebig nahe an der Entropie liegen, selbst wenn einzelne Symbolwahrscheinlichkeiten 0,5 übersteigen. Arithmetische Codierung ist jedoch rechenintensiver und historisch patentrechtlichen Beschränkungen unterworfen.

Ja. DEFLATE — der Kompressionskern in ZIP, gzip und PNG — kombiniert LZ77-Zeichenkettenabgleich mit Huffman-Codierung. JPEG nutzt Huffman- (oder optional arithmetische) Codierung nach seinem DCT-Quantisierungsschritt. Auch das ältere PKZIP-Format und der Brotli-Webkompressionsalgorithmus bauen auf Huffman-Familienschemata auf.

Gleichstände werden willkürlich aufgelöst; verschiedene Auflösungsstrategien erzeugen unterschiedliche Baumformen, erreichen aber immer dieselbe optimale erwartete Codelänge. In der Praxis geben stabile oder kanonische Huffman-Implementierungen eine deterministische Regel zur Auflösung von Gleichständen vor, sodass Encoder und Decoder denselben Baum aus einem kompakten Header rekonstruieren können.

Ein kanonischer Code weist Codewörter so neu zu, dass Codes gleicher Länge aufeinanderfolgende ganze Zahlen sind, wodurch der Decoder nur die Codelängen statt des gesamten Baums speichern muss. Dies reduziert den Header-Overhead drastisch: Statt den Baum zu serialisieren, überträgt der Kompressor nur die Symbollängen, was Kilobytes in Formaten wie der zlib-Schicht von PNG spart.

Nur wenn die Quelle eine sehr niedrige Entropie hat — zum Beispiel eine Binärdatei, die fast ausschließlich einen einzigen Byte-Wert enthält. In diesem Extremfall könnte der Huffman-Code für dieses Symbol 1 Bit betragen, was eine Reduktion um bis zu das 8-Fache gegenüber 8-Bit-ASCII ergibt. Bei natürlichem englischem Text liegen die Kompressionsverhältnisse mit Huffman allein typischerweise beim 1,5- bis 2,5-Fachen.

Adaptive Huffman-Codierung aktualisiert die Häufigkeitstabelle und baut den Baum bei jedem verarbeiteten Symbol neu auf (oder passt ihn schrittweise an), wodurch ein Zwei-Durchgang-Algorithmus oder ein gespeicherter Header überflüssig wird. Die Algorithmen FGK und Vitter erhalten die Geschwister-Eigenschaft, um inkrementelle Aktualisierungen mit O(log n) zu ermöglichen, was Einzeldurchgang-Streaming-Kompression erlaubt.