> huffman | optimale | Codes <
// Huffman-Codierung – optimale präfixfreie Kompressionsalgorithmen
Optimale Codes
Erzeugt die kürzeste durchschnittliche Kodelänge für die gegebenen Häufigkeiten.
Präfixfrei
Kein Code ist Präfix eines anderen – damit ist die Dekodierung eindeutig.
Frequenzbasiert
Häufig vorkommende Zeichen erhalten automatisch kürzere Codes.
>> technische infos
Wie funktioniert die Huffman-Codierung?:
Die Huffman-Codierung baut einen binären Baum von unten nach oben auf. Ausgehend von den Zeichenhäufigkeiten werden wiederholt die beiden Knoten mit der geringsten Häufigkeit zu einem Elternknoten zusammengefasst, bis nur noch die Wurzel übrig bleibt. Linke Kanten stehen für '0', rechte für '1'. Zeichen mit höherer Häufigkeit bekommen kürzere Codes und erreichen so eine optimale Kompression für die gegebene Verteilung.
Beispiel für Huffman-Codierung:
Text: "AABBBCCCC"
Frequencies:
A: 2
B: 3
C: 4
Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)
Tree:
Root(9)
/ \
C(4) AB(5)
/ \
A(2) B(3)
Codes:
C: 0
A: 10
B: 11
Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000
Warum Huffman-Codierung verwenden?:
- ▸Nahezu optimale Kompressionsrate
- ▸Einfache Implementierung
- ▸Grundlage von ZIP- und JPEG-Kompression
- ▸Keine Datenverluste
- ▸Bewährte Effizienz in Praxis und Theorie
>> häufig gestellte fragen
Was ist die Huffman-Codierung?
Die Huffman-Codierung ist ein optimaler, präfixfreier Kompressionsalgorithmus, der 1952 von David A. Huffman entwickelt wurde. Er weist Zeichen variable Codelängen zu, die sich nach ihrer Häufigkeit richten – häufigere Zeichen erhalten kürzere Codes. So wird die minimal mögliche durchschnittliche Kodelänge erreicht.
Warum heißt sie präfixfrei?
Ein Code ist präfixfrei, wenn kein Codewort Präfix eines anderen ist. Wenn z. B. 'A' den Code '01' hat, darf kein anderes Zeichen mit '01' beginnen. Dadurch ist die Dekodierung eindeutig – man erkennt ohne Trenner immer, wo ein Code endet und der nächste beginnt.
Wie effizient ist Huffman-Codierung?
Die Huffman-Codierung erreicht für eine gegebene Häufigkeitsverteilung die optimale Kompression und liegt typischerweise innerhalb von 1 Bit des theoretischen Entropielimits. Für englische Texte werden oft 60–70 % Kompression erreicht, besonders dann, wenn sich die Zeichenhäufigkeiten stark unterscheiden.
Wo wird Huffman-Codierung eingesetzt?
Huffman-Codes werden in der JPEG-Bildkompression, in ZIP-Archiven (zusammen mit LZ77 in DEFLATE), in MP3-Audio und vielen anderen Formaten verwendet. Häufig wird Huffman mit anderen Verfahren kombiniert – JPEG nutzt Huffman nach DCT und Quantisierung, während ZIP es nach LZ77 einsetzt.
// Durchgerechnetes Beispiel
| Symbol | Freq | Bits | Code |
|---|---|---|---|
| A | 4 | 1 | 0 |
| B | 2 | 2 | 10 |
| C | 1 | 2 | 11 |
// Codebeispiele
Input AAAABBC (7 symbols, 56 bits as 8-bit ASCII) Counts A=4 B=2 C=1 Merge C(1)+B(2) -> node(3); node(3)+A(4) -> root(7) Codes A=0 B=10 C=11 (0/1 on left/right branches; ties may swap) Encoded 0 0 0 0 10 10 11 = 4*1 + 2*2 + 1*2 = 10 bits
>> Weitere Fragen
F: Ist der Huffman-Code eindeutig?
A: Nicht unbedingt. Bei gleichen Häufigkeiten kann die Wahl der Knoten und die Zuordnung von 0 und 1 variieren. Die Codelängen und die Gesamtlänge sind aber bei jedem korrekten Huffman-Baum optimal und gleich.
F: Was bedeutet präfixfrei?
A: Kein Codewort ist Anfang eines anderen. Dadurch lässt sich der Bitstrom ohne Trennzeichen eindeutig decodieren, indem man vom Baumwurzel aus den Bits folgt, bis ein Blatt erreicht wird.
F: Wann ist Huffman-Kodierung nicht optimal?
A: Sie vergibt ganzzahlige Bitlängen pro Symbol. Bei sehr ungleichen Wahrscheinlichkeiten (z. B. 0,99) verschenkt sie Effizienz; arithmetische Kodierung kommt näher an die Entropie heran. Der Decoder braucht außerdem die Codetabelle.