Czestina Huffmanovo kódování TNT's HomePage Algoritmy komprese dat

Huffmanovo kódování

Jde o velmi známou statistickou (využívá různé četnosti znaků) metodu. Na stejném základě pracuje také velmi podobné Shannon-Fanovo a Aritmetické kódování.

Algoritmus byl navržen Davidem Huffmanem roku 1952. Toto kódování využívá optimálního (nejkratšího) prefixového (kód žádného znaku není prefixem jiného) kódu. Přiřadí tedy častěji se vyskytujícím znakům kratší kódy (např. 2 bity místo původních 8) a naopak. Délky kódů jednotlivých znaků jsou celočíselné, to však nemusí být ideální (místo 6 bitů by bylo výhodnější např. 5.25 bitu). Lepšího výsledku se tedy dosáhne kódováním n-tic znaků (k "zaokrouhlování" na celý bit dochází méně často), tím však prudce rostou nároky na pamět, zatímco výsledný kompresní poměr se zlepšuje jen velmi pomalu.

Výhody této metody jsou velmi rychlá komprese i dekomprese a nepříliš velké nároky na paměť. Nevýhodou je nutnost uložení binárního stromu a slabší kompresní poměr (algoritmus si nevšímá opakování řetězců). Toto kódování se někdy používá pro zlepšení účinnosti některé slovníkové metody.

Komprese

Popis algoritmu:

  1. Zjištění četnosti jednotlivých znaků ve zdrojovém souboru.
  2. Vytvoření binárního stromu (Huffmanova kódu jednotlivých znaků).
    Toto je jediný bod, který se liší od Shannon-Fanova kódování.
    jednotlivé znaky označíme za vrcholy grafu (listy stromu)
      a dáme je do seznamu S
    while (S.length>1) {
      v S nalezneme dva vrcholy m, n s nejmenšími počty výskytů
      p = new Vrchol;
      p.left = m; p.right = n;
      p.count = m.count + n.count;	// count je # výskytů
      S.remove(m, n); S.add(p);
    }
    S obsahuje kořen stromu 
    najdeme kódy jednotlivých znaků (při průchodu z kořene do listu
    kódujeme 0 při kroku vlevo a 1 vpravo)
    
    Demonstrační program (Java Applet)
    
    Příklad:
    Vstupní soubor: ABRAKADABRA
    
    Vytvořený strom
    Jednotlivé znaky	 A       B       D       K       R
    Počty výskytů		(5)     (2)     (1)     (1)     (2)
    			  \       \       \     /       /
    			   \	   \       0   1       /
    			    \	    \       \ /       /
    			     \	     \      (2)      /
    			      \	      \     /       /
    			       \       0   1       /
    			        \       \ /       /
    				 \      (4) 	 /
    				  \       \     /
    				   \       0   1
    				    \       \ /
    				     \	    (6)
    				      \     /
    				       0   1
    				        \ /
    				       (11)
    
    
  3. Uložení stromu

    Jeden z možných způsobů uložení binárního stromu je následující:
    Začneme listem úplně nalevo a kódujeme přechod k dalšímu vrcholu (0=dolů=ke kořenu, 1=nahoru=k listům). Každý kód by se tedy skládal z několika počátečních nul a následovaly by jedničky. Počet úvodních nul je vždy zřejmý (ve stromu se pohybujeme dolů, tj. zapisujeme nuly, dokud nenarazíme na vrchol, jehož pravý následník ještě nebyl zapsán. Potom následuje jednička (nahoru doprava). A dále několik jedniček (nahoru vlevo) a právě tyto jedničky je nutno zapsat (a ukončit nulou).

    Strom z předchozího příkladu by tedy byl zakódován těmito sedmi bity:

    A B DKR
    1101000
    
    Takto je ale uložen jen tvar stromu, je ještě nutné označit listy příslušnými znaky. Například tak, že každý n-tý vrchol je následován nulou, pokud za n-tým použitým znakem je opět použitý znak, nebo jedničkou a počtem následujích nepoužitých vrcholů. Tím je určeno jaké znaky se ve zdrojovém souboru vyskytují, zbývá ještě určit jejich permutaci na listech stromu. Při procházení stromu jsou znaky, které neodpovídají příslušným listům, ukládány do seznamu. Pro každý list nastane a je zapsána identifikace jedné z těchto tří možností:
  4. n-tý list reprezentuje n-tý použitý znak
  5. n-tý list reprezentuje menší než n-tý použitý znak
    Správné číslo znaku je tedy již v seznamu a stačí zapsat index do tohoto seznamu. Číslo n-tého listu je potom zapsáno na konec seznamu.
  6. n-tý list reprezentuje větší než n-tý použitý znak
    Správné číslo tedy bude v seznamu až při zpětném chodu. Na konec zakódovaného stromu je zapsán index do seznamu při zpětném chodu. Na konec seznamu je opět přidáno číslo n-tého listu.

  7. Vlastní komprese: Nahrazení znaků jejich kódy.

Dekomprese

  1. Načtení a obnovení stromu, algoritmus je popsán při kompresi
  2. Vlastní dekomprese: Nahrazení kódů původními znaky.
    v = vrchol stromu
    while (!eof(input)) do {
      b = read bit
      if (b==0) v = v.left
      else v = v.right
      if (v je list) {
        write v.value	// znak reprezentovany tímto listem
        v = vrchol stromu
      }
    }
    

Dynamická verze Huffmanova kódování se označuje FGK (Faller, Gallagher, Knuth). Tato modifikace je sice pomalejší než statická, ale nevyžaduje ukládání stromu a adaptuje se na změny charakteru souboru a může tak dosáhnout lepšího kompresního poměru. Po zakódování (případně dekódování) každého znaku se strom upraví podle nových četností. Znaky, které v okamžiku kódování ve stomu nebyly, se uvedou speciálním znakem (escape), a do stromu zařadí. Začíná se tedy se stromem obsahujícím pouze speciální znak.
Last change Mar 24 1997 by TNT