Optimale koder

Genererer den kortest mulige gennemsnitlige kodelængde for de givne frekvenser.

Præfiksfri

Ingen kode er præfiks for en anden, så dekodning er entydig.

Frekvensbaseret

Hyppige tegn får automatisk kortere koder.

Hvordan fungerer Huffman-kodning?

Huffman-kodning bygger et binært træ nedefra og op. Ud fra tegnfrekvenser kombineres de to noder med lavest frekvens gentagne gange til en forælder, indtil kun roden er tilbage. Venstre gren repræsenterer '0' og højre '1'. Tegn med højere frekvens får kortere koder, hvilket giver optimal komprimering for den givne fordeling.

Eksempel på Huffman-kodning

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