Huffmanovo kódování

Představuje základní (a vlastně velmi jednoduchý) kompresní algoritmus. Je účinné, pokud jednotlivé znaky ve zdrojovém textu nejsou obsaženy se stejnou četností. To je například případ psaných dokumentů, kde z hlediska ASCII tabulky je využito pouze minimální množství znaků a často ještě s různou incidencí (například písmena a a e se vyskytují v anglickém jazyce zdaleka nejčastěji, naopak například písmeno z se v angličtině vyskytuje minimálně).

Princip

Předpokládejme tedy, že máme analýzu četnosti výskytu jednotlivých znaků (například v procentech), například:

Kódování

V prvním kroku provedeme sestupné seřazení dle četnosti výskytu jednotlivých znaků (při schodě se postupuje dle jiného klíče, který však musí být vždy stejný, řekněme dle lexikálního uspořádání znaků apod.):

V dalším kroku již záleží na tom, jaká je n-arita výsledného kódu (tj. kolik máme k dispozici znaků, při binárním kódování máme k dispozici dva znaky, při ternarním kódování máme 3 znaky apod.). Obecně postupujeme tak, že odspodu spojujeme n vstupních symbolů (dle n-arity) a součet jejich pravděpodobnosti představuje v dalším kroku jeden symbol, takto postupujeme cyklicky dokola, dokud nespojíme všechny symboly (součet výsledné pravděpodobnosti je nyní 100%). V druhém kroku určujeme kód, který přidělíme jednotlivým vstupním symbolům. Zde se postupuje tak, že začínáme od konce (100% pravděpodobnosti) a inkrementálně přidělujeme jednotlivým znakům ve stromu kód, inkrementujeme vždy pouze danou pozici, aby nevznikali prefixy. Vše je zobrazeno na obrázku níže (červeně) pro binární kódování.

Tvovrba binárního kódu

Při vzniklém kódu by se například řetězec (kde se vyskytují jednotlivé znaky s incidencí uvedenou v tabulce výše):

AECCEBBBCC CBDBBBAABB FEEEAAAEBD BEEGEEDEAD AEAEAAAEED

Zakódoval jako (mezery jsou do výstupu zařazeny pouze pro lepší čitelnost):

100011011 001011011 011101101 101011110 101101101 100100101 101111100 001001001 000101111 010100111 110011100 100111010 001000100 100100001 110

Tvorba ternárního kódu

Dle stejného postupu je možné vytvořit obecně n-ární kód, v případě níže je ukázka tvorby ternárního kódu (kód o základu 3). Vše se dělá identicky jako u binárního, pouze se neberou dvě "vlákna", nýbrž tři.

Stejně jako výše je možné snadno zakódovat slovo při využití ternárního kódu (vše je vlastně stejné)

AECCEBBBCC CBDBBBAABB FEEEAAAEBD BEEGEEDEAD AEAEAAAEED

Výsledek při ternárním kódu:

1021210202 0202121212 0220202020 1120202210 0011102022 0200022200 2200122010 1011100220

Dekódování

Probíhá stejně jako kódování, dle stejného předpisu si vytvoříme kódy pro jednotlivé symboly (musíme znát tabulku symbolů a jejich incidence). Nahrazování zakódovaných slov probíhá od NEJDELŠÍHO kódu (v našem případě odspodu od písmene F), tj. od znaků s nejmenší incidencí výskytu.