Huffmanův kód

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. ledna 2019; kontroly vyžadují 27 úprav .

Huffmanův algoritmus je chamtivý algoritmus pro optimální prefixové kódování abecedy s minimální redundancí . Byl vyvinut v roce 1952 postgraduálním studentem MIT Davidem Huffmanem při psaní semestrální práce . V současné době se používá v mnoha programech pro kompresi dat .

Na rozdíl od Shannon-Fano algoritmu zůstává Huffmanův algoritmus vždy optimální pro sekundární abecedy m 2 s více než dvěma znaky.

Tato metoda kódování se skládá ze dvou hlavních kroků:

Konstrukce optimálního kódového stromu.
Vytvoření mapování kód-symbol na základě vytvořeného stromu.

Klasický Huffmanův algoritmus

Myšlenka algoritmu je následující: se znalostí pravděpodobnosti výskytu znaků ve zprávě je možné popsat postup pro konstrukci kódů s proměnnou délkou sestávajících z celého čísla bitů. Znakům je pravděpodobnější přiřadit kratší kódy. Huffmanovy kódy mají vlastnost prefix (to znamená, že žádné kódové slovo není prefixem jiného), což umožňuje jejich jednoznačné dekódování.

Klasický Huffmanův algoritmus přijímá tabulku četností znaků ve zprávě jako vstup. Dále je na základě této tabulky zkonstruován Huffmanův kódovací strom (H-strom). [jeden]

Znaky vstupní abecedy tvoří seznam volných uzlů. Každý list má váhu, která se může rovnat buď pravděpodobnosti, nebo počtu výskytů znaku ve zprávě, která má být komprimována.
Jsou vybrány dva volné uzly stromu s nejmenší váhou.
Jejich rodič je vytvořen s váhou rovnou jejich celkové hmotnosti.
Rodič je přidán do seznamu volných uzlů a jeho dva potomci jsou z tohoto seznamu odstraněni.
Jeden oblouk vycházející z rodiče je nastaven na bit 1, druhý na bit 0. Bitové hodnoty větví pocházejících z kořene nezávisí na vahách potomků.
Kroky počínaje druhým se opakují, dokud v seznamu volných uzlů nezůstane pouze jeden volný uzel. Bude považován za kořen stromu.

Řekněme, že máme následující tabulku absolutních frekvencí:

Symbol	ALE	B	V	G	D
Absolutní frekvence	patnáct	7	6	6	5

Tento proces si lze představit jako vytvoření stromu , jehož kořenem je symbol se součtem pravděpodobností kombinovaných symbolů získaných kombinací symbolů z posledního kroku, jeho n 0 potomky jsou symboly z předchozího kroku atd. .

Abychom určili kód pro každý ze znaků obsažených ve zprávě, musíme přejít od listu stromu odpovídajícího aktuálnímu znaku k jeho kořenu, přičemž při pohybu po větvích stromu shromažďujeme bity (první větev v cestě odpovídá nejméně významnému bitu). Takto získaná sekvence bitů je kód daného znaku, zapsaný v obráceném pořadí.

Pro danou tabulku znaků budou Huffmanovy kódy vypadat takto.

Symbol	ALE	B	V	G	D
Kód	0	100	101	110	111

Vzhledem k tomu, že žádný z přijatých kódů není prefixem druhého, lze je při čtení ze streamu jednoznačně dekódovat. Kromě toho je nejčastější symbol zprávy A kódován nejmenším počtem bitů a nejvzácnější symbol D je kódován největším.

V tomto případě bude celková délka zprávy sestávající ze symbolů uvedených v tabulce 87 bitů (průměrně 2,2308 bitů na symbol). Při použití jednotného kódování by celková délka zprávy byla 117 bitů (přesně 3 bity na znak). Všimněte si, že entropie zdroje, který nezávisle generuje symboly se zadanými frekvencemi, je ~2,1858 bitů na symbol, což je redundance Huffmanova kódu konstruovaného pro takový zdroj, chápaná jako rozdíl mezi průměrným počtem bitů na symbol a entropie, je menší než 0,05 bitu na symbolu.

Klasický Huffmanův algoritmus má řadu významných nevýhod. Za prvé, aby bylo možné obnovit obsah komprimované zprávy, musí dekodér znát frekvenční tabulku používanou kodérem. Proto je délka komprimované zprávy zvýšena o délku frekvenční tabulky, která má být odeslána před daty, což může popřít jakoukoli snahu o komprimaci zprávy. Kromě toho potřeba mít kompletní statistiku frekvence před zahájením skutečného kódování vyžaduje dva průchody zprávou: jeden pro vytvoření modelu zprávy (tabulka frekvencí a H-strom), druhý pro skutečné kódování. Za druhé, redundance kódování zmizí pouze v těch případech, kdy pravděpodobnosti zakódovaných symbolů jsou převrácené mocniny 2. Za třetí, pro zdroj s entropií nepřesahující 1 (například pro binární zdroj), přímá aplikace Huffmanova kódu je zbytečné.

Adaptivní komprese

Adaptivní komprese vám umožňuje nepřenášet model zprávy spolu s ním a omezit se na jeden průchod zprávou jak při kódování, tak při dekódování.

Při vytváření adaptivního Huffmanova kódovacího algoritmu vznikají největší potíže při vývoji postupu pro aktualizaci modelu o další znak. Teoreticky by bylo možné do této procedury jednoduše vložit kompletní konstrukci Huffmanova kódovacího stromu, nicméně takový kompresní algoritmus by měl nepřijatelně nízký výkon, protože sestavení H-stromu je příliš pracné a je nerozumné to dělat při zpracování každá postava. Naštěstí existuje způsob, jak upravit již existující H-strom, aby odrážel zpracování nové postavy. Nejznámější přestavbové algoritmy jsou Voller-Gallagher-Knuth (FGK) algoritmus a Witterův algoritmus.

Všechny algoritmy pro přestavbu stromu při čtení dalšího znaku zahrnují dvě operace:

Prvním je zvýšení hmotnosti uzlů stromu. Nejprve zvýšíme váhu listu odpovídající čtenému znaku o jednu. Poté zvýšíme váhu rodiče, aby byla v souladu s novými váhami dětí. Tento proces pokračuje, dokud se nedostaneme ke kořeni stromu. Průměrný počet přírůstků váhy se rovná průměrnému počtu bitů potřebných k zakódování znaku.

Druhá operace - permutace uzlů stromu - je vyžadována, když zvýšení hmotnosti uzlu vede k porušení vlastnosti uspořádání, to znamená, že zvýšená hmotnost uzlu je větší než váha následujícího uzlu v objednat. Pokud budeme pokračovat ve zpracování přírůstku hmotnosti a budeme se pohybovat směrem ke kořeni stromu, pak strom již nebude Huffmanovým stromem.

Aby se zachovalo pořadí kódovacího stromu, algoritmus funguje následovně. Nechť je nová zvýšená hmotnost uzlu W+1. Poté se začneme po seznamu pohybovat ve směru rostoucí váhy, dokud nenajdeme poslední uzel s váhou W. Přeuspořádejme mezi sebou v seznamu aktuální a nalezené uzly, čímž obnovíme pořadí ve stromu (v tomto případě rodiče každého z uzlů se také změní). Tím je operace swap dokončena.

Po permutaci pokračuje operace zvyšování hmotnosti uzlů dále. Další uzel, kterému algoritmus zvýší váhu, je nový rodič uzlu, jehož zvýšení hmotnosti způsobilo permutaci.

Kanonické Huffmanovy kódy

Problémem konvenčního Huffmanova kompresního algoritmu je nedeterminismus. Pro podobné sekvence mohou vzniknout různé stromy a jeden strom bez řádné serializace může odpovídat různým sekvencím. Aby se zabránilo použití kanonických Huffmanových kódů.

Tento algoritmus nevytváří Huffmanův strom [2] .

Skládá se ze dvou fází:

Výpočet délky kódu pro nějaký znak
Skládání kódu.

Výpočet délky

Vypočítejte frekvenci pro každý znak
Seřaďte je v lexikografickém pořadí.
Zapišme frekvenci každého písmene do pole.
Vlevo přiřadíme pole stejné délky, ale se sériovými čísly z pole vpravo. Levé pole se získá jako seznam ukazatelů na prvky pravé strany.
Na levé straně vytvoříme nerostoucí pyramidu . Ale halda nebude podle hodnoty prvků pole, ale podle hodnoty odkazovaného prvku pole.
Prvek nejvíce vlevo ukazuje na znak z pravého pole s nejnižší frekvencí. Dá se odstranit takto:
1. Nedotýkejte se pravé poloviny
2. Nahradíme první prvek pole prvkem zcela vpravo levého pole, čímž se údajně posune hranice separace.
3. Zkontrolujeme podmínky pro správnost pyramidy, pokud je něco špatně, musíme opakovat „hipizaci“.
4. První prvek z levé strany pole je odstraněn a dříve odstraněný prvek je zkombinován. Součet jejich frekvencí je zapsán na hranici mezi levým a pravým polem.
5. Místo smazaného prvku na levé straně se zapíše index pole tam, kde byl v posledním kroku přidán součet frekvencí.
6. Vzhledem k tomu, že byly zkombinovány dva prvky, je nutné změnit hodnoty těchto prvků pole s odkazem na rodiče, kam byly vloženy.
Opakujeme, v hromadě nezůstane 1 prvek.
Na pravé straně pole máme odkazy na prvky, které kombinují 2 znaky. Proto procházíme polem po odkazech a zvyšujeme úroveň ponoření.
Počet kliknutí na odkazy bude odpovídat délce Huffmanova kódu.

Kompilace kódu

Uspořádejte prvky v lexikografickém pořadí.
Udělejme tabulku skládající se z bloků, počínaje největší délkou kódu. Každý blok bude obsahovat prvky se stejnou délkou kódu.
Úplně první znak tabulky je zakódován nulami.
V každém bloku budou znaky v lexikografickém pořadí.
Kódy v bloku budou binární a budou se lišit o 1.
Při přechodu na další blok jsou kódové bity nejnovějšího znaku odříznuty a přidána 1.

Bigramový model

Existuje varianta Huffmanova algoritmu, který používá kontext. V tomto případě je velikost kontextu rovna jedné (bigram - dva znaky, trigram - tři atd.). Toto je metoda konstrukce předponového kódu pro modely vyššího řádu, který již není zdrojem bez paměti. Použije výsledek operace (předchozí operace) na předchozí písmeno spolu s aktuálním písmenem. Je postaven na bázi Markovova řetězce s hloubkou závislosti . [3] $r=1$

Algoritmus

Tabulka je konstruována ve formě čtverce - rozdělení pravděpodobnosti na bigramech. Okamžitě se vypočítá počáteční schéma, s jehož pomocí bude zakódováno pouze první písmeno. Řádky v tabulce jsou například předchozí písmena a sloupce jsou aktuální.
Pravděpodobnosti se počítají pro kódové stromy pro kontexty.
Délkové kontexty slouží k sestavení zbývajících kódových stromů, s jejichž pomocí budou zakódovány všechny ostatní znaky (kromě prvního). $r=1$
Provede se kódování, první znak se zakóduje podle výchozího schématu, všechny následující znaky se zakódují na základě kódových stromů pro kontexty (předchozí znak).

Dekódování se provádí podobným způsobem: ze schématu počátečního kódu získáme první kontext a poté přejdeme do odpovídajícího stromu kódu. Navíc dekodér potřebuje tabulku rozdělení pravděpodobnosti.

Příklad

Řekněme, že zpráva, která má být zakódována, je „abcabcabc“ . Tabulku frekvence symbolů známe předem (na základě jiných dat, jako jsou statistiky slovníku).

	A	b	C	Součet
A	${\tfrac {3}{16}}$	${\tfrac {1}{16}}$	${\tfrac {1}{16}}$	${\tfrac {5}{16}}$
b	${\tfrac {1}{8))$	${\tfrac {1}{16}}$	${\tfrac {1}{8))$	${\tfrac {5}{16}}$
C	${\tfrac {1}{8))$	${\tfrac {1}{8))$	${\tfrac {1}{8))$	${\tfrac {6}{16}}$

Máme výchozí schéma: . Seřaďte sestupně: a vytvořte strom Huffmanových kódů. $(a={\tfrac {5}{16}},b={\tfrac {5}{16}},c={\tfrac {6}{16}})$ $(c={\tfrac {6}{16}},a={\tfrac {5}{16}},b={\tfrac {5}{16}})$

Pro kontext " a " máme:

$p(a/a)=p(a,a)/p(a)={\tfrac {3}{16}}\div {\tfrac {5}{16}}={\tfrac {3 {5}}$ ,
$p(b/a)=p(b,a)/p(a)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1 {5}}$ ,
$p(c/a)=p(c,a)/p(a)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1 {5}}$ .

Pro kontext " b " máme:

$p(a/b)=p(a,b)/p(b)={\tfrac {1}{8}}\div {\tfrac {5}{16}}={\tfrac {2 {5}}$ ,
$p(b/b)=p(b,b)/p(b)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1 {5}}$ ,
$p(c/b)=p(c,b)/p(b)={\tfrac {1}{8}}\div {\tfrac {5}{16}}={\tfrac {2 {5}}$ .

Pro kontext " c " máme:

$p(a/c)=p(a,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 {3}}$ ,
$p(b/c)=p(b,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 {3}}$ ,
$p(c/c)=p(c,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 {3}}$ .

Poznámka: zde p(x, y) není rovno p(y, x) .

Vytváříme kódové stromy pro každý kontext. Provádíme kódování a máme zakódovanou zprávu: (00, 10, 01, 11, 10, 01, 11, 10, 01).

00 - z kódu písmene "a" pro počáteční schéma,
10 - z kódu písmene "b" pro kontext "a" ,
01 - z kódu písmene "c" pro kontext "b" ,
11 - z kódu písmene "a" pro kontext "c" .

Přetečení

Jak kompresní algoritmus běží, váha uzlů v Huffmanově kódovacím stromě neustále roste. První problém nastává, když váha kořene stromu začne převyšovat kapacitu buňky, ve které je uložen. Obvykle se jedná o 16bitovou hodnotu, a proto nemůže být větší než 65535. Druhý problém, který si zaslouží více pozornosti, může nastat mnohem dříve, když velikost nejdelšího Huffmanova kódu překročí kapacitu buňky, která se používá k jeho přenosu do výstupní proud. Dekodér se nestará o to, jak dlouho kód dekóduje, protože se pohybuje shora dolů po stromě kódování a vybírá jeden bit po druhém ze vstupního toku. Kodér na druhé straně musí začínat na listu stromu a pohybovat se nahoru ke kořenu a sbírat bity, které mají být přenášeny. To se obvykle děje s proměnnou typu integer, a když délka Huffmanova kódu překročí velikost typu integer v bitech, dojde k přetečení.

Lze dokázat, že Huffmanův kód pro zprávy se stejnou vstupní abecedou bude mít maximální délku, pokud frekvence symbolů tvoří Fibonacciho posloupnost . Zpráva s frekvencemi symbolů rovnými Fibonacciho číslům až Fib(18) je skvělý způsob, jak otestovat, jak funguje Huffmanův kompresní program.

Měřítko vah uzlů Huffmanova stromu

Vezmeme-li v úvahu výše uvedené, algoritmus aktualizace Huffmanova stromu by měl být změněn následujícím způsobem: jak se váha zvyšuje, je třeba zkontrolovat, zda dosáhl povoleného maxima. Pokud jsme dosáhli maxima, pak je třeba váhu „rozměřit“, obvykle tak, že váhu listů vydělíme celým číslem, například 2, a pak přepočítáme váhu všech ostatních uzlů.

Při dělení hmotnosti na polovinu však nastává problém spojený s tím, že po provedení této operace může strom změnit svůj tvar. To se vysvětluje tím, že při dělení celých čísel se zlomková část zahodí.

Správně organizovaný Huffmanův strom po změně měřítka může mít tvar, který se výrazně liší od původního. Je to proto, že změna měřítka vede ke ztrátě přesnosti ve statistikách. Se sběrem nových statistik však důsledky těchto „chyb“ prakticky mizí. Váhové škálování je poměrně nákladná operace, protože vede k nutnosti přestavět celý kódovací strom. Ale protože potřeba toho vzniká poměrně zřídka, můžete se s tím smířit.

Výhody škálování

Měřítko váhy uzlů stromu v určitých intervalech dává neočekávaný výsledek. I když při škálování dochází ke ztrátě statistické přesnosti, testy ukazují, že škálování vede k lepšímu výkonu komprese, než kdyby bylo škálování zpožděno. To lze vysvětlit tím, že současné symboly stlačitelného proudu jsou více „podobné“ svým blízkým předchůdcům než těm, které se vyskytovaly mnohem dříve. Změna měřítka má za následek snížení vlivu „starých“ symbolů na statistiku a zvýšení vlivu „nedávných“ symbolů na ni. To je velmi obtížné kvantifikovat, ale v zásadě má škálování pozitivní vliv na stupeň komprese informací. Experimenty se změnou měřítka v různých bodech procesu komprese ukazují, že stupeň komprese silně závisí na okamžiku změny měřítka hmotnosti, ale neexistuje žádné pravidlo pro výběr optimálního momentu změny měřítka pro program zaměřený na kompresi jakéhokoli typu informací.

Aplikace

Huffmanovo kódování je široce používáno v kompresi dat, včetně komprese fotografií a videa ( JPEG , MPEG ), v oblíbených archivátorech ( PKZIP , LZH atd.), v protokolech přenosu dat HTTP ( Deflate ), MNP5 a MNP7 a dalších.

Úpravy

V roce 2013 byla navržena modifikace Huffmanova algoritmu, která umožňuje kódování znaků se zlomkovým počtem bitů - ANS [4] [5] . Na základě této úpravy vznikly kompresní algoritmy Zstandard (Zstd, Facebook, 2015—2016) [6] a LZFSE (Apple, OS X 10.11, iOS 9, 2016) [7] [8] [9] [10] jsou implementovány .

Poznámky

↑ D. Mastryukov. Monitor 7-8.93 Archivováno 17. května 2018 na Wayback Machine
↑ Algoritmus je podrobně popsán s příklady v Managing Gigabytes od Witten, Moffat, Bell na straně 68.
↑ Shmuel T. Klein a Dana Shapira. Huffmanovo kódování s netříděnými frekvencemi (2008). Datum přístupu: 2. ledna 2016. Archivováno z originálu 4. března 2016. (neurčitý)
↑ Archivovaná kopie . Získáno 2. ledna 2016. Archivováno z originálu 5. března 2016. (neurčitý)
↑ Archivovaná kopie . Staženo 2. ledna 2016. Archivováno z originálu 11. září 2016. (neurčitý)
↑ Facebook zveřejnil implementaci kompresního algoritmu Zstandard 1.0 Archivováno 2. září 2016 na Wayback Machine / Opennet.ru, 09/01/2016
↑ Apple zahájil implementaci algoritmu bezeztrátové komprese LZFSE
↑ Apple Open-Sourses svůj nový kompresní algoritmus LZFSE . Získáno 1. září 2016. Archivováno z originálu 11. září 2016. (neurčitý)
↑ Komprese dat
↑ GitHub - lzfse/lzfse: Knihovna pro kompresi LZFSE a nástroj příkazového řádku . Získáno 1. září 2016. Archivováno z originálu 28. listopadu 2020. (neurčitý)

Literatura

Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmy: konstrukce a analýza = Úvod do algoritmů. - 2. vyd. — M .: Williams , 2006. — 1296 s. — ISBN 0-07-013151-1 .
D. Salomon. Komprese dat, obrázků a zvuku. - M .: Technosfera, 2004. - 368 s. - 3000 výtisků. — ISBN 5-94836-027-X .
Ian H. Witten, Alistair Moffat, Timothy C. Bell. Správa gigabajtů: Komprese a indexování dokumentů a obrázků. - 1999. - 551 s. — ISBN 1558605703 .
Levitin A. V. Kapitola 9. Greedy Methods: The Huffman Algorithm // Algorithms. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 392-398. — 576 s. — ISBN 978-5-8459-0987-9

Markov A. A. Úvod do teorie kódování. — M .: Nauka, 1982. — 192 s.

Odkazy

Kompresní metody

Teorie

Informace	Vlastní Vzájemné Entropie Podmíněná entropie Složitost Nadbytek
Jednotky	Bit Nat Okusovat Hartley Hartleyho vzorec

Bezztrátový

Entropická komprese	Asymetrické číselné soustavy Huffmanův algoritmus Adaptivní Huffmanův algoritmus Shannon-Fano algoritmus Shannonův algoritmus Aritmetické kódování ( interval ) Golombovy kódy Delta Univerzální kód Eliáš fibonacci
Slovníkové metody	RLE Vyfouknout LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
jiný	RLE CTW BWT MTF PPM DMC

Zvuk

Teorie	Konvoluce PCM Aliasing Vzorkování Kotelnikovova věta
Metody	LPC LAR LSP WLPC CELP ACELP Zákon μ-zákon ADPCM MDCT Fourierova transformace Psychoakustický model
jiný	Audio kompresor Komprese řeči Pásmové kódování

snímky

Podmínky	barevný prostor Pixel Saturační podvzorkování Kompresní artefakty
Metody	RLE DPCM fraktál vlnka EZW SPIHT LP Přípravka PCL
jiný	Bitová rychlost Standardní testovací obrázek PSNR Kvantování

Video

Podmínky	Vlastnosti videa Rám Typy rámů Kvalita videa
Metody	Kompenzace pohybu Přípravka Kvantování vlnka
jiný	Video kodek Teorie zkreslení sazby CBR ABR VBR