> huffman | optimal | kodning <
// Huffman-kodning – optimal præfiksfri komprimeringsalgoritme
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.
>> teknisk info
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
Hvorfor bruge Huffman-kodning?:
- ▸Næsten optimal komprimeringsgrad
- ▸Simpel implementering
- ▸Grundlaget for ZIP/JPEG
- ▸Ingen tab af data
- ▸Dokumenteret effektivitet
>> ofte stillede spørgsmål
Hvad er Huffman-kodning?
Huffman-kodning er en optimal, præfiksfri komprimeringsalgoritme udviklet af David A. Huffman i 1952. Den tildeler variable kodelængder til tegn baseret på deres frekvens, så hyppigere tegn får kortere koder og man opnår den mindst mulige gennemsnitlige kodelængde.
Hvorfor kaldes den præfiksfri?
En kode er præfiksfri, når ingen kodeord er præfiks for et andet. Hvis f.eks. 'A' er '01', må ingen andre tegn have en kode, der starter med '01'. Denne egenskab gør dekodningen entydig – man kan altid se, hvor én kode slutter og den næste begynder uden ekstra skilletegn.
Hvor effektiv er Huffman-kodning?
Huffman-kodning opnår optimal komprimering for en given frekvensfordeling og ligger typisk inden for 1 bit af den teoretiske entropigrænse. For engelsk tekst giver den ofte 60–70 % komprimering og er mest effektiv, når tegnfrekvenserne varierer meget.
Hvor bruges Huffman-kodning?
Huffman-kodning bruges i JPEG-billedkomprimering, ZIP-filkomprimering (sammen med LZ77 i DEFLATE), MP3-lyd og mange andre formater. Den kombineres ofte med andre algoritmer – f.eks. bruger JPEG Huffman efter DCT og kvantisering, mens ZIP bruger det efter LZ77.
// Gennemregnet eksempel
| Symbol | Freq | Bits | Code |
|---|---|---|---|
| A | 4 | 1 | 0 |
| B | 2 | 2 | 10 |
| C | 1 | 2 | 11 |
// Kodeeksempler
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
>> Flere spørgsmål
S: Er Huffman-koden entydig?
S: Ikke nødvendigvis. Ved lige hyppigheder kan valget af knuder og tildelingen af 0 og 1 variere. Kodelængderne og den samlede størrelse er dog optimale og ens i ethvert korrekt Huffman-træ.
S: Hvad betyder præfiksfri?
S: Intet kodeord er begyndelsen på et andet. Bitstrømmen kan derfor afkodes uden skilletegn: følg bittene fra roden til et blad.
S: Hvornår er Huffman ikke optimal?
S: Den giver et helt antal bit pr. symbol. Ved meget skæve sandsynligheder (fx 0,99) går effektivitet tabt; aritmetisk kodning ligger tættere på entropien. Afkoderen skal også bruge kodetabellen.