> huffman | optimale | Codes <
// Huffman-Codierung – optimale präfixfreie Kompressionsalgorithmen
>> funktionen
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.