Huffmancodering

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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.

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]

  1. Maak een lijst van de symbolen in het te comprimeren bestand met hun frequentie in afnemende frequentievolgorde (hiervoor kan 'haal-naar-vorencodering' gebruikt worden).
  2. Maak nu een boomstructuur als volgt:
    1. Koppel de twee symbolen met de kleinste frequentie tot een gecombineerd symbool met als frequentie de som van de twee afzonderlijke frequenties.
    2. Plaats het gecombineerde symbool terug in de gesorteerde lijst.
    3. Voer de vorige 2 stappen uit tot er één enkel symbool overblijft.
  3. 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 bereik je compressie. Als je namelijk platte tekst opslaat (ASCII), nemen alle karakters in de tekst 1 byte (van 8 bits) in beslag. Door Huffmancodering zorg je ervoor dat karakters die vaak voorkomen in een tekst in minder bits gecodeerd worden. 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.

Een voorbeeld[bewerken]

Stel, we trachten een Huffmancodering te vinden voor een Nederlandse tekst. De letterfrequenties in het Nederlands zijn, volgens onderzoek[1]:

letterfrequenties in het Nederlands
Letter percent Letter percent Letter percent Letter percent Letter percent Letter percent Letter percent
E 18,91% N 10,03% A 7,49% T 6,79% I 6,50% R 6,41% O 6,06%
D 5,93% S 3,73% L 3,57% G 3,40% V 2,85% H 2,38% K 2,25%
M 2,21% U 1,99% B 1,58% P 1,57% W 1,52% J 1,46% Z 1,39%
C 1,24% F 0,81% X 0,04% Y 0,03% Q 0,01%

We nemen de twee laagste frequenties uit deze lijst, en combineren ze. Dat zijn dus de Y (krijgt een 0) en de Q (krijgt een 1). Vervolgens doen we hetzelfde met de resulterende lijst. YQ en X staan nu onderaan. YQ krijgt een 0 (Y dus 00, Q 01), en X krijgt een 1. Vervolgens wordt F bij XYQ gevoegd. Enzovoort. Het eindresultaat staat hieronder, met bij elke knoop het percentage (de boom is voor het gemak 90° gedraaid; de bovenste tak is steeds '0', de onderste tak '1')

 +-10,03% (N)
 +-18,10%+
| | +--2,21% (M)
| | +--4,34%+
| | | | +--1,24% (C)
| | | +--2,13%+
| | | | +--0,81% (F)
| | | +--0,89%+
| | | | +--0,03% (Y)
| | | | +--0,04%+
| | | | | +--0,01% (Q)
| | | +--0,08%+
| | | +--0,04% (X)
| +--8,07%+
| +--3,73% (S)
 +-32,73%+
| | +--7,49% (A)
| +-14,63%+
| | +--1,99% (U)
| | +--3,57%+
| | | +--1,58% (B)
| +--7,14%+
| +--3,57% (L)
 +-58,92%-+
| | +--6,79% (T)
| | +-13,29%+
| | | +--6,50% (I)
| +-26,19%+
| | +--3,40% (G)
| | +--6,49%+
| | | | +--1,57% (P)
| | | +--3,09%+
| | | +--1,52% (W)
| +-12,90%+
| +--6,41% (R)
-+
| +--6,06% (O)
| +-11,99%+
| | +--5,93% (D)
| +-22,32%+
| | | +--2,85% (V)
| | | +--5,70%+
| | | | | +--1,46% (J)
| | | | +--2,85%+
| | | | +--1,39% (Z)
| | +-10,33%+
| | | +--2,38% (H)
| | +--4,63%+
| | +--2,25% (K)
 +-41,23%-+
 +-18,91% (E)

(Dit komt niet precies op 100% uit, waarschijnlijk door afronding in de bron waaruit bovenstaande tabel is overgenomen)

Dit levert de volgende Huffmancodering:

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 maar niet optimale codering voor Nederlandstalige tekst.

Literatuur[bewerken]

Bronnen, noten en/of referenties