English
předchozí hlavní stránka obsah další

Adaptivní Huffmanovo kódování - Vitterův algoritmus ( Λ )

Základní informace

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

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

Historie

Klasické Huffmanovo kódování nejprve upravili Faller, Gallager a Knuth na rychlejší algoritmus, nazývaný dle prvních písmen jejich jmen FGK. Další úpravu představil Jeffrey Scott Vitter v roce 1987. Je podobná algoritmu FGK, ale používá trochu jiný způsob upravování stromu a v určitých případech tak dává lepší výsledky.

Popis

Základ algoritmu Λ je stejný jako u FGK algoritmu. Při kódování (i dekódování) udržujeme strom, který jako listy obsahuje všechny doposud se vyskytující znaky a vnitřní uzly obsahující součty četností výskytu jednotlivých znaků ve svých podstromech. Dále je ve stromu speciální uzel (list) ZERO, jehož kód slouží jako uvozující escape sekvence při výskytu nového znaku.

Pokud k zakódování přijde znak, který se již ve stromě jako list vyskytuje, vypíšeme na výstup kód tohoto listu a dále aktualizujeme strom (viz níže). Jestliže se jedná o první výskyt znaku, na výstup vypíšeme kód uzlu ZERO jako escape sekvenci uvozující první výskyt znaku, který dáme na výstup též (v dohodnutém formátu). Dále vytvoříme ve stromu v místě uzlu ZERO nový vnitřní uzel, který bude jako své potomky obsahovat uzel ZERO a nový list, reprezentující právě kódovaný znak. Následuje opět postupná aktualizace celého stromu. Aktualizace začíná zdola od naposledy se vyskytujícího znaku (1.případ) nebo od nově vytvořeného uzlu (2.případ). Nejprve je nutno určit blok, který ve stromě předchází aktualizovaný uzel. Blok uzlů je skupina uzlů, které mají stejné ohodnocení (četnost) a jsou všechny stejného typu - vnitřní uzly nebo listy. Jestliže je splněna příslušná podmínka na přesun (viz pseudokód), uzel se přesune před blok (rotace vlevo) a dále se pokračuje vyšším stupněm.

Rozdíl mezi FGK algoritmem a Vitterovou úpravou Huffmanova kódování je možno vidět na následujícím případě. Při kódování sekvence znaků abacabdabaceabacabdf vytvoří (i když ne zcela stejným postupem) oba algoritmy shodný strom. Jestliže je dalším písmenem G, dávají ale rozdílné výsledky, oproti FGK je Vitterův strom vyvázenější. Tento výsledek zobrazují obrázky:

FGK:
FGK 		Vitter:
Vitter

Pseudokód


 1:  begin
 2:     Inicializuj 
 3:     readSymbol(X)
 4:     while (X!=EOF) do 
 5:      begin
 6:        if (první_načtení(X)) then 
 7:         begin
 8:           output(kód uzlu ZERO) 
 9:           output(X)
10:           vytvoř nový uzel U s následníky ZERO a list s X
11:           aktualizuj_strom(U);
12:         end
13:        else
14:         begin
15:           output(kód uzlu s X)
16:           aktualizuj_strom(uzel s X)
17:         end
18:        readSymbol(X)
19:     end
20:  end 
21:    
22:  procedure aktualizuj_strom(U)
23:  begin
24:     while (U!=kořen) do 
25:      begin
26:        b := blok nasledující uzel U
27:        if ((U je list) a (b je blok vnitřních uzlu) a (ohodnocení U == ohodnocení b))
28:          or ((U je vnitřní uzel) a (b je blok listů) a (ohodnocení U == ohodnocení b - 1)) then
29:         begin
30:           předsuň U před blok b
31:           zvyš ohodnocení U o 1
32:           if (U je list) then 
33:              U := předek(U)
34:           else 
35:              U := předek (U před předsunem)
36:         end
37:        else
38:         begin
39:           zvyš ohodnocení U o 1
40:           U := předek(U)
41:         end
42:      end
43:     zvyš ohodnocení U o 1
44:  end

Odkazy a literatura

  1. Oficiální stránky J. S. Vittera
  2. J. S. Vitter: Design and analysis of dynamic Huffman codes. Journal of ACM 34, 4 (Oct. 1987), 825-845
  3. J. S. Vitter: Algorithm 673 Dynamic Huffman Coding. ACM Transactions on Mathematical Software, 15(2), červen 1989, 158-167
  4. Adaptive Huffman coding. Wikipedia, the free encyclopedia.
  5. Popis adaptivního Hufmannova kódování - FGK a Vitter

Ukázka