Adaptivní Huffmanův algoritmus

Adaptivní Huffmanovo kódování (také nazývané dynamické Huffmanovo kódování ) je adaptivní metoda založená na Huffmanově kódování . Umožňuje sestavit kódové schéma v režimu streamování (bez předběžného skenování dat), bez jakýchkoli počátečních znalostí z původní distribuce, což umožňuje komprimovat data v jediném průchodu. Výhodou této metody je možnost kódování za chodu.

Algoritmy

Existuje několik implementací této metody, nejpozoruhodnější je "FGK" (FGK: Voller, Gallagher a Knuth ) a Witterův algoritmus.

Algoritmus FGK

Umožňuje vám dynamicky upravovat Huffmanův strom bez počátečních frekvencí. FGD Huffmanův strom má speciální vnější uzel, nazývaný 0-node , který se používá k identifikaci příchozích znaků. To znamená, že kdykoli se objeví nový znak, jeho cesta ve stromu začíná od nulového uzlu. Nejdůležitější je, že v případě potřeby musíte zkrátit a vyvážit FGD Huffmanův strom a aktualizovat frekvenci přidružených uzlů. Se zvyšující se frekvencí symbolu se musí zvyšovat i frekvence všech jeho rodičů. Toho je dosaženo postupnou permutací uzlů, podstromů nebo obou.

Důležitým rysem stromu FGD je princip bratrství (neboli rivality): každý uzel má dvě děti (uzly bez dětí se nazývají listy) a váhy jsou v sestupném pořadí. Díky této vlastnosti lze strom uložit do běžného pole, což zvyšuje výkon. [1] [2]

Witterův algoritmus

Kód je reprezentován jako stromová struktura, ve které má každý uzel přiřazenou váhu a jedinečné číslo.

Čísla klesají a zprava doleva.

Závaží musí splňovat princip bratrství. Pokud je tedy A rodič B a C je potomkem B, pak .

Váha je jen počet dosud naražených postav.

Sada uzlů se stejnými váhami je blok .

Abychom získali kód pro každý uzel, v případě binárního stromu bychom mohli jednoduše projít všechny cesty od kořene k uzlu a napsat například „1“, pokud půjdeme doprava, a „0“, pokud jděte doleva.

Také tento algoritmus používá speciální list (uzel bez potomků), NYT (z angličtiny dosud nevysílaný - dosud nepřenesený znak), ze kterého „vyrůstají nové, dříve neviděné znaky“.

Kodér a dekodér začínají pouze u kořenového uzlu, který má maximální váhu. Na začátku je to náš NYT uzel.

Když předáme znak NYT, musíme nejprve předat kód samotného uzlu a poté data.

Pro každý symbol, který je již ve stromu, musíme předat pouze kód koncových uzlů (listů).

Pro každý vysílaný znak provedou vysílač a přijímač postup aktualizace:

1. Pokud není aktuální symbol nalezen, přidejte dva podřízené uzly do NYT: jeden pro další NYT a druhý pro symbol. Zvyšte váhu nového listu a starého NYT a přejděte ke kroku 4. Pokud aktuální symbol není NYT, přejděte na list symbolů.
2. Pokud tento uzel nemá nejvyšší váhu v bloku, zaměňte jej za uzel s nejvyšším číslem, pokud tento uzel není nadřazený [3]
3. Zvýšení váhy pro aktuální uzel
4. Pokud to není kořenový uzel, přejděte na nadřazený uzel a poté přejděte ke kroku 2. Pokud se nejedná o kořenový uzel, dokončete.

Poznámka: Nahrazení uzlů znamená nahrazení vah a odpovídajících symbolů, nikoli čísel.