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 c 0 C 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.
Za naš primer je gradnja drevesa prikazana na sliki 2. Ker je v naši abecedi 6 znakov, je začetna dolžina vrste 6, potrebujemo pa 5 korakov, da zgradimo drevo.
Slika 2. Koraki Huffmanovega algoritma za podatke iz Tabele 1. Vsaka slika prikazuje stanje vrste s prednostjo glede na frekvence. Na vsakem koraku združimo dve poddrevesi z najmanjšima frekvencama. Listi so pravokotniki, v njih pa je naveden znak in frekvenca le-tega. Notranja vozlišča so v krogih, v njih pa je zapisana vsota frekvenc obeh sinov. Povezave na leve sinove so označene z 0, na desne pa z 1. Kodna beseda za znak pa je zaporedje oznak na povezavah, ki vodijo od korena drevesa do izbranega lista/znaka. (a) začetna množica znakov, (b)-(e) vmesni koraki, (f) zgrajeno Huffmanovo drevo za naš primer.
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(log n), torej je časovna zahtevnost algoritma O(nlogn).