Huffmankodning

Huffmankodning är en förlustfri data­komprimeringsalgoritm som uppfanns av David A. Huffman 1952. Den tilldelar variabel längdkoder till symboler i en ström baserat på deras frekvens, så att vanliga symboler får kortare koder än sällsynta.

Algoritmen bygger en prefixkod, vilket innebär att ingen kod är prefix till en annan. Detta gör avkodningen entydig utan avgränsare. Frekvenser räknas upp och ett binärt träd byggs där de minst frekventa noderna slås ihop tills endast en nod återstår.

Koderna erhålls genom att gå från roten till löven; vänster ger 0 och höger ger 1. Den resulterande koden är optimal för en given sannolikhetsfördelning i den meningen att den genomsnittliga kodlängden är minimal bland prefixkoder.

Det finns statisk Huffmankodning där koderna fastställs för en hel datablock samt adaptiv eller dynamisk Huffmankodning som uppdaterar koderna under kodningen (t.ex. FGK- eller Vitter-algoritmer). Användningar återfinns i DEFLATE (gzip/zlib) och i PNG:s komprimering.

Komplexitet: att bygga trädet kräver vanligtvis O(n log n) tid för alfabetet med n symboler; avkodning och kodning är linjär i längden av data. Begränsningar inkluderar behovet av kännedom om symbolfrekvenser samt att prestanda varierar med datafördelningen.