26: Huffmanovo kodiranje

Huffmanovo kodiranje je pogosto uporabljan in učinkovit način stiskanja podatkov. Običajno lahko pri stiskanju podatkov prihranimo med 20% in 90%, odvisno od tipa podatkov. Prihranku je potrebno odšteti še shranjevanje in/ali prenašanje Huffmanovega drevesa, ki ga potrebujemo za dekodiranje. Pri večjih datotekah in ne previkem številu znakov pa to lahko skoraj zanemarimo.

Za podatke vzemimo kar zaporedje znakov - besedilo. Običajno je tako besedilo zapisano v naboru znakov s fiksno dolžino dvojiškega zapisa (npr. ASCII - 7 bitov, Unicode - 16 bitov). V ASCII naboru ima npr. črka 'A' dvojiško kodo 1000001 oziroma 65 v desetiškem zapisu.

Za razliko od standarnega kodiranja s fiksno dolžino kode Huffmanovo kodiranje uporablja spremenljivo dolžino kode v dvojiškem zapisu.  Zato lahko znake, ki se v danem besedilu pogosteje pojavljajo zakodiramo s krajšim zapisom, redkeje zastopane znake pa z daljšim. Seveda moramo v obeh primerih (fiksna in spremenljiva dolžina dvojiškega zapisa) zagotoviti enoličnost zapisa.

Primer:

Recimo, da imamo datoteko s 10.000 znaki, ki jo želimo pretvoriti v dvojiški zapis. V datoteki nastopa le šest različnih znakov (a, b, c, d, e in f), pogostost pa je podana v spodnji tabeli:

Tabela 1. Kodiranje s fiksno in spremenljivo dolžino za dano frekvenco.

Seveda obstaja veliko načinov, kako predstavimo tako datoteko. Poglejmo si dva.

Za kodiranje s fiksno dolžino v tem primeru za vsak znak zadostujejo trije biti (a=000, b=001, c=010, d=011, e=100). S tem zapisom porabimo 30.000 bitov za celotno datoteko. Lahko ta rezultat še popravimo?

Če znakom, ki se pojavljajo pogosteje določimo čim krajšo kodo, manj pogostim pa daljšega, lahko prihranimo precej prostora. V zgornji tabeli je podan primer take kode za dane podatke (kasneje bomo videli, da je to tudi optimalno kodiranje za to datoteko), kjer za znak a potrebujemo samo en bit, za znake b, c in d po tri bite, za kodiranje znakov e in f pa potrebujemo štiri bite.

Glede na dane podatke, lahko torej izračunamo, koliko bitov potrebujemo za zapis:

4500*1 + 1300*3 + 1200*3 + 1600*3 + 900*4 + 500*4 = 22.400 bitov

Torej smo prihranili približno 25% prostora glede na prvi način. Če bi v prvem načinu uporabili kar standarden ASCII zapis, pa bi bil prihranek še precej večji.

Kode s predpono (angl. prefix codes)

Zanimale nas bodo le take kode zankov, kjer nobena kodna beseda ni predpona kakšne druge kodne besede. Takšne kode imenujemo kode s predpono, čeprav bi jih bilo morda bolje imenovati brezpredponske kode, saj posamezne kode niso predpone... V [1] je navedeno, da optimalno stiskanje podatkov z znakovno kodo vedno dosežemo s kodami s predpono. Tako se lahko omejimo le na kode s predpono.

Kodiranje je precej enostavno za dvojiške zankovne kode: nizu v dvojiškem zapisu (kodi) dodamo kodno besedo, ki predstavlja vsak posamezen znak v datoteki. Niz abc (s podatki iz zgornje tabele) lahko torej zapišemo 0101100.

Ker smo uporabili kode s predpono, je tudi dekodiranje precej lažje in še pomembnejše - enolično. Ker nobena kodna beseda ni predpona kakšne druge kodne besede, lahko hitro določimo katera je prva kodna beseda in jo pretvorimo nazaj v pripadajoč znak. To ponavljamo, doker ne dekodiramo vseh znakov v nizu. V našem primeru bi dvojiški zapis 001011101 razčlenili v 0.0.101.1101, oziroma aabe (druge možnosti sploh ni).

Pri dekodiranju potrebujemo primerno predstavitev kod s predpono, tako da lahko hitro najdemo kodne besede. Najprimernejša predstavitev je dvojiško drevo, v katerem so dani znaki listi. Dvojiško kodno besedo interpretiramo kot pot od korena drevesa do ustreznega lista, kjer 0 pomeni "pojdi do levega sina", 1 pa "pojdi do desnega sina". Na sliki 1 vidimo dvojiški drevesi za obe kodiranji iz našega primera.

Slika 1. Dvojiški drevesi za primer iz Tabele 1.
Levo je dvojiško drevo za kode s fiksno dolžino, desno pa Huffmanovo dvojiško drevo

Optimalno kodiranje je vedno predstavljeno s polnim dvojiškim drevesom, kjer ima vsako vozlišče, ki ni list, dva sinova. Drevo na levi (fiksna dolžina kode) ni optimalno, saj ni polno: nobena kodna beseda se ne začne na 11...

Zato lahko pozornost usmerimo na polna dvojiška drevesa. Za nek nabor znakov C (abeceda, števke, ločila, posebni in ostali znaki), ki imajo vsi pozitivno frekvenco velja, da ima optimalno dvojiško drevo kod s predpono natanko |C| listov in |C| - 1 notranjih vozlišč.

Za dano drevo T, ki predstavlja kodo s predpono, lahko hitro izračunamo število bitov za dano datoteko. Za vsak znak c iz nabora C naj bo f(c) frekvenca znaka c v datoteki, d_T(c) pa naj označuje globino znaka c v dvojiškem drevesu. Seveda je d_T(c) tudi dolžina kodne besede za znak c. Število potrebnih bitov je torej

B(T) = 3_c0C  f(c) d_T(c) ,        (1)

kar definiramo kot ceno drevesa T.