David Albert Huffman vyvinul tento algoritmus v roce 1952. Huffmanovo kódování využívá takzvaného prefixového kódu. Principem prefixového kódu je, že žádné kódové slovo není předponou jiného .
Algoritmus je založen na četnosti výskytu jednotlivých znaků v posloupnosti. Znaky, které se vyskytují nejčastěji, pak budou kódované kratší kódovou posloupností, a znaky, které se vyskytují málo budou zakódované naopak větší kódovou posloupností
Algoritmus kódování:
v prvním kroku algoritmus projde vstupním řetězcem a vytvoří tabulku četnosti výskytu jednotlivých znaků,
podle četnosti výskytu znaků vytvoříme frontu, kde priorita bude podle čestnosti výskytu jednotlivých znaků,
začne tvořit uzly binárního stromu. Dva první znaky z fronty sloučí a z nich vytvoří nový uzel stromu, který přidá do fronty. Četnost nového uzlu je součet četností sečtených prvků,
opakujeme předchozí kroky tak dlouho, dokud se nevytváří celý strom,
zakódujeme strom 1 a 0. Uzlům, které se nachází v levé části stromu přidává 0 a uzlům, které se nachází v pravé části stromu přidává 1,
v dalším kroku provede kódovaní vstupního řetězce do binárního tvaru podle binárního stromu, který byl vytvořen v předchozím kroku,
kódovaní se provádí tak dlouho, dokud nebude zakódován celý vstupní řetězec.
Algoritmus dekódování:
dekódování se provádí pomocí binárního stromu,
dekodér projde stromem od kořene k uzlům a zjistí, kterému znaku odpovídá kód,
dekódování se provádí tak dlouho, dokud nebude dekódován celý řetězec.
(c) 2016 Ivan Tvorogov, Pavel Rajmic, Ústav telekomunikací, FEKT, VUT v Brně