Statické Huffmanovo kódování

Základní informace

statistická kompresní metoda
dvouprůchodová kompresní metoda
semiadaptivní kompresní metoda
asymetrická kompresní metoda
Optimální prefixový kód
Komprimační algoritmy PKZIP, JPEG, MP3, BZIP2

Časová a paměťová složitost algoritmu

Časová složitost algoritmu: O(n + |Σ| * log|Σ|)
Paměťová složitost algoritmu: O(|Σ|)

Označme n velikost vstupních dat a |Σ| velikost vstupní abecedy. Z algoritmu vyplývá, že se celý vstupní text projde 2x (jednou pro získání četností a jednou pro zakódování jednotlivých znaků), pak se vytvoří binární strom (ne nutně úplný) o |Σ| listech a hloubce log₂|Σ|, jeho velikost je tedy přibližně 2*|Σ| (počet uzlů). Tento strom se pak prochází kvůli získání kódu pro každé vstupní písmeno, průchod trvá |Σ|*log₂|Σ|. Pro seřazení a zatřiďování můžeme počítat časovou složitost O(|Σ|log|Σ|). Časová složitost je 2*n + |Σ|*log₂|Σ| + |Σ|log|Σ| a tedy O(n + |Σ|log|Σ|) a paměťová 2*|Σ| tedy O(|Σ|).

Historie

Příběh Davida Huffmana a jeho kódování

Kalendář ukazoval rok 1951. Na univerzitách a vysokých školách po celém světě se řeší desítky podobných problémů jako na té, kde studoval David Huffman. Profesor umožnil svým studentům vyhnout se zkoušce, když vyřeší složitý problém. Spočíval v dosažitelnosti nejkratšího prefixového kódování (tzv. ideální kódování ve vztahu k informační entropii). Jednalo se zatím o nevyřešenou úlohu, což ovšem studenti nevěděli. 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. Nikoliv snad proto, že by látce nerozuměl, ale chtěl se zkoušce prostě vyhnout. Úloha se zpočátku zdála téměř neřešitelná. Když už chtěl nechat bádání a regulérně se na zkoušku připravit, zadíval se na papír s poznámkami, které zlostně vyhodil do koše a v tu chvíli ho to napadlo...

Později už jako magistr Huffman 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). Jeho řešení pomocí binárního stromu bylo velmi prosté a zároveň elegantní. Ale také velmi účinné v praxi. Svůj geniální nápad David Huffman však nikdy nepatentoval (ani nechtěl). Svému synovci totiž říkával: "Vždyť je to jen algoritmus."

Dnes se nejrůznější varianty Huffmanova kódování (například adaptivní varianta) používají v mnoha produktech, zejména v některých komprimačních algoritmech (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í.

Popis

Algoritmus si nejprve spočítá četnosti (pravděpodobnosti) jednotlivých znaků ve vstupní abecedě. Na základě těchto četností poté vygeneruje binární strom, jehož hrany nesou hodnotu 0 nebo 1, a v jehož listech jsou znaky vstupní abecedy. Navíc platí, že čím vyšší má znak pravděpodobnost, tím blíže ke kořenu se ve stromu vyskytuje. Místo těchto znaků je do listů následně přiřazen bitový kód, který odpovídá zřetězení hodnot hran, kterými projdeme při cestě z kořene do daného listu. Jelikož jedna z hodnot 0 nebo 1 se vyskytuje vždy na hranách vedoucích k pravému následníkovi (kdežto druhá k levému) a znaky vstupní abecedy jsou umístěny pouze v listech, je výsledný kód prefixový. Tento strom, nebo alespoň informace o četnostech výskytů jednotlivých znaků ve vstupních datech, je také potřeba přiložit k výsledné posloupnosti, aby byla možná dekomprimace.

Pseudokód


 1:  begin
 2:     spočíst četnosti jednotlivých znaků (zdrojových jednotek)
 3:     output(zakódované četnosti ve Fibonacciho kódu 2. řádu)
 4:     setřidit je do neklesající posloupnosti
 5:     vytvořit list (znak, četnost c, levý syn = NULL, pravý syn = NULL) 
 6:       stromu pro každý znak a vložit listy do fronty F
 7:     while (|F|>=2) do 
 8:      begin
 9:        z fronty vyber dva první uzly (u1, u2) s nejnižšími četnostmi
10:        vytvoř uzel ohodnocený součtem vybraných jednotek, 
11:          následníci jsou vybrané jednotky (eps, c(u1)+c(u2), u1, u2)
12:        zatřiď nový uzel do fronty
13:      end
14:     list ohodnotit cestou z kořene do listu (levý syn 1, pravý syn 0)
15:     vytvořit výstup z takto zakódovaných vstupních písmen
16:  end

Odkazy

D. Huffman: A Method for the Construction of Minimum Redundancy Codes. Proceedings of the I.R.E, svazek 40, str. 1098-1101, září 1952.
David A. Huffman. Wikipedia, the free encyclopedia.