Huffmanovo kodiranje

Iz MaFiRaWiki

Vsebina

Kratek opis problema

Tekstovne datoteke lahko stisnemo tako, da zamenjamo pogosto ponavljajoče se besede s krajšimi simboli. Eden izmed načinov takega kodiranja je Huffmanovo kodiranje. Huffmanovo kodiranje je dobilo ime po Davidu Huffmanu, ki je leta 1952 objavil članek, v katerem je opisal metodo.

Opis algoritma

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 prevelikem š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:


a b c d e f
Frekvenca 4500 1300 1200 1600 900 500
Koda - fiksna dolžina 000 001 010 011 100 101
Koda - spremenljiva dolžina 0 101 100 111 1101 1100


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.

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, dT(c) pa naj označuje globino znaka c v dvojiškem drevesu. Seveda je dT(c) tudi dolžina kodne besede za znak c. Število potrebnih bitov je torej


B(T) = 3c0C f(c) dT(c) , (1)

kar definiramo kot ceno drevesa T.

Gradnja Huffmanove kode

Huffman je napisal požrešen algoritem, ki konstruira optimalno kodo s predpono, t.i. Hoffmanovo kodo.

Na kratko lahko postopek opišemo takole:

  • znake uredimo po pripadajočih verjetnostih (frekvenco znaka delimo s številom vseh znakov),
  • najmanj verjetnima znakoma dodelimo vrednosti bitov 0 in 1 ter ju združimo v skupni simbol
    z vsoto njunih verjetnosti,
  • izmenično ponavljamo prva dva koraka, dokler ne preostaneta le še dva simbola, ki jima
    dodelimo še zadnja bita 0 in 1,
  • kodna beseda za posamezen znak se prebere v obratni smeri, kot smo dodeljevali bite


Naj bo C nabor n znakov, tako da ima vsak znak c0C frekvenco f(c). Z algoritmom zgradimo drevo T, ki predstavlja optimalno kodo. Drevo zgradimo od spodaj navzgor tako, da iz množice | C | listov izvedemo | C | − 1 "združevanj". Pri tem uporabimo vrsto s prednostjo Q, ki je vezana na frekvence f. Najprej poiščemo dva najredkeje zastopana znaka in ju združimo. Dobimo nov objekt s frekvenco, ki je enaka vsoti frekvenc obeh znakov, ki smo ju združili.

Algoritem je zapisan v psevdo kodi:

Huffman(C)

1 n = |C| // število znakov

2 Q = C // vrsta postane kar nabor vseh znakov

3 for i=1 to n-1

4 do določi novo vozlišče z

5 levo[z] = x = poišči-min(Q) // v vrsti Q poiščemo in izločimo vozlišče z najmanjšo frekvenco

6 desno[z] = y = poišči-min(Q) // v vrsti Q poiščemo in izločimo naslednje vozlišče z najmanjšo frekvenco

7 f[z] = f[x] + f[y]

8 dodaj(Q,z) // v vrsto Q dodamo vozlišče z

9 return poišči-min(Q) // vrne koren drevesa


V drugi vrstici inicializiramo vrsto s prednostjo Q - vanjo dodamo vse znake iz nabora C. Zanka for (vrstice 3-8) poišče in izloči po dve vozlišči z najmanjšima frekvencama (x, y) in ju nadomesti z združenim vozliščem z. Frekvenca z je kar vsota frekvenc x in y (vrstica 7). Vozlišče z ima levega sina x in desnega y. (Če ju zamenjamo, dobimo kodo z enako ceno.) Po n − 1 korakih imamo v vrsti le še eno vozlišče - koren drevesa.

Če že imamo podane frekvence, je časovna zahtevnost Huffmanovega algoritma naslednja: za inicializacijo vrste je O(n) (vrstica 2), for zanka pa se izvede (n − 1)-krat. Vsaka operacija nad vrsto zahteva O(logn), torej je časovna zahtevnost algoritma O(nlogn).

Program predstavi stiskanje podatkov tako, da dano besedilo "stisne" v dvojiški zapis. V tem zapisu so ničle in enke "standardni" znaki. Če bi želeli v resnici stisniti podatke, bi morali "dvojiški" zapis pretvoriti v bite.

Glej tudi


Viri

Osebna orodja