> huffman | optimale | codes <
// Huffman-codering - optimale prefixvrije compressie-algoritme
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.
>> technische info
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
Waarom Huffman-codering gebruiken?:
- ▸Bijna optimale compressieverhouding
- ▸Eenvoudige implementatie
- ▸Basis van ZIP/JPEG-compressie
- ▸Geen gegevensverlies
- ▸Bewezen efficiëntie in de praktijk
>> veelgestelde vragen
Wat is Huffman-codering?
Huffman-codering is een optimaal, prefixvrij compressie-algoritme dat in 1952 door David A. Huffman werd voorgesteld. Het kent tekens codes met variabele lengte toe op basis van hun frequentie; frequenter voorkomende tekens krijgen kortere codes, waardoor de gemiddelde codelengte minimaal wordt.
Waarom heet het prefixvrij?
Een code is prefixvrij wanneer geen enkel codewoord het prefix is van een ander codewoord. Als 'A' bijvoorbeeld de code '01' heeft, mag geen ander teken een code hebben die met '01' begint. Zo kan de binaire stroom zonder scheidingstekens eenduidig worden gedecodeerd.
Hoe efficiënt is Huffman-codering?
Huffman-codering bereikt voor een gegeven frequentieverdeling de optimale compressie en ligt meestal binnen 1 bit van de theoretische entropiegrens. Voor Engelse tekst wordt vaak een compressie van 60–70% gehaald, vooral wanneer de tekenfrequenties sterk variëren.
Waar wordt Huffman-codering gebruikt?
Huffman-codering wordt gebruikt in JPEG-afbeeldingscompressie, ZIP-bestandscompressie (samen met LZ77 in DEFLATE), MP3-audio en vele andere formaten. Vaak wordt het gecombineerd met andere algoritmen; zo gebruikt JPEG Huffman na DCT en kwantisatie, terwijl ZIP het toepast na LZ77.
// Uitgewerkt voorbeeld
| Symbol | Freq | Bits | Code |
|---|---|---|---|
| A | 4 | 1 | 0 |
| B | 2 | 2 | 10 |
| C | 1 | 2 | 11 |
// Codevoorbeelden
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
>> Meer vragen
V: Is de Huffman-code uniek?
A: Niet per se. Bij gelijke frequenties kunnen de keuze van knopen en de toewijzing van 0 en 1 verschillen. De codelengtes en totale grootte zijn bij elke correcte Huffman-boom wel optimaal en gelijk.
V: Wat betekent prefixvrij?
A: Geen enkel codewoord is het begin van een ander. De bitstroom is daardoor zonder scheidingstekens te decoderen: volg de bits vanaf de wortel tot een blad.
V: Wanneer is Huffman niet optimaal?
A: Het kent een geheel aantal bits per symbool toe. Bij zeer ongelijke kansen (bv. 0,99) gaat efficiëntie verloren; rekenkundig coderen komt dichter bij de entropie. De decoder heeft ook de codetabel nodig.