Huffmankoodaukseen

Huffman-koodaus on häviötön tiedonpakkausmenetelmä, joka antaa jokaiselle symbolille koodin, jonka pituus määräytyy sen esiintymistiheyden mukaan. Yleisimmille symboleille annetaan lyhyemmät koodit ja harvinaisemmille pidemmät, mikä pienentää keskimääräistä pakatun tiedon kokoa.

Perusidea on rakentaa binäärinen puu, jonka lehdet vastaavat symboleita. Prosessi: toistuvasti yhdistetään kaksi pienimmän frekvenssin symbolia tai alipuuta muodostaen uuden solmun, jonka frekvenssi on näiden summan. Kun jäljellä on juuri yksi juuripuu, jokaiselle lehden polut määritellään koodit: vasemmalle 0 ja oikealle 1.

Koodit ovat prefix-free eli mikään koodi ei ole toisen koodin alkuosa, mikä mahdollistaa välittömän dekoodauksen. Huffman-koodaus on optimaalinen odotetun koodipituuden kannalta, kun symbolien esiintymistiheydet ovat vakioita.

Monimutkaisuus: Puun rakentaminen vaatii prioriteettijonon avulla O(n log n) aikaa ja tilaa. Koodin hakeminen ja purku ovat käytännössä lineaarisia syötteen pituuden suhteen.

Sovellukset: Käytetään laajalti Deflate-pakkauksissa (gzip, zlib) sekä joissakin kuvaliitteissä; PNG käyttää Deflatea. Adaptiiviset Huffman-koodausversiot päivittävät koodirakenteen syötteen etenemisen aikana.

Historia: David A. Huffman julkaisi menetelmän vuonna 1952 artikkelissaan "A Method for the Construction of Minimum-Redundancy Codes".