Huffmanin koodaus

Huffmanin koodaus on tietotekniikassa tiedonpakkaukseen käytettävä algoritmi.

Tyypillisesti tietokone esittää jokaisen merkin samanpituisena bittijonona, vaikkapa 'a'=00, 'b'=01, 'c'=10 ja 'd'=11. Jos merkkien esiintymistiheys vaihtelee, voidaan tietoa tiivistää valitsemalla bittijonojen pituudet niin, että yleisimmät merkit vastaavat lyhimpiä bittijonoja. Tällöin tietysti harvinaisemmille merkeille tulee alkuperäistä koodausta pidemmät bittijonot. Jos 'a' olisi selvästi yleisin merkki ja 'd' toisiksi yleisin, olisi sopiva koodaus 'a'=0, 'b'=100, 'c'=101, 'd'=11.

Huffmanin koodauksessa merkkien bittiesitykset muodostetaan eräänlaisella puumallilla. Aluksi jokainen merkki on lehti, jonka arvona on merkin esiintymistiheys. Kaksi pienintä lehteä, siis kaksi harvinaisinta merkkiä, yhdistetään puuksi, jonka vasen ja oikea puoli ovat merkit ja jonka arvoksi tulee lehtien arvojen summa. Tätä jatketaan yhdistäen aina kaksi pienimmän arvon omaavaa puuta kunnes tuloksena on yksi iso puu. Nyt esimerkiksi 'c' voi löytyä juuresta lähdettäessä reittiä vasen–vasen–oikea–vasen. Merkitään vasemmalle siirtymistä ykkösellä ja oikealle siirtymistä nollalla, jolloin vastaava bittiesitys on 1101. On helppo huomata, että yleisempi merkki on 'painava' ja kestää pitkään ennen kuin se yhdistetään puuhun, ja näin sen polusta tulee lyhyempi ja bittiesityksestä myös lyhyempi.

Huffmanin koodaus on optimaalinen siinä mielessä, että mitään parempaa tapaa valita merkkien koodit kiinteästi ei ole. Yleensä parempi ja aina vähintään yhtä tehokas pakkaustapa on aritmeettinen koodaus; usein myös dynaaminen Huffmanin koodaus pakkaa datan tiiviimmin.

Tätä koodausta käytetään nykyään usein 'loppukoodauksena' joidenkin muiden pakkausmetodien jälkeen. Deflaatiossa (ZIPin algoritmi) ja multimediakoodekeissa, kuten JPEG:ssä ja MP3:ssa on usein etumalli ja kvantisointi, joita seuraa Huffman-koodaus.