Statické Huffmanovo kódování
28. Březen 2002, 00:00 (14894x zobrazeno) Statické huffmanovo kódování je založeno na četnostech znaků v textu.
Tato myšlenka se, v podobě algoritmu, poprvé objevila v Shannon-Fanově kódu
(Fano byl Huffmanův učitel na MIT a Huffmanovo kódování vzniklo jako domácí
úloha, kterou David Huffman vypracoval místo zkoušky). Zakladni myšlenkou
je tedy zakódování znaků podle počtu jejich výskytů ve vstupu tak, že znaky,
které se vyskytují nejčastěji, mají nejkratší kód. Tedy například máme-li
na vstupu text s četnostmi znaků:
a: 19
b: 13
c: 10
d: 7
e: 5
f: 1,
pak vznik (Shannon-Fanova) kódu můžeme vidět v následující tabulce:
| Znaky | Četnosti | ||||
| a | 19 | 0 | 0 | ||
| b | 13 | 0 | 1 | ||
| c | 10 | 1 | 0 | ||
| d | 7 | 1 | 1 | 0 | |
| e | 5 | 1 | 1 | 1 | 0 |
| f | 1 | 1 | 1 | 1 | 1 |
Do tabulky jsme zanesli všechny znaky, které se v daném vstupním textu vyskytují a spočítali jsme jejich četnosti (lineárním průchodem vstupního textu). Seskupili jsme je tak, že rozdíl součtu četností znaků v jedné skupině a znaků v skupině druhé je minimální a znakům v jedné skupině jsme přiřadili jedničku, zatímco znakům v druhé nulu (to jsou první znaky kódového slova daného písmene). Tento systém dále aplikujeme rekurzivně na každou skupinu zvlášť. Tedy např. kód písmene 'd' je '110'. Na výstup vydáme místo každého písmena právě vytvořený jemu odpovídající kód. Samozřejmě, že jedničky a nuly zde nechápeme jako 1-bytove položky, ale jako 1-bitové(!) položky. Jinak by místo komprese došlo k několikanásobné expanzi, což jistě není kýžený výsledek. Jeden znak je klasicky uložen v jednom bytu a ten je tvořen osmi bity. My jsme ale kódováním dosáhli toho, že jeden znak má méně než osm bitů, čímž dochází ke kompresi. To znamená, že vstupy a výstupy našeho případného programu musíme nějakým způsobem ošetřit a při dekomprimaci nečíst po bytech, ale po bitech.
Důležitou vlastností právě popsaného algoritmu je jeho "prefixovost".
Čímž rozumíme, že žádné kódové slovo (v našem případě kód písmene) není prefixem
nějakého jiného. Kdyby tomu tak bylo, pak bychom text nemohli jednoznacně
dekódovat. Uveďme si jednoduchý příklad:
| A | 10011 |
| B | 10 |
| C | 011 |
Tuto prefixovost Shannon-Fannova kódu můžeme zachytit tzv. prefixovým
stromem. Náš původní příklad (jehož Shannon-Fanův kód je uveden v první tabulce)
bude mít následující prefixový strom:
Každý Shannon-Fanův kód lze zachytit takovýmto binárním stromem, kde písmena vstupní abecedy jsou v listech a jejich kódy tvoří cesta od kořene do daného vrcholu. Nyní je snadno vydět že kód je opravdu prefixový. Kdyby tomu tak nebylo, pak by na cestě do nějakého listu muselo ležet nějaké písmeno vstupní abecedy, což by ovšem bylo ve sporu s tím, že všechny písmena leží v listech.
Přirozeně se teď nabízí otázka, zda je Shannon-Fanův kód optimální, zda někdy neexistuje prefixový strom, který by byl lepší. Odpověď na tuto otázku je ano. Shannon-Fanův kód nám skutečně nezajišťuje optimální řešení (tedy ani optimální kompresi) a jak vás už možná napadlo, tak algoritmus, který vždy vydá optimální prefixový strom je Huffmanův kód.
Jak tedy sestrojit huffmanův kód? Huffman si všiml dvou věcí, které musí
optimální prefixový kód splňovat:
- Znaky s větší četností musí stejně dlouhá nebo kratší kódová slova, než znaky s četností menší.
- Pro každé dva znaky s nejmenšími četnostmi se dá nalézt optimální prefixový kód, kde tyto znaky mají stejně dlouhá kódová slova lišící se pouze v posledním znaku, nebo-li jsou to bratři v prefixovém stromě (o úroveň "výše" je stejný vrchol - otec).
Postavíme jednotlivé znaky (u kterých si pamatujeme jejich četnost) jako samostatné vrcholy a z nich postupně budujeme prefixový strom. Množinu tvořenou vrcholy označme například X. Vezmeme z X dva prvky (vrcholy==znaky) s nejmenším ohodnocením (kde ohodnocením rozumíme jejich četnosti) a spojíme je tak, že z nich uděláme bratry, přičmž jejich otec bude mít ohodnocení rovnající se součtu četností jeho synů. Právě užité prvky z množiny vyjmeme a namísto nich přidáme do X jejich otce. Tento postup rekurzivně opakujeme do té doby, než bude množina X jednoprvková. Tento jediný prvek je kořenem našeho Huffmanova stromu vyjadřující optimální prefixový kód.
Výše zmíněný postup si ukážeme na následující sekvenci obrázků (znaky a jejich četnosti jsou zvoleny stejně jako v 1. tabulce):
Vybereme dva prvky s nejmenší četností a vytvoříme k nim vrchol reprezentující jejich otce s četností rovnající se součtu četností jeho synů.
Vybrali jsme tedy vrcholy 'e' a 'f'. K nim vytvoříme jejich otce.
Nyní potřebujeme znovu vybrat vrcholy s nejmenšími četnostmy z množiny X (v ní již nejsou vrcholy 'e' a 'f'). Vezmeme tedy nově vytvořený vrchol (to je ten s ohodnocenímt 6) a vrchol 'd' (ohodnocení 7).
Další postup je analogický a jistě si ho sami domyslíte z následujících obrázků.
Huffmanův kód se používá (spolu s Burrows-Wheelerovou transformací, které bude věnován některý z dalších článků) například v bzip2, kompresním programu dnes hojně používaném v linuxovém světě. To ovšem není náhoda. Důvodem (samozřejmě nebereme-li do úvahy dobrý kompresní poměr) je fakt, že Huffmanův algoritmus (ani Burrows-Whellerova transformace) není patentován, narozdíl od většiny ostatních kompresních algoritmů (např. slovníkové metody, aritmetické kódování, nebo dokonce RLE).
Příště se tedy podíváme na adaptivní Huffmanův kód, který je o něco málo složitější než statický, což je ovšem vyváženo lepším kompresním poměrem.
Líbil se vám článek?
3.8 (5x hodnoceno)
Přidejte si článek do oblíbených
linkuj.cz
del.icio.us
rss - HOWTOKomentáře
Sarka - 27. duben 2009, 13:38
obrazky
Bylo by mozne pridat i obrazky? Diky
pokus - 19. leden 2013, 22:34
pokus
pokus
jojo - 8. červen 2009, 18:24
jo
jo
asd
Budou i obrázky?
K. - 26. červen 2009, 14:29
test
test
Celkem pěkné, málokde je tak pěkné vysvětlení.
ca1 - 3. duben 2008, 15:24
appended variation of algorithm
[max...min] stack of to_be_done
[min...max] front of waiting_for (contains sorted for sum of 2 minimal in stack gets >= previous 2 minimal ;)
* while 1 < count
* choose 2 smallest from front & stack
* remove them from stack & front and insert to back of front
ja - 11. říjen 2010, 21:43
jkfaj
jj
w0t - 15. listopad 2010, 16:51
thx
Tonda - 29. listopad 2008, 17:40
obrázky
Bohužel chybí obrázky.
Tonda - 29. listopad 2008, 17:40
obrázky
Zajímavé, hned po odeslání komentáře se objevily. Předtim ani F5 nepomohlo.
PataS - 28. prosinec 2009, 14:33
jj
Díky za článek :)
