Optimale codes

Genereert de kortst mogelijke gemiddelde codelengte voor de gegeven frequenties.

Prefixvrij

Geen enkele code is een prefix van een andere, wat eenduidige decodering mogelijk maakt.

Frequentiegebaseerd

Veelvoorkomende tekens krijgen automatisch kortere codes.

Hoe werkt Huffman-codering?

Huffman-codering bouwt een binaire boom van onder naar boven. Vanuit de tekenfrequenties worden steeds de twee knopen met de laagste frequentie samengevoegd tot een ouderknoop, totdat alleen de wortel overblijft. Linker takken stellen '0' voor en rechter takken '1'. Tekens met een hogere frequentie krijgen kortere codes, waardoor een optimale compressie voor de gegeven verdeling wordt bereikt.

Voorbeeld van Huffman-codering

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