Hur Huffman bygger den optimala koden
Hamming presenterar Huffmankodning som en girig algoritm som konstruerar en prefix-fri kod med minimal genomsnittlig längd. Huvudidén: bygga trädet från botten upp, alltid sammansluta de två minst sannolika symbolerna.
Framåtpasset (Bygg)
1. Sortera alla symboler efter sannolikhet, högsta till lägsta.
2. Ta de två lägsta sannolikhetssymbolerna. Kombinera dem till en ny metasymbol med sannolikhet = summan av de två.
3. Sätt in metasymbolen på sin sorterade position.
4. Upprepa tills endast två symboler återstår.
5. Tilldela 0 och 1 till de två återstående symbolerna.
Bakåtpasset (Tilldela koder)
Ångra sammanslagningarna i omvänd ordning: vid varje uppdelning får de två symboler som sammanslagits samma prefiksbitar som deras kombinerade förälder, plus en extra 0 (ett barn) eller 1 (andra barnet). Tilldelningen av 0/1 är godtycklig — båda är giltiga.
Varför detta är optimalt: om någon annan kod hade mindre genomsnittlig längd L', skulle tillämpning av samma framåtreduktion så småningom producera två symboler med genomsnittlig längd mindre än 1 bit — omöjligt för en 2-symbolskod. Motsägelse.
Spåra algoritmen
Exempel från Hamming: fyra symboler A, B, C, D med p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
Framåtpass:
Steg 1: Sorterad: A(0,5), B(0,25), C(0,125), D(0,125). Lägsta två: C, D.
Steg 2: Sammanslå CD med p=0,25. Ny lista: A(0,5), B(0,25), CD(0,25).
Steg 3: Lägsta två: B(0,25), CD(0,25). Sammanslå BCD med p=0,5.
Steg 4: Två symboler återstår: A(0,5), BCD(0,5). Tilldela A=0, BCD=1.
Bakåtpass:
BCD → B får 10, CD får 11. CD → C får 110, D får 111.
Slutlig kod: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75 bitar.
Flera giltiga Huffmankoder
Hamming noterar två källor till icke-unikitet:
1. Godtycklig 0/1-tilldelning. Vid varje uppdelning kan du ge 0 åt antingen barn. Att byta 0 och 1 genomgående ger en annan kod med identisk L.
2. Oavgjord-bryting. När två noder har lika sannolikhet kan antingen placeras 'högre' (kombineras först). Olika oavgjord-brytningsval kan producera strukturellt olika träd — 'långa' mot 'spridda' — med samma L men olika kodlängdsfördelningar.
Höga mot spridda
Höga träd (sneda): en symbol på varje djupnivå (Fibonaccilik struktur). Kodlängder varierar kraftigt: en symbol får en kort kod, andra kaskaderar till längre koder.
Spridd träd (balanserat): symboler fördelade jämnt över djupnivåer. Kodlängder klustrar nära genomsnittet. Lägre varians.
Hammings rekommendation: när du ges ett val, föredra det spridda trädet. Samma L, men mindre varians i kodlängder → mer enhetlig avkodningstid → mindre bufferkrav i realtidsapplikationer.
Beräkning av kodlängdsvarians
Varians av kodlängder: Var = E[l²] − (E[l])²
För koden {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} med p=[0,5, 0,25, 0,125, 0,125]:
E[l] = L = 1,75
E[l²] = 0,5·1² + 0,25·2² + 0,125·3² + 0,125·3² = 0,5 + 1,0 + 1,125 + 1,125 = 3,75
Var = 3,75 − 1,75² = 3,75 − 3,0625 = 0,6875
En alternativ spridd kod för lika sannolikhetssymboler använder alla längd-2 koder: L=2, Var=0.
Kompressionvinster mot symbolfördelning
Hammings regel: Huffmankodning lönar sig endast när symbolsannolikheter skiljer sig väsentligt.
Lika sannolikheter. Om alla 2^k symboler har lika sannolikhet 1/2^k, producerar Huffman en blockkod: varje symbol får längd k. L = H = k. Ingen vinst jämfört med den enkla blockkoden.
Sneda sannolikheter. Om en symbol dominerar (p >> 1/2^k för andra), tilldelar Huffman den en mycket kort kod (längd 1 eller 2), vilket drastiskt minskar L.
Kommakoden (Hammings term). När varje sannolikhet överskrider 2/3 av återstoden, producerar Huffman naturligt: p(s1)→0, p(s2)→10, p(s3)→110, ..., ned till två koder med lika längd i slutet. Detta är en 'kommakod': det avslutande 0:an efter en körning av 1:or fungerar som ett komma.
Hamming noterar: verklig datakomprimering (säkerhetskopiering, filarkivering) kan minska lagring med mer än hälften när källan har sneda sannolikheter — engelsk text är ett främsta exempel.
Huffman mot blockkod: Numerisk jämförelse
Hammings andra exempel: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
Blockkod: 8 symboler → 3 bitar var → L_block = 3.
Hamming beräknar Huffmankoden och rapporterar L_Huffman ≈ 2,58 bitar.
Besparingar: (3 − 2,58)/3 ≈ 14% komprimering jämfört med blockkodning.
När symbolsannolikheter skiljer sig kraftigt (1/3 kontra 1/30 här, ett 10:1-förhållande), lönar sig variabellängdskodning väsentligt.
Självinitierande program
Hamming avslutar kapitel 11 med en slående idé: en Huffmanenkodar kan koda sig själv. Avkodningsträdet (som säger åt avkodaren hur den ska läsa det komprimerade meddelandet) överförs tillsammans med de komprimerade data. Mottagaren behöver ingen förkunskap om koden.
Enkodaren: samplar data, uppskattar sannolikheter, konstruerar Huffmankoden, kodar avkodningsträdet som en rubrik, kodar sedan data.
Avkodaren: läser rubriken för att rekonstruera trädet, avkodar sedan data med det.
Hammings poäng: denna hela pipeline kan köras som en biblioteksfunktion utan mänskligt inblandning. Du anropar den, den komprimerar och dekomprimerar automatiskt. Moderna arkiveringsformat (ZIP, gzip, bzip2) implementerar exakt detta mönster.
Den djupare principen: intelligensen är i algoritmen, inte i en fast kodtabell. Algoritmen anpassar sig till vilken data den än mottar. Detta är det mönster Hamming ser i alla stora ingenjörssystem: adaptabilitet inbyggd, inte skruvad på.