Huffmancodering
Huffmancodering is een methode om gegevens die bestaan uit een rij van symbolen, optimaal en verliesloos te comprimeren. De codering wordt onder andere toegepast bij datacommunicatie en voor digitale afbeeldingen. Huffmancodering is vernoemd naar David Huffman, die de codering in 1952 voor het eerst beschreef. Elk symbool wordt gecodeerd als een bitstring, zodanig dat de code van een symbool nooit het eerste deel is van de code van een ander symbool. Dit maakt het mogelijk een rij symbolen te coderen door de codes van de afzonderlijke symbolen achter elkaar te plaatsen zonder scheidingsteken. Bij het decoderen van een bitstring volgt na iedere herkenbare code het begin van een volgende eenduidig herkenbare code. Dit wordt een prefixcodering of prefixvrije codering genoemd. Het principe van huffmancodering is eenvoudig. Van een reeks symbolen worden de veel voorkomende symbolen weergegeven door een kortere code, dan de weinig voorkomende. Zo kan de hele reeks op een kortere manier gecodeerd worden.
Huffmancodering is een methode om gegevens die bestaan uit een rij van symbolen, optimaal en verliesloos te comprimeren. De codering wordt onder andere toegepast bij datacommunicatie en voor digitale afbeeldingen. Huffmancodering is vernoemd naar David Huffman, die de codering in 1952 voor het eerst beschreef.
Elk symbool wordt gecodeerd als een bitstring, zodanig dat de code van een symbool nooit het eerste deel is van de code van een ander symbool. Dit maakt het mogelijk een rij symbolen te coderen door de codes van de afzonderlijke symbolen achter elkaar te plaatsen zonder scheidingsteken. Bij het decoderen van een bitstring volgt na iedere herkenbare code het begin van een volgende eenduidig herkenbare code. Dit wordt een prefixcodering of prefixvrije codering genoemd.
Het principe van huffmancodering is eenvoudig. Van een reeks symbolen worden de veel voorkomende symbolen weergegeven door een kortere code, dan de weinig voorkomende. Zo kan de hele reeks op een kortere manier gecodeerd worden.
Algoritme
[bewerken | brontekst bewerken]- Maak een lijst van de symbolen in het te comprimeren bestand met hun frequentie in afnemende frequentievolgorde (hiervoor kan 'haal-naar-vorencodering' gebruikt worden).
- Maak nu een boomstructuur als volgt:
- Koppel de twee symbolen met de kleinste frequentie tot een gecombineerd symbool met als frequentie de som van de twee afzonderlijke frequenties.
- Plaats het gecombineerde symbool terug in de gesorteerde lijst.
- Voer de vorige 2 stappen uit tot er één enkel symbool overblijft.
- Beginnend bij dit laatste symbool (de wortel van de boom, Engels: root en tree): codeer de vertakkingen nu steeds zodanig dat de hoogste frequentie een 0 en de laagste een 1 krijgt.
De huffmancode van een symbool is nu de lijst van bits (enen en nullen) die je tegenkomt als je vanaf de wortel van de boom het symbool opzoekt. Hiervoor geldt: hoe hoger de frequentie, hoe korter de (binaire) code. Op deze manier wordt compressie bereikt. Slaat men platte tekst op in (ASCII), dan nemen alle karakters in de tekst 1 byte (van 8 bits) in beslag. Door huffmancodering worden karakters die vaak voorkomen in een tekst in minder bits gecodeerd. Sommige karakters die weinig (of niet) voorkomen in de tekst krijgen weliswaar een code die langer is dan 8 bits (wat dus niet voor compressie zorgt), maar doordat deze karakters minder vaak voorkomen in de tekst dan de karakters met een laag aantal bits, zal het totaal wel gecomprimeerd zijn.
Het bovenstaande gaat ervan uit dat per bestand een optimale codering wordt afgeleid, en vervolgens toegepast. De huffmancodering is in zoverre optimaal dat deze een symboolstringcode geeft die vergeleken met andere prefixcoderingen en vastelengtecodering uit het kleinste aantal bits bestaat. Daarbij is niet meegerekend dat de codering zelf, of frequentie-informatie waaruit die is af te leiden, ook een aantal bits vergt.
Een andere mogelijkheid is om één codering op meerdere bestanden toe te passen, op basis van de frequenties in het geheel van de bestanden. Dan is de huffmancodering optimaal in de zin dat het verwachte aantal bits van de codering minimaal is.
Voorbeeld 1
[bewerken | brontekst bewerken]Bij 3 symbolen zijn de aantallen bits per code 1, 2 en 2, het eerste voor de code van het meest frequente symbool. Ook bij gelijke frequenties is er al een besparing.
Voorbeeld 2
[bewerken | brontekst bewerken]Bij 4 symbolen zijn de aantallen bits per code 1, 2, 3 en 3, bijvoorbeeld 1, 01, 001 en 000, als de hoogste frequentie groter is dan de laagste twee samen, en anders 2 voor elk symbool, namelijk 11, 10, 01 en 00.
Voorbeeld 3
[bewerken | brontekst bewerken]In dit voorbeeld wordt een huffmancodering afgeleid voor een willekeurige Nederlandse tekst, zonder rekening te houden met spaties en leestekens. Daarbij wordt uitgegaan van de letterfrequenties in het Nederlands.[1]:
Letterfrequenties in het Nederlands Letter frequentie (%) Letter frequentie (%) Letter frequentie (%) Letter frequentie (%) E 18,91 D 5,93 M 2,21 C 1,24 N 10,03 S 3,73 U 1,99 F 0,81 A 7,49 L 3,57 B 1,58 X 0,04 T 6,79 G 3,40 P 1,57 Y 0,03 I 6,50 V 2,85 W 1,52 Q 0,01 R 6,41 H 2,38 J 1,46 O 6,06 K 2,25 Z 1,39
Als eerste worden de twee letters met de laagste frequenties uit deze lijst, de Y en de Q, gecombineerd. De Y krijgt een 0 en de Q een 1. Samen hebben ze de frequentie 0,04. In de resulterende lijst staan nu de combinatie YQ en de X onderaan. YQ krijgt een 0 (Y dus 00, Q 01), en X krijgt een 1. De tak XYQ heeft frequentie 0,08 en de eerstvolgende laagste frequentie is 0,81 van de F. De F krijgt een 0 en de tak met XYQ een 1. Zo verdergaand wordt de C toegevoegd met frequentie 1,24. De C krijgt een 0 en de tak met FXYQ een 1. De zo ontstane tak heeft een gezamenlijke frequentie 2,13. De nu laagste twee zijn de J en de Z, die de bladeren van een nieuwe tak vormen. Zo gaat het verder tot de boom compleet is. Het eindresultaat staat hiernaast, met bij elke knoop de frequentie (de boom is voor het gemak 90° gedraaid; de bovenste tak is steeds '0', de onderste tak '1') (Dit komt niet precies op 100% uit, waarschijnlijk door afronding in de bron waaruit bovenstaande tabel is overgenomen.)
De verwachte lengte van een code is voor deze codering:
Bij codes van vaste lengte zouden er voor elke letter 5 bits nodig zijn.
Merk op dat de kortste code 11 is voor de letter E die het vaakst voorkomt. Geen van de overige codes begint met 11 of met een van de andere codes. Zo zijn er bijvoorbeeld codes die met 0001 beginnen, maar 0001 is zelf geen code.
Dit levert de volgende huffmancodering:
In omgekeerde volgorde van de frequentie Q 0001011101 Y 0001011100 X 000101111 F 00010110 C 0001010 Z 101011 J 101010 W 011011 P 011010 B 001101 U 001100 M 000100 K 10111 H 10110 V 10100 G 01100 L 00111 S 00011 D 1001 O 1000 R 0111 I 0101 T 0100 A 0010 N 0000 E 11
In alfabetische volgorde A 0010 B 001101 C 0001010 D 1001 E 11 F 00010110 G 01100 H 10110 I 0101 J 101010 K 10111 L 00111 M 000100 N 0000 O 1000 P 011010 Q 0001011101 R 0111 S 00011 T 0100 U 001100 V 10100 W 011011 X 000101111 Y 0001011100 Z 101011
Ter vergelijking:
- Morse-code is eveneens een verliesloze codering voor tekst. Hierbij is de code van veel letters wel het eerste deel van de code van een andere letter. Dit wordt ondervangen door de timing (de letterspatie is een pauze, zonder signaal).
- Bij 26 tekens met gelijke frequentie zouden bij de huffmancodering 16 een code van 5 bits hebben, 4 een code van 4 bits en 6 een code van 3 bits. Het gemiddelde aantal bits per teken is dan 4,385.
Literatuur
[bewerken | brontekst bewerken]- (en) D.A. Huffman, "A method for the construction of minimum-redundancy codes", Proceedings of the I.R.E., sept. 1952, pp 1098-1102