Huffmanin koodaus

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

Huffmanin puun muodostaminen.

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. Harvinaisemmille merkeille tulee alkuperäistä koodausta pidemmät bittijonot. Jos 'a' olisi selvästi yleisin merkki ja 'd' toiseksi 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.^selvennä

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

Lähteet

• Moffat, Alistair: Huffman coding. ACM Computing Surveys, 2019, 52. vsk, nro 4, s. 1-35.
• Salomon, David: ”2 Huffman Coding”, A concise introduction to data compression. London: Springer, 2008. ISBN 978-1-84800-071-1. (englanniksi)

Aiheesta muualla

• Kuvia tai muita tiedostoja aiheesta Huffmanin koodaus Wikimedia Commonsissa