Optimale koder

Gir kortest mulig gjennomsnittlig kodelengde for de gitte frekvensene.

Prefiksfri

Ingen kode er prefiks for en annen, noe som gir entydig dekoding.

Frekvensbasert

Vanlige tegn får automatisk kortere koder.

Hvordan fungerer Huffman-koding?

Huffman-koding bygger et binært tre nedenfra og opp. Med utgangspunkt i tegnfrekvenser kombineres gjentatte ganger de to nodene med lavest frekvens til en foreldrenode, til bare roten står igjen. Venstre grener representerer '0', høyre grener '1'. Tegn som forekommer oftere får kortere koder, noe som gir optimal komprimering for den gitte frekvensfordelingen.

Eksempel på Huffman-koding

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