Kódování

V roce 1952 představil jinou konstrukci efektivního prefixového kódu David A. Huffman, který jako student doktorského studia reagoval o rok dříve na představení Shannon-Fano metody jedním z jejích tvůrců. Profesor Fano na jednom ze seminářů vyzval studenty, aby navrhli optimální řešení daného problému. Huffmanovo kódování se opravdu ukázalo být více efektivní, než způsob jeho učitele. Základní myšlenka zůstala stejná a spočívá v tom, přiradit znakům ze zdrojové abecedy kódová slova podle pravděpodobnosti výskytu ve zprávách, které zdroj produkuje. Častěji se vyskytujícím znakům jsou přiřazena kratší kódová slova a naopak.

Postup vytvoření efektivního prefixového kódu Huffmanovou metodou vypadá obecně následovně:

1. Pravděpodobnosti sestupně seřadíte.
2. Sečtete dvě nejmenší pravděpodobnosti.
3. Nově získanou posloupnost pravděpodobností opět sestupně seřadíte (bude mít o jeden prvek méně než předchozí pravděpodobnost).
4. Kroky 2 a 3 opakujete, dokud nezbude v posloupnosti pouze jediný prvek, kterým je 1 (vždy byste se měli dosčítat do 100 %).
5. Začnete jít zpět s tím, že se podíváte na pravděpodobnosti, na které se rozpadá poslední sčítanec.
6. Pravděpodobnosti, která byla ve sčítání a je v rámci řazení nahoře přidělíte na konec kódového slova např. binární 1.
7. Pravděpodobnosti, která byla ve sčítání a je v rámci řazení dole přidělíte na konec kódového slova binární 0.
8. Kroky 5 až 7 opakujete, dokud budou v posloupnosti nějaké pravděpodobnosti, které vznikly sčítáním.

Obr. 20: Obecné schéma Huffmanova kódování. (Zdroj vlastní)

Binární 1 a 0 můžete přidělovat v opačném pořadí (0 k horní pravděpodobnosti, 1 k dolní), ale je třeba to dělat po celou dobru stejně. Alternativou může být, že budete dávat k pravděpodobnostem binární 0 a 1 rovnou při cestě vpřed. I při této variantě kódová slova vytváříte odzadu (resp. právě umisťovaný bit dáváte na poslední místo).

 Jak podle uvedeného postupu zakódujete zdrojové znaky D = 18 %, E = 36 %, F = 6 %, K = 10 %, P = 21 %, V = 9 %?