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

Adaptivní Huffmanovo kódování - FGK

Základní informace

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

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

V nejhorším případě (kódovací strom je nutné změnit po každém znaku v celé jeho hloubce) bude odhad operační složitosti O(n*log|Σ|), kde n je počet znaků ve zprávě a |Σ| je počet symbolů vstupní abecedy. Potom log |Σ| je zhruba hloubka stromu (strom nemusí být nutně vyvážený, nicméně pro jednoduchost lze takovéto zjednodušení použít).

Historie

Algortimus je založen na původním Huffmanově kódování. Nejstarší adaptivní algoritmus byl nezávisle publikován Fallerem (1973), později Gallagerem (1978). V roce 1985 provedl další obměnu tohoto algoritmu Knuth. Tento algoritmus dostal zkrácený název FGK.

Popis

Pro objasnění principu algoritmu je nutné uvést jednu definici:
Binární strom má sourozeneckou vlastnost jestliže každý uzel (s vyjímkou kořenu) má sourozence a pokud lze uzly seřadit do monotónní posloupnosti (podle četnosti daného uzlu) tak, že má každý uzel v posloupnosti za souseda svého sourozence.
Gallager potom dokázal, že binární prefixový kód je Huffmanovým kódem právě tehdy když má odpovídající kódovací strom sourozeneckou vlastnost. Algoritmus potom funguje na principu vkládání symbolů do stromu a v případě, že se podaří detekovat porušení sourozenecké vlastnosti se provede přeuspořádání stromu tak, aby byla sourozenecká vlastnost zachována.
Algoritmus má dvě varianty přístupu k abecedám:

  • Inicializace se všemi znaky abecedy - v tomto případě je strom na začátku nastaven tak, že obsahuje všechny znaky se zvolenou pravděpodobností
  • Použití uzlu ZERO - v tomto případě obsahuje počáteční strom pouze jediný uzel ZERO. Při načtení znaku, který dosud nebyl zakódován, se do výstupu vypíše kód uzlu zero a uzel se rozdělí na nový uzel ZERO a list s novým znakem.

Pseudokód


 1:  begin
 2:     vytvoř uzel ZERO
 3:     readSymbol(X)
 4:     while (X!=EOF) do 
 5:      begin
 6:        if (prvníNačteni(X)) then
 7:         begin
 8:           output(kód uzlu ZERO)
 9:           output(X)
10:           vytvoř nový uzel U s naslední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:        if (existuje uzel U1 se stejným ohodnocením a vyšším pořadím) then 
27:           vyměň U1 a U
28:        zvyš ohodnocení U o 1
29:        U := předek(U)
30:      end
31:     zvyš ohodnocení U o 1, aktualizuj kódy listů
32:  end

Odkazy

  1. Adaptive Huffman coding - odkazy na dokumentaci, zdrojové kódy, implementace. Datacompression.info.
  2. Adaptive Huffman coding. Codepedia, the developers encyclopedia.

Ukázka