Huffmanovo kódování

Huffmanův strom vygenerovaný pro přesné frekvence výskytu textu "TO JE PŘÍKLAD Huffmanova stromu". Frekvence a kódy každého znaku jsou uvedeny níže. Kódování této 41znakové fráze pomocí tohoto kódu vyžaduje 156 bitů (bez započítání místa pro strom), když 8bitové bajty vyžadují 328 bitů.

Charakter Frekvence Kód Prostor 8 00 A 6 100 N 3 1100 BUĎ 3 1110 NEBO 3 0100 A dva 0101 D dva 1010 F dva 1011 L dva 0110 M dva 0111 Ano dva 11010 B. 1 110110 H 1 110111 J 1 111100 P 1 111101 R 1 111110 T 1 111111

V informatice a teorii informace je Huffmanovo kódování algoritmus používaný pro kompresi dat . Termín odkazuje na použití tabulky s proměnnou délkou kódu pro zakódování určitého symbolu (jako je znak v souboru), kde byla tabulka vyplněna specifickým způsobem na základě odhadované pravděpodobnosti výskytu každé možné hodnoty tohoto symbolu. symbol. Byl vyvinut Davidem A. Huffmanem , když byl doktorandem na MIT , a publikován v „Metodě pro konstrukci kódů minimální redundance“.

Huffmanovo kódování používá specifickou metodu pro výběr reprezentace každého symbolu, což má za následek prefixový kód (tj. bitový řetězec představující konkrétní symbol není nikdy předřazen bitovému řetězci jiného symbolu), který představuje nejběžnější znaky pomocí nejkratší bitové řetězce a naopak. Huffman byl schopen vymyslet nejúčinnější kompresní metodu tohoto druhu: žádná alternativní reprezentace sady vstupních symbolů neprodukuje menší průměrný výstup, když frekvence symbolů odpovídají frekvencím použitým k vytvoření kódu. Později byla nalezena metoda, jak toho dosáhnout v lineárním čase, pokud jsou seřazeny pravděpodobnosti vstupních symbolů (také známé jako „váhy“).

Pro skupinu symbolů s rovnoměrným rozdělením pravděpodobnosti a počtem členů, který je mocninou dvou, je Huffmanovo kódování ekvivalentní binárnímu blokovému kódování, například kódování ASCII . Huffmanovo kódování je tak rozšířená metoda vytváření prefixových kódů, že termín „Huffmanovo kódování“ je široce používán jako synonymum pro „prefixový kód“, i když takový kód nebyl vytvořen pomocí Huffmanova algoritmu.

Ačkoli je Huffmanovo kódování optimální pro kódování symbol po symbolu dané rozdělením pravděpodobnosti, jeho optimalita může být někdy náhodně nadhodnocena. Například aritmetické kódování a kódování LZW obvykle nabízejí vyšší možnosti komprese. Tyto dvě metody mohou seskupit libovolný počet symbolů pro efektivnější kódování a jsou obecně přizpůsobeny skutečným vstupním statistikám. To je užitečné, když pravděpodobnosti nejsou přesně známy nebo se v rámci datového toku výrazně liší.

Historie

V roce 1951 si David Huffman a jeho spolužáci v předmětu „Teorie informací“ mohli vybrat mezi složením závěrečné zkoušky nebo přednesením referátu. Profesor Robert. M. Fano zadal podmínky práce za předpokladu nalezení nejefektivnějšího binárního kódu. Huffman, který nebyl schopen prokázat, který kód byl efektivnější, to vzdal a začal se učit na závěrečnou zkoušku. Zatímco v tomto procesu přišla na mysl myšlenka použití uspořádaných frekvenčních binárních stromů a rychle dokázal, že je to nejúčinnější metoda.

Touto studií Huffman porazil svého profesora, který spolupracoval s vynálezcem informačních teorií Claudem Shannonem na vývoji podobného kódu. Huffman opravil většinu chyb v kódovacím algoritmu Shannon-Fano. Řešení bylo založeno na procesu budování stromu zdola nahoru místo obráceně.

Definice problému

Neformální popis

Kostky

Sada symbolů a jejich vah (obvykle úměrné pravděpodobnosti).

Nalézt

Prefixový binární kód ( soubor prvků kódu) s minimální očekávanou délkou slova (ekvivalentně strom s minimální délkou cesty).

Formální popis

Vstupenky

Abeceda , což je abeceda symbolů velikosti . Množina , což je množina (kladných) vah symbolů (obvykle úměrných pravděpodobnostem), tzn . $A=\left\{a_{1},a_{2},\cdots ,a_{n}\right\}$$n$
$W=\left\{w_{1},w_{2},\cdots ,w_{n}\right\}$$w_{i}=\mathrm {váha} \left(a_{i}\right),1\leq i\leq n$

Odchod

Kód , což je množina prvků (binárního) kódu, kde je kódové slovo pro . $C\left(A,W\right)=\left\{c_{1},c_{2},\cdots ,c_{n}\right\}$$c_{i}$$a_{i},1\leq i\leq n$

Fotbalová branka

Nechť je vážená délka cesty kódu . Podmínka: pro jakýkoli kód . $L\left(C\right)=\sum​​i=1}^{n}{w_{i}\times \mathrm {length} \left(c_{i}\right)}$$C$$L\left(C\right)\leq L\left(T\right)$$T\left(A,W\right)$

Příklad

Vstup ( A , W )	symbol ( ai )	A	b	C	d	a	Přidání
	Hmotnost ( w i )	0,10	0,15	0,30	0,16	0,29	= 1
Výstup C	kódová slova ( c i )	010	011	jedenáct	00	10
	Délka slova (v bitech) ( l i )	3	3	dva	dva	dva
	Vážená délka cesty ( l i w i )	0,30	0,45	0,60	0,32	0,58	L ( C ) = 2,25
optimalita	Pravděpodobnost (2 - l i )	1/8	1/8	1/4	1/4	1/4	= 1,00
	Množství informace (v bitech) (− log 2 w i ) ≈	3.32	2,74	1,74	2.64	1,79
	Entropie (− w i log 2 w i )	0,332	0,411	0,521	0,423	0,518	H ( A ) = 2,205

Pro jakýkoli kód 1: 1, tento jedinečně dekódovatelný kód , je součet pravděpodobností všech symbolů vždy menší nebo roven jedné. V tomto příkladu se přesně rovná jedné; takže říkáme, že je to úplný kód . Pokud tomu tak není, lze ekvivalentní kód vždy odvodit přidáním dalších symbolů (s přidruženými nulovými pravděpodobnostmi), aby byl kód úplný a přitom zůstal jeden ku jedné .

Jak definoval Shannon (1948) , množství informace h (v bitech) každého symbolu ai _s nenulovou pravděpodobností w _i je

$h(a_{i})=\log{2}{1 \over w_{i}}.$

Entropie H (v bitech ) je vážený součet všech symbolů a _i s nenulovou pravděpodobností w _i množství informací v každém symbolu:

$H(A)=\sum​​w_{i}>0}w_{i}h(a_{i})=\sum​​w_{i}>0}w_{i}\log​​ 2}{1 \over w_{i}}=-\sumw_{i}>0}w_{i}\log2}{w_{i}}.$

(Poznámka: symbol s nulovou pravděpodobností má nulový příspěvek k entropii. Když w = 0, jedná se o neurčitost; použijeme L'Hôpitalovo pravidlo  : $w\log 2}(1/w)=0\cdot \infty$

$\lim​​w\to 0^{+}}{\frac {\log{2}{\frac {1}{w}}}{\frac {1}{w}}}=\ lim w\to 0^{+}}{\frac {-{\frac {1}{w\ln 2}}}{-{\frac {1}{w^{2}}}}}= \lim w \to 0^{+}}{\frac {w}{\ln 2}}=0$.

Pro zjednodušení byly z výše uvedeného vzorce vynechány symboly s nulovou pravděpodobností.)

V důsledku Shannonova teorému o zdrojovém kódování je entropie mírou nejmenší délky kódového slova, která je teoreticky možná pro danou abecedu s přidruženými váhami. V tomto příkladu je průměrná délka slova 2,25 bitů na symbol, o něco větší než vypočítaná entropie 2,205 bitů na symbol. Nejenže je tedy tento kód optimální v tom smyslu, že žádný jiný možný kód nefunguje lépe, ale také se velmi blíží teoretickému limitu stanovenému Shannonem.

Všimněte si, že obecně Huffmanův kód nemusí být jedinečný, ale pokud ano, je to vždy jeden z kódů, který minimalizuje . $L(C)$

Základní technika

Použitá technika je samotný Huffmanův algoritmus . Skládá se z vytvoření binárního stromu , ve kterém jsou listové uzly označeny znaky spolu s jejich frekvencemi, a postupně se spojí každá dvojice uzlů, které se sčítají méně často, čímž se vytvoří nový mezilehlý uzel označený uvedeným součtem. Tato akce se provádí, dokud nezůstanou žádné listové uzly, které by se daly připojit k jakémukoli nadřazenému uzlu, a dokud se nevytvoří binární strom.

Následně jsou hrany, které spojují každý z uzlů, označeny nulami a jedničkami (například pravý a levý potomek). Výsledný kód pro každý znak je čtení po větvi od kořene ke každému znaku (nebo naopak) každého z popisků hran.

Stavba stromu

Pro získání Huffmanových kódů je nutné sestavit binární strom uzlů, vycházející ze seznamu uzlů, jehož velikost závisí na počtu symbolů, . Uzly obsahují dvě pole, symbol a váhu (četnost výskytu). $n$

Každý uzel ve stromu, což jsou informace, které se velmi opakují, může být buď „listový“ uzel , nebo „interní“ uzel . Zpočátku jsou všechny uzly v počátečním seznamu považovány za listové uzly stromu. Po sestavení stromu budou mít vnitřní uzly váhu a dva podřízené uzly a volitelně odkaz na nadřazený uzel , který lze použít k procházení stromu v obou směrech. Podle konvence je bit '0' spojen s levou větví a bit '1' s pravou. Po dokončení bude strom obsahovat podřízené uzly a vnitřní uzly . $n$ $n-1$

Proces konstrukce stromu začíná vytvořením mezilehlého uzlu, který seskupuje dva listové uzly, které mají nejnižší váhu (frekvenci výskytu). Nový mezilehlý uzel bude mít tyto dva listové uzly jako podřízené uzly a jeho váhové pole se bude rovnat součtu vah podřízených uzlů. Dva podřízené uzly se odstraní ze seznamu uzlů a nahradí je novým mezilehlým uzlem. Proces se opakuje, dokud v seznamu nezůstane pouze jeden uzel. Tento poslední uzel se stane kořenovým uzlem Huffmanova stromu.

Algoritmus konstrukce stromu lze shrnout takto:

1. Vytvořte listový uzel pro každý symbol, přiřaďte váhu podle četnosti jeho výskytu a vložte jej do seznamu ve vzestupném pořadí.
2. Pokud je v seznamu více než jeden uzel:
   1. Odeberte dva nejméně pravděpodobné uzly ze seznamu.
   2. Vytvořte nový interní uzel, který se propojí s předchozími uzly, a jako váhu přiřaďte součet vah podřízených uzlů.
   3. Vložte nový uzel do seznamu (na místo, které mu odpovídá podle hmotnosti).
3. Uzel, který zůstane, je kořenový uzel stromu.

Zde je příklad stavby stromu z francouzského textu „j'aime aller sur le bord de l'eau les jeudis ou les jours empairs“:

Hlavní vlastnosti

Použité pravděpodobnosti mohou být obecné pro doménu aplikace, které jsou založeny na průměrné velikosti písmen, nebo to mohou být skutečné frekvence nalezené v komprimovaném textu. (Tato varianta vyžaduje, aby frekvenční tabulka nebo jiná struktura použitá pro kódování byla uložena s komprimovaným textem; implementace využívají různé mechanismy pro efektivní ukládání tabulek.)

Huffmanovo kódování je optimální, když pravděpodobnost každého vstupního symbolu je záporná mocnina dvou. Předponové kódy bývají mírně neefektivní na malých abecedách, kde jsou pravděpodobnosti obvykle mezi těmito optimálními body. „Sbalení“ neboli rozšíření velikosti abecedy zřetězením více symbolů do „slov“ pevné nebo proměnné velikosti před Huffmanovým kódováním obvykle pomáhá, zvláště když jsou sousední symboly korelovány (jako v textu v přirozeném jazyce). Nejhorší případ pro Huffmanovo kódování může být, když pravděpodobnost symbolu překročí 2 ^-1 = 0,5, takže horní mez neefektivity je neomezená. Tyto situace často dobře reagují na formu paketu nazývanou run-length encoding .

Aritmetické kódování vytváří mírný zisk oproti Huffmanově kódování, ale v praxi byl tento zisk jen zřídka dostatečně velký na to, aby bylo možné použít aritmetické kódování, které má vyšší výpočetní složitost a také vyžaduje licenční poplatky . (Od července 2006 je IBM držitelem patentů na mnoho metod aritmetického kódování v různých jurisdikcích.)

Variace

Existuje mnoho variant Huffmanova kódu, některé používají Huffmanův algoritmus a jiné, které nalézají optimální prefixový kód. Všimněte si, že v druhém případě metoda nemusí být nutně Huffmansova a nemusí končit v polynomiálním čase .

Huffmanův n-ary kód

Huffmanův n-ární algoritmus používá abecedu {0,1,….,n-1} pro zakódování zprávy a sestavení n-árního stromu. Tento přístup zvážil Huffman ve svém původním přístupu.

Adaptivní Huffmanův kód

Variace zvaná adaptivní Huffmanův kód dynamicky vypočítává pravděpodobnost frekvence zdrojového řetězce na základě minulých výskytů. Souvisí s rodinou algoritmů LZ.

Šablona Huffmanův algoritmus

Ve většině případů je velikost implementací Huffmanova kódu reprezentována numerickými pravděpodobnostmi, ale algoritmus to nevyžaduje; je vyžadován pouze jeden způsob, jak objednat velikost a přidat k ní. Huffmanův šablonový algoritmus vám umožňuje použít jakýkoli typ velikosti (náklady, frekvence, páry velikostí, nenumerické velikosti) a jednu z mnoha metod kombinování (nejen sčítání). Takové algoritmy mohou vyřešit problémy minimalizace, jako je minimalizace Max[Wi + C(i)], problém poprvé použitý při návrhu obvodů.

Huffmanův kód v omezené velikosti

Velikostně omezený Huffmanův kód je varianta, kde je cílem dosáhnout cesty s minimálními náklady s omezením, že délka každého slova je menší než konstanta. Algoritmus slučování balíčků to řeší pomocí hrabivého algoritmu , velmi podobného tomu, který používá Huffmanův algoritmus. Jeho složitost je v řádu O(nL), kde L je velikost nejdelšího slova. Není znám žádný algoritmus, který by řešil tento problém v lineárním čase, na rozdíl od konvenčních Huffmanových problémů.

Huffmanovo kódování s nestejnými náklady

Ve standardním problému Huffmanova kódování se předpokládá, že každý symbol abecedy, ze kterého je každé kódové slovo vytvořeno, má stejné přenosové náklady: kódové slovo o délce N číslic bude mít vždy cenu N , bez ohledu na to, kolik z těchto číslic jsou nuly, kolik jich je atd. Při práci za tohoto předpokladu je minimalizace celkových nákladů na zprávu a minimalizace celkového počtu číslic stejná.

V Huffmanově kódování s nestejnými náklady již neplatí předchozí předpoklad: znaky abecedy mohou mít nestejnoměrnou délku kvůli vlastnostem přenosového média. Příkladem je abeceda Morseovy abecedy , kde 'pomlčka' vyžaduje více času k odeslání než 'tečka', a proto jsou náklady na dobu přenosu pomlčky vyšší. Cílem je stále minimalizovat průměrnou délku kódového slova, ale nestačí minimalizovat počet symbolů použitých ve zprávě. Není znám žádný algoritmus, který by to řešil stejným způsobem nebo se stejnou účinností jako konvenční Huffmanovo kódování.

Optimální abecední binární stromy (kódování Hu–Tucker)

Ve standardní situaci Huffmanova kódování se předpokládá, že jakýkoli kód může odpovídat libovolnému vstupnímu symbolu. V abecední verzi musí být abecední pořadí vstupů a výstupů shodné. Vstupu tedy například nelze přiřadit , ale spíše nebo . Toto je také známé jako Hu-Tuckerův problém podle autorů publikace, která obsahuje první linearitmické řešení tohoto alfabetického binárního problému optimality, který je podobný, ale ne variací, Huffmanovu algoritmu. Tyto optimální abecední binární stromy se často používají jako binární vyhledávací stromy . $A=\left\{a,b,c\right\}$$H\left(A,C\right)=\left\{00,1,01\right\}$$H\left(A,C\right)=\left\{00,01,1\right\}$$H\left(A,C\right)=\left\{0,10,11\right\}$

Kanonický Huffmanův kód

Pokud jsou váhy odpovídající (abecedním) záznamům v číselném pořadí, Huffmanovy kódy mají stejnou délku jako optimální abecední kódy, takže je lze vypočítat jako posledně uvedené, takže Hu-Tucker kódování není nutné. Kód vyplývající z numericky (pře)uspořádaných vstupů je známý jako kanonický Huffmanův kód a je to kód běžně používaný v praxi, vzhledem k jeho snadnému kódování a dekódování. Technika hledání tohoto kódu je známá jako Huffman–Shannon–Fano kódování , protože je optimální jako Huffmanovo kódování a abecední podle pravděpodobnosti vah, jako Shannon–Fano kódování.

Tímto způsobem kódovací metoda Huffman-Shannon-Fano postupně přiřazuje kratší prefixové kódy těm symbolům s vyšší váhou a ty nejdelší těm s nižší váhou. To znamená, že seřadí symboly sestupně podle jejich hmotnosti, poté zakóduje podle metody Shannon-Fano Encoding , jakmile je kódování získáno, sestaví se vývojový diagram , který začíná dotazem, zda hodnota prvního bit prefixu získaného pro Hledaný symbol je 0, ze kterého vycházejí 2 větve, jedna pro afirmaci a druhá pro negaci; pak bude pokračovat v dotazování na druhý bit a odvozovat pro každou větev další rozhodnutí nebo symbol, podle potřeby.

Aplikace

Aritmetické kódování lze považovat za zobecnění Huffmanova kódování, ve skutečnosti aritmetickému kódování předchází Huffmanovo kódování, protože je snazší najít aritmetiku pro binární vstup než pro nebinární. Na druhou stranu, i když kompresní kódování nabízí lepší výkon než Huffmanovo kódování, Huffmanovo kódování je stále široce používáno díky své jednoduchosti, vysoké rychlosti a nedostatku patentových problémů .

Huffmanovo kódování se často používá v některé jiné kompresní metodě. Jako deflace a multimediální kodeky jako JPEG a MP3 , které mají digitální kvantizaci založenou na Huffmanově kódování.

Příklad

Vesmírná sonda byla vypuštěna do vesmíru, aby spočítala určité typy hvězdných poruch. Musí spočítat, kolik se jich stane každou minutu, a každý den má poměrně krátké časové okno na odeslání dat na Zemi ; proto je zajímavé co nejvíce zkrátit dobu přenosu a pro tento účel jsou vzorky kódovány pomocí Huffmanova kódu.

Následující tabulka ukazuje hodnoty, které mají být přenášeny, spolu s jejich relativními frekvencemi, jejich kód ve 3bitovém binárním kódování a jejich kód v možném Huffmanově kódu pro tyto hodnoty.

Hodnota	Frekvence	Binární kód	Huffmanův kód
0	10 %	000	010
1	dvacet%	001	10
dva	30 %	010	00
3	25 %	011	jedenáct
4	10 %	100	0110
5 nebo více	5 %	101	0111

Je vidět, že v binárním kódování dostávají všechny možné hodnoty kódy o stejném počtu bitů, zatímco v Huffmanově kódování má každá hodnota jiný počet bitů: nejčastější kódy mají dva bity, zatímco ty nejméně časté Mají čtyři bity.

Níže je uveden kód potřebný k přenosu následující řady hodnot:

5,4,2,3,2,2,1,0,1,3,2,4,3,4,3,2,3,4,2,4

Při použití binárního kódování by to byl 60bitový řetězec; tedy 3 bity na symbol.

101100010011010010001000001011010100011100011010011100010100

poznámka: stejná série rozdělená do bloků byla přidána pouze z důvodu usnadnění bezchybného ručního přepisu pro studium zainteresovaným čtenářům.

101.100.010.011.010.010.001.000.001.011.010.100.011.100.011.010.011.100.010.100

Při použití Huffmanova kódování by musela být odeslána 53bitová sekvence; to znamená 2,65 bitů na symbol.

01110110001100001001010110001101101101100110110000110

poznámka: stejný řetězec rozdělený do 4bitových bloků pro stejné pozorování jako výše.

0111.0110.0011.0000.1001.0101.1000.1101.1011.0110.0110.1100.0011.0

V tomto příkladu je průměrný počet bitů na symbol, který byste od tohoto kódování očekávali, na delších hodnotových řetězcích 2,4.

Pro srovnání, entropie sady symbolů je 2,366; to znamená, že nejlepší kompresní metoda by byla schopna zakódovat tyto hodnoty pomocí 2 366 bitů na symbol.

Je také možné vidět, jak lze původní hodnoty jednoznačně extrahovat z Huffmanem zakódovaného řetězce.

Je třeba dodat, že Huffmanovo kódování nelze použít na černobílé obrázky, protože není schopno vytvořit kompresi na binární abecedu .

Bibliografie

• DA Huffman, "Metoda pro konstrukci kódů minimální redundance," Proceedings of the IRE, září 1952, str. 1098-1102

Viz také

• Huffmanův algoritmus
• Huffmanův kanonický kodex
• aritmetické kódování

Externí odkazy

• Huffmanův stromový generátor
• Huffmann v PHP