Student World

Příběh Davida Huffmana

V době, kdy stále ještě není jasné, jaký obrat vezmou diskuse a legislativní střety o softwarové patenty, může být zajímavý příběh Davida Huffmana, který si své slavné kódování nikdy patentovat nenechal…

Psal se rok 1951. Byla to výzva, jakých se denně na univerzitách a vysokých školách po celém světě urodí desítky. Profesor umožnil svým studentům vyhnout se zkoušce, když vyřeší složitý problém. Jednalo se o problém dosažitelnosti nejkratšího prefixového kódování (tzv. ideální kódování ve vztahu k informační entropii). Studenti ovšem nevěděli, že se jedná o nevyřešenou úlohu, protože v té době byly známy jen docela neúčinné metody (analýzou shora dolů).

Davidu Huffmanovi (narozen 1925) na univerzitě v Ohiu se ke zkoušce nechtělo. Ne snad proto, že by látce nerozuměl. Chtěl se zkoušce prostě vyhnout, jenže úloha se zdála téměř neřešitelná. Když už chtěl nechat bádání a začít se na závěrečnou zkoušku učit, zadíval se na papír s poznámkami, které zlostně vyhodil do koše. V tu chvíli ho to napadlo.

Magistr Huffman později publikoval svůj nápad v práci nazvané Metoda pro vytvoření kódu s minimální redundancí (A Method for the Construction of Minimum Redundancy Codes, http://compression.graphicon.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf). Jeho řešení pomocí binárního stromu bylo velmi prosté a zároveň elegantní. Ale také velmi účinné v praxi. V tu dobu již působil na MIT (Massachusetts Institute of Technology), kde také získal rok nato doktorát.

Míru informace (přesněji řečeno nejistoty, http://en.wikipedia.org/wiki/Information_entropy) stanovil poprvé americký vědec C. E. Shannon (http://en.wikipedia.org/wiki/Claude_E._Shannon). Určuje nahodilost v nějakém signálu – například míru informace písmena "a" ve větě (v řetězci písmen). Čím více se pravděpodobnost výskytu písmena na dané pozici blíží hodnotě 0,5, tím vyšší má informační hodnotu. Více prozradí následující graf (http://upload.wikimedia.org/wikipedia/en/c/c9/Binary_entropy_plot.png) – na ose x je pravděpodobnost výskytu a je jasné, že pokud se písmeno v řetězci nevyskytuje, nebo je řetězec tvořen jen tímto písmenem, pak je míra informace minimální.

Princip Huffmanovy metody spočívá ve vytvoření binárního stromu s ohodnocenými hranami (1,0) a uzly (pravděpodobnosti výskytu). Pravděpodobnost vnitřního uzlu je rovna součtu pravděpodobností jeho potomků. Ve výsledném stromu jsou kódované znaky uložené pouze v listech, takže je zaručeno, že kódování (tedy posloupnost ohodnocení hran od kořene k listu) bude prefixové (tedy žádná předpona nebude kódem jiného znaku – zakódovaný vstup bude jednoznačně dekódovatelný, protože neznáme šířky binárních kódů). Doporučuji shlédnout demonstrační applet (http://www.cs.sfu.ca/cs/CC/365/li/squeeze/Huffman.html).

Dnes se nejrůznější varianty Huffmanova kódování (například adaptivní varianta, http://vychodil.inf.upol.cz/courses/cs1pp/doc/adaptivni-huffman.pdf) používají v široké škále produktů, zejména je to neoddělitelná součást některých komprimačních algoritmů (PKZIP, JPEG, MP3, BZIP2). Zajímavé je, že algoritmus z unixového programu bzip2 používal nejdříve aritmetické kódování (jedná se o zobecněný princip Huffmanova kódování, algoritmus vykazuje mírně vyšší účinnost). Jelikož ale na tento algoritmus získala firma IBM v letech 1977-2001 přes desítku patentů a bylo prakticky nemožné jej efektivně implementovat bez použití těchto metod, programátoři tohoto open-source programu bzip 2 se rozhodli použít Huffmanovo kódování.

Profesor David A. Huffman (http://en.wikipedia.org/wiki/David_A._Huffman) stál při zrodu fakulty informatiky na University of California v Santa Cruz a získal mnoho ocenění (kromě jiného medaili R. W. Hamminga při IEEE za celoživotní přínos pro informatiku). Po desetiměsíčním boji s rakovinou zemřel v říjnu roku 1999. Svůj geniální nápad David Huffman nikdy nepatentoval (ani nechtěl). Svému synovci (http://www.huffmancoding.com/) říkával: "Vždyť je to jen algoritmus."

autor Lukáš Zapletal