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
Koodit ovat prefix-free eli mikään koodi ei ole toisen koodin alkuosa, mikä mahdollistaa välittömän dekoodauksen. Huffman-koodaus
Monimutkaisuus: Puun rakentaminen vaatii prioriteettijonon avulla O(n log n) aikaa ja tilaa. Koodin hakeminen ja purku
Sovellukset: Käytetään laajalti Deflate-pakkauksissa (gzip, zlib) sekä joissakin kuvaliitteissä; PNG käyttää Deflatea. Adaptiiviset Huffman-koodausversiot päivittävät koodirakenteen
Historia: David A. Huffman julkaisi menetelmän vuonna 1952 artikkelissaan "A Method for the Construction of Minimum-Redundancy