Wat is Huffman-code?
Methode om uit de kansen van de symbolen een prefixcode te maken waarvan de gemiddelde codelengte zo klein mogelijk is. Er wordt een boom opgebouwd door herhaaldelijk de twee symbolen (of knopen) met de kleinste kansen samen te voegen tot één, en aan elke vertakking worden 0 en 1 toegekend om de codewoorden te vormen. Hoe vaker een symbool voorkomt, hoe korter zijn codewoord. Ze is optimaal onder de prefixcodes die één symbool tegelijk coderen, en haar gemiddelde codelengte is minstens de entropie en kleiner dan de entropie + 1 bit. Ze wordt in combinatie met andere methoden gebruikt in Deflate (ZIP, gzip), JPEG en elders. Huffman publiceerde haar in 1952.
Japanse benaming: ハフマン符号
“Huffman-code” komt voor in 5 oefenvragen uit 1 onderwerpen, bijv. Basis van informatietheorie en codering.
Vakgebied: Basis van informatietheorie en codering
Hoe je er een maakt
Voor symbolen met kansen 1/2, 1/4, 1/8 en 1/8 worden eerst de twee keer 1/8 samengevoegd tot 1/4, dan dat en de 1/4 tot 1/2, en ten slotte dat en de resterende 1/2. Door de takken van de wortel naar elk symbool met 0 en 1 te labelen krijgt men de codewoorden 0, 10, 110 en 111, met een gemiddelde codelengte van 1,75 bit, gelijk aan de entropie. Wanneer elke kans het omgekeerde is van een macht van 2, valt de gemiddelde codelengte zo samen met de entropie.
De codewoorden zijn niet uniek
De codewoorden veranderen afhankelijk van hoe 0 en 1 worden toegekend en welke van twee gelijke kansen eerst wordt samengevoegd. Met kansen 0,4; 0,2; 0,2; 0,1 en 0,1 kunnen de codelengtes bijvoorbeeld 1, 2, 3, 4, 4 of 1, 3, 3, 3, 3 of 2, 2, 2, 3, 3 zijn, maar de gemiddelde codelengte is in alle gevallen 2,2 bit. Daarom vragen examens eerder naar de gemiddelde codelengte dan naar de codewoorden zelf.
Grenzen en verbeteringen
Codelengtes zijn beperkt tot gehele aantallen bits, dus voor een bron met een symbool waarvan de kans dicht bij 1 ligt, wordt het verschil met de entropie groot. Binaire symbolen één voor één coderen kost 1 bit per symbool, hoe scheef ze ook verdeeld zijn. Symbolen samen coderen, of een methode gebruiken die niet aan hele bits gebonden is, zoals aritmetische codering, brengt de lengte dichter bij de entropie.
Veelgestelde vragen
Wat is nodig om gegevens te herstellen die met een Huffman-code zijn gecomprimeerd?
Om de gegevens te herstellen moet bekend zijn welk codewoord aan welk symbool is toegekend (een codetabel, of de codelengte van elk symbool). Gecomprimeerde gegevens dragen de codetabel daarom met zich mee of gebruiken een vooraf afgesproken tabel. Deflate stuurt alleen de codelengtes, en de ontvanger bouwt de codewoorden opnieuw op volgens dezelfde regel (canonieke Huffman-codes).
Kan een Huffman-code alle gegevens kleiner maken?
Nee. Zijn de kansen van de symbolen niet scheef verdeeld, dan krimpen de gegevens nauwelijks. In gegevens waarin alle 256 bytewaarden even waarschijnlijk zijn, is bijvoorbeeld elk codewoord 8 bits lang, en de codetabel maakt het resultaat iets groter.