Huffmancode
Code met vaste lengte
Bespaard
Entropie

Symbool Aantal Code Bits Bits totaal

Meer informatie over Huffmancodering

Huffmancode-bouwer

Waarom zou een veelvoorkomende letter als e evenveel bits innemen als een zeldzame als q? Huffmancodering geeft frequente symbolen korte codes en zeldzame lange codes, en doet dat op de best mogelijke manier. Typ een tekst of kies een voorbeeld en bouw de Huffmanboom stap voor stap op: de twee lichtste bomen komen samen onder een nieuwe knoop, steeds weer, tot er één boom over is. Dan spelt elk pad vanaf de top een code, en kun je elk symbool volgen door de gecodeerde bits. Typ een tekst of kies een voorbeeld. Elk symbool begint als blad met zijn aantal. Doorloop de opbouw stap voor stap: elke stap voegt de twee lichtste bomen samen onder een nieuwe knoop met hun som, tot er één boom over is. Daarna geeft het pad van de top naar een blad de code ervan, 0 voor links en 1 voor rechts. Klik op een blad, een rij of een stuk van de bits om één symbool te volgen, en vergelijk het totaal met een code met vaste lengte en met de entropie.

Hoe het werkt

  1. Typ of plak een tekst, of kies een voorbeeld zoals ABRACADABRA of MISSISSIPPI RIVER.
  2. Doorloop de opbouw met ‘Volgende stap’, of druk op ‘Afspelen’: elke stap voegt de twee lichtste bomen samen onder een knoop met hun som.
  3. Als de boom klaar is, klik je op een blad, een rij van de tabel of een stuk van de bits om één symbool te volgen, en vergelijk je de totalen in de tegels.

Hoe de boom wordt opgebouwd

Tel hoe vaak elk symbool voorkomt en maak van elk symbool een boom van één blad, gewogen naar zijn aantal. Herhaal dan één eenvoudige stap: neem de twee bomen met de kleinste gewichten en hang ze onder een nieuwe knoop waarvan het gewicht hun som is. Elke stap laat één boom minder over, dus na n − 1 stappen voor n symbolen blijft er één boom over. De zeldzame symbolen werden het eerst samengevoegd en zitten diep beneden; de veelvoorkomende werden laat samengevoegd en zitten dicht bij de top.

De codes aflezen

Loop vanaf de top naar beneden: een stap naar links voegt een 0 toe, een stap naar rechts een 1. Het pad naar een blad is de code van dat symbool. Omdat symbolen alleen in de bladeren zitten, is geen enkele code het begin van een andere, dus een reeks bits kan zonder scheidingstekens worden gedecodeerd: volg de bits omlaag door de boom, en telkens als je een blad bereikt, schrijf je het symbool op en begin je weer bovenaan. Voor ABRACADABRA heeft Huffman 23 bits nodig, tegen 33 voor een vaste code van 3 bits per letter.

Veelgestelde vragen

Waarom is de Huffmancode de best mogelijke?

Van alle codes die elk symbool een eigen reeks hele bits geven, heeft geen enkele een korter totaal voor de gegeven aantallen. Het bewijs volgt de constructie: in een optimale code kunnen de twee zeldzaamste symbolen altijd zusterknopen op het diepste niveau worden, en als je ze samenvoegt, blijft er een kleiner probleem van dezelfde soort over. Het totale aantal bits is gelijk aan de som van de gewichten van alle interne knopen van de boom.

Wat is een prefixcode?

Een code waarin geen enkel codewoord het begin is van een ander, zoals 0, 10, 110 en 111. Dankzij die eigenschap kan een decoder een stroom bits zonder scheidingstekens lezen, omdat hij altijd weet waar een codewoord eindigt. Elke Huffmancode is een prefixcode: de symbolen zitten alleen in de bladeren van de boom.

Is de Huffmanboom uniek?

Niet helemaal: als twee bomen hetzelfde gewicht hebben, mag elk van beide eerst worden genomen, en links en rechts kunnen worden verwisseld. Verschillende keuzes geven verschillende codes, maar altijd hetzelfde totale aantal bits. De bouwer kiest bij gelijk gewicht altijd op dezelfde manier, dus een tekst geeft altijd dezelfde boom.

Hoe dicht komt Huffman bij de entropie?

De gemiddelde codelengte is minstens de entropie en minder dan één bit erboven. Ze is gelijk aan de entropie als elke kans een macht van een half is, zoals bij het voorbeeld met halverende aantallen. Aritmetische codering en moderne range coders omzeilen de grens van hele bits en komen nog dichterbij.

Wordt mijn tekst ergens naartoe gestuurd?

Nee. De boom en de codes worden in je browser berekend, en je tekst blijft in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor