Huffmancodering uitgelegd
Computers slaan meestal elke letter op in hetzelfde aantal bits, acht in gewoon ASCII. Dat is eenvoudig maar verspillend, want sommige letters komen veel vaker voor dan andere. In 1951 vond een student de beste manier om elk symbool een code van eigen lengte te geven, frequente symbolen kort en zeldzame lang, met een constructie die zo eenvoudig is dat ze in een paar regels past. Huffmancodering zit nu in bijna elk gecomprimeerd bestand, elke afbeelding en elk geluid dat je opent.
Korte codes voor veelvoorkomende symbolen
Morsecode gebruikte het idee al in de jaren 1830: E, de meest voorkomende letter in het Engels, is één enkele punt, terwijl Q streep streep punt streep is. Zo'n code bespaart tijd en ruimte wanneer sommige symbolen vaker voorkomen dan andere. Maar variabele lengtes leveren een probleem op dat morsecode met pauzes oploste: hoe weet je waar de ene code eindigt en de volgende begint? En welke lengtes moet elk symbool krijgen om het totaal zo klein mogelijk te maken?
Prefixcodes
Het eerste probleem verdwijnt als geen enkele code het begin is van een andere. Met de codes A = 0, B = 10, C = 110 en D = 111 kunnen de bits 0101100 alleen gelezen worden als A B C A: zodra de tot dusver gelezen bits een code vormen, is die code compleet. Zulke prefixcodes komen precies overeen met binaire bomen met de symbolen in de bladeren, waarin elke linkertak voor 0 staat en elke rechtertak voor 1. Een code kiezen is een boom kiezen.
Huffmans constructie
Begin met één blad per symbool, gewogen naar hoe vaak het voorkomt. Neem de twee lichtste bomen en voeg ze samen onder een nieuwe knoop waarvan het gewicht hun som is, en herhaal dat tot er één boom over is. Dat is het hele algoritme. Zeldzame symbolen worden het eerst samengevoegd en komen diep in de boom terecht, met lange codes; veelvoorkomende worden het laatst samengevoegd en blijven dicht bij de top, met korte codes. Met een prioriteitswachtrij kost het tijd evenredig met n log n voor n symbolen.
Waarom het optimaal is
In een best mogelijke boom kunnen de twee zeldzaamste symbolen altijd als zusterknopen op het diepste niveau worden geplaatst: ze verwisselen met wat daar staat, kan het totaal alleen maar korter maken. Voeg ze samen tot één symbool met hun gezamenlijke gewicht, en de rest is hetzelfde probleem met één symbool minder, dus de gulzige stap sluit het beste antwoord nooit uit. Het totale aantal gebruikte bits is gelijk aan de som van de gewichten van alle interne knopen, en het samenvoegen houdt die zo klein mogelijk.
Een werkstuk in plaats van een examen
In 1951 volgde David Huffman, promovendus aan het MIT, de cursus informatietheorie van Robert Fano. Fano liet zijn studenten kiezen: het eindexamen doen of een werkstuk schrijven over het vinden van de efficiëntste binaire code. Huffman gaf het werkstuk bijna op, maar zag toen dat de boom van onderaf opbouwen, in plaats van van bovenaf te splitsen zoals in de methode van Shannon–Fano, altijd het beste resultaat geeft. Hij publiceerde het in 1952; de methode van de student versloeg die welke zijn professor met Claude Shannon had uitgewerkt.
Dicht bij de entropie
Claude Shannon toonde aan dat geen enkele code gemiddeld minder bits per symbool kan gebruiken dan de entropie van de bron. Een Huffmancode bereikt de entropie precies wanneer elke kans een macht van een half is, en ligt nooit een volle bit per symbool erboven. Het gat doet ertoe als één symbool heel vaak voorkomt: een symbool met een aandeel van 99% heeft nog steeds minstens één hele bit nodig, hoewel het maar ongeveer 0,015 bits informatie draagt. Aritmetische codering en de asymmetrische getalsystemen (ANS) van nieuwere compressors omzeilen die grens.
Huffmancodes overal
Huffmancodering wordt zelden alleen gebruikt, maar vormt de laatste stap van veel formaten. Deflate, in ZIP, gzip en PNG, vervangt eerst herhalingen door verwijzingen en schrijft het resultaat daarna met Huffmancodes. JPEG gebruikt ze voor de getallen die overblijven na de transformatie van het beeld, MP3 voor de audiogegevens, en faxapparaten voor de lengtes van zwarte en witte reeksen. Formaten versturen meestal een canonieke Huffmancode, waarbij alleen de codelengtes opgeslagen hoeven te worden, omdat de codes zelf daaruit kunnen worden herbouwd.
Probeer het zelf
Open de Huffmancode-bouwer om stap voor stap de boom op te bouwen van ABRACADABRA, MISSISSIPPI RIVER, een eigen zin of een andere tekst. Zie bij elke stap de twee lichtste bomen samenkomen, klik op een blad om de code ervan te zien, volg een symbool door de gecodeerde bits, en vergelijk het totaal met een code met vaste lengte, UTF-8 en de entropie.
Veelgestelde vragen
Wat is het verschil tussen Huffman- en Shannon–Fano-codering?
Shannon–Fano-codering bouwt de boom van bovenaf op door de symbolen steeds weer in twee groepen van bijna gelijk gewicht te splitsen. Dat is vaak goed, maar niet altijd optimaal. Huffman bouwt de boom van onderaf op door de twee lichtste bomen samen te voegen, en geeft altijd de kortst mogelijke prefixcode.
Heeft de decoder de boom nodig?
Ja, hij heeft dezelfde code nodig. Gecomprimeerde bestanden slaan die daarom op, meestal als een lijst codelengtes voor een canonieke code, wat maar enkele tientallen bytes kost. Bij korte teksten kan die overhead groter zijn dan de besparing; de bouwer telt alleen de gecodeerde bits.
Kan Huffmancodering een bestand groter maken?
De gecodeerde symbolen nemen nooit meer bits in dan een code met vaste lengte voor dezelfde symbolen. Maar ook de codetabel moet worden opgeslagen, dus bij heel korte of bijna willekeurige gegevens kan het resultaat iets groter zijn dan het origineel.
Wat zegt de ongelijkheid van Kraft?
Dat een prefixcode met codelengtes l₁, l₂, … precies dan bestaat als de som van 2 tot de macht −l over alle symbolen hoogstens 1 is. Voor een volledige boom, zoals elke Huffmanboom met minstens twee symbolen, is de som precies 1.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Open de Huffmancode-bouwer