Kanonski Hafmanov kod

Kanonski Hafmanov kod je posebna vrsta Hafmanovog koda sa jedinstvenim svojstvima koji omogućavaju da bude opisan na vrlo kompaktan način.

Kompresori podataka obično rade na jedan od dva načina. Ili dekompresor može zaključiti, iz prethodnog konteksta, koji je šifrarnik kompresor koristio, ili kompresor mora reći dekompresoru koji je šifrarnik koristio. Budući da kanonski Hafmanov šifrarnik može da bude efikasno memorisan, većina kompresora započne stvaranje "normalnog" Hafmanovog šifrarnika, a zatim ga pre upotrebe konvertuje u kanonski Hafmanov kod.

Da bi šifrarnik poput Hafmanovog koda bio dekompresovan, isti model kodiranja podataka koji je korišten za kompresiju izvornih podataka mora biti dostavljen algoritmu za dekodiranje, tako da može da bude upotrebljen za dekompresiju kodiranih podataka. U standardnom Hafmanovom kodu ovaj model uzima oblik stabla za promenljive dužine kodova, tako da se najučestaliji simboli nalaze na vrhu strukture i predstavljeni su najmanjim brojem bitova.

Međutim, ovo kodno stablo uvodi dve kritične neefikasnosti pri realizaciji šifrarnika. Prvo, svaki čvor stabla mora da čuva ili reference njegovih potomaka ili simbol koji ih predstavlja. Ovo je veoma skupo jer zauzima dosta memorije i ako postoji visok procenat jedinstvenih simbola u izvornim podacima, onda na veličinu kodnog stabla može da otpada značajna količina od ukupnih kodiranih podataka. Drugo, prolaženje kroz stablo je računski skupo, jer zahteva od algoritama za nasumičan skok kroz strukturu da pamti kako se svaki bit kodiranih podataka učitava.

Kanonski Hafmanovi kodovi rešavaju ova dva problema stvaranjem kodova u jasnom standardnom formatu; svim kodovima date dužine se redom dodeljuju njihove vrednosti. To znači da umesto čuvanja kodnog stabla za dekompresiju su potrebne samo dužine kodova, što smanjuje veličinu kodiranih podataka. Pored toga, pošto su kodovi sekvencijalni, algoritam za dekodiranje može biti drastično pojednostavljen tako da bude računski efikasan.

Algoritam[uredi | uredi izvor]

Normalni Hafmanov algoritam za kodiranje dodeljuje kod promenljive dužine svakom simbolu alfabeta. Češće korišćenim simbolima će biti dodeljen kraći kod. Na primer, pretpostavimo da imamo sledeći nekanonski šifrarnik:

A = 11 
B = 0 
C = 101 
D = 100

Ovde su slovu A dodeljena dva bita, B ima jedan bit, a C i D imaju po tri bita. Da bi se napravio kanonski Hafmanov kod, kodovi su prenumerisani. Dužine u bitovima ostaju iste s tim što su kodovi sortirani prvo po dužini kodne reči, a zatim po abecednom redu:

B = 0 
A = 11 
C = 101 
D = 100

Svaki od postojećih kodova je zamenjen novim iste dužine, koristeći sledeći algoritam:

Prvom simbolu u listi dodeljuje se kodna reč koja je iste dužine kao prvobitna kodna reč simbola, ali zamenjena svim nulama. To će biti jedna nula ('0').
Svakom narednom simbolu je sekvencijalno dodeljen sledeći binarni broj, obezbeđujući da su sledeći kodovi uvek veće vrednosti.
Kada dostigne dužu kodnu reč, nakon uvećanja, dodajemo nule dok dužina nove kodne reči ne bude ista kao dužina stare. Ovo se može posmatrati kao pomeranje ulevo.

Prateći ova tri pravila, kanonska verzija će biti:

B = 0
A = 10 
C = 110 
D = 111

Kao razlomljeni binarni broj[uredi | uredi izvor]

Drugi izgled kanonskog šifrarnika je da su one cifre iza binarne tačke (binarni decimalni zarez) binarna reprezentacija određenog niza. Specijalno pretpostavimo da su dužine l₁,...,l_n. Onda je kanonska kodna reč za simbol i prva l_i binarna cifra iza binarne tačke u binarnoj reprezentaciji.

$\sum _{j=1}^{i-1}2^{-l_{j}}$

Ovakva perspektiva je posebno korisna imajući u vidu Kraftovu nejednakost koja kaže da će iznos iznad uvek biti manji od 1 (jer dužine dolaze iz slobodnog prefiksnog koda). Ovo pokazuje da dodavanjem jedinice u algoritmu iznad nikad ne stvara kodnu reč koja je duža nego što je predviđeno.

Kodiranje[uredi | uredi izvor]

Sva prednost kanonskog Hafmanovog stabla je da se može kodirati opis (kodna shema) u manje bita nego kompletno opisano stablo.

Uzmimo prvobitnu Hafmanov šifrarnik:

A = 11 
B = 0 
C = 101 
D = 100

Postoji nekoliko načina na koje možemo kodirati ovo Hafmanovo stablo. Na primer, možemo napisati svaki simbol, a zatim broj bitova i kod.

('A',2,11), ('B',1,0), ('C',3,101), ('D',3,100)

Pošto smo nabrojali simbole u sekvencijalnom abecednom redu, možemo izostaviti simbole, navodeći samo broj bitova i kod:

(2,11), (1,0), (3,101), (3,100)

Sa našom kanonskom verzijom znamo da su simboli u sekvencijalnom abecednom redu i da će vrednost narednog koda uvek biti veća od vrednosti prethodnog. Jedini deo koji je ostao za slanje je broj bitova za svaki simbol. Imajte na umu da kanonsko Hafmanovo stablo uvek ima veće vrednosti za simbole koji imaju veći broj bitova i da svaki simbol sa istim brojem bitova (C i D) ima veće vrednosti kodova za veće simbole:

A = 10    (вредност кода: 2 децимално, битова: 2) 
B = 0     (вредност кода: 0 децимално, битова: 1) 
C = 110   (вредност кода: 6 децимално, битова: 3) 
D = 111   (вредност кода: 7 децимално, битова: 3)

Pošto su poznate dve trećine ograničenja, samo broj bitova za svaki simbol treba da se prenese:

2, 1, 3, 3

Sa poznavanjem kanonskog Hafmanovog algoritma moguće je rekonstruisati celu tabelu (simbole i vrednosti koda) samo od broja bitova. Neiskorišćeni simboli se obično kodiraju kao da imaju nula bitova.

Još jedan efikasan način predstavljanja kodne sheme je nabrojati sve simbole u rastućem redosledu prema njihovom broju bitova i evidentirati broj simbola za svaki broj bitova. Na primer, iznad pomenuto kodiranje postaje:

(1,1,2), ('B','A','C','D')

To znači da je prvi simbol B dužine 1, zatim A dužine 2, a ostatak 3. Budući da su simboli sortirani po broju bitova možemo efikasno da rekonstruišemo šifrarnik. Pseudo kod koji predstavlja rekonstrukciju je predstavljen u sledećem odeljku.

Ovaj tip kodiranja ima velike prednosti kada je kompresovano samo nekoliko simbola u pismu. Na primer, ako šifrarnik sadrži samo četiri slova C, O, D i E, svaki dužine dva. Da bi predstavili slovo O koristeći prethodni metod trebalo bi da ili dodamo mnogo nula:

0, 0, 2, 2, 2, 0, ... , 2, ...

ili evidentirati koja četiri slova smo koristili. Svaki način čini opis duži od:

(0,4), ('C','O','D','E')

JPEG format je usvojio, zapravo, ovaj način kodiranja, jer, uglavnom, samo 162 simbola 8-bitne azbuke, koja ima veličinu 256, biće u šifrarniku.

Pseudo kod[uredi | uredi izvor]

S obzirom da je lista simbola razvrstana po broju bitova, sledeći pseudo kod prikazati kanonski Hafmanov kod:

code = 0
while more symbols:    
print symbol, code    
code = (code + 1) << ((broj bitova sledeceg simbola) - (trenutni broj bitova))

Algoritam[uredi | uredi izvor]

Algoritam opisan u "A Method for the Construction of Minimum-Redundancy Codes", Dejvid A. Hafman, izdavač I.R.E je:

израчунати Хафманов код: 
улаз: порука (комплет од (порука, вероватноћа)).
      основа D 
излаз: код (комплет од (порука, код)). 
алгоритам: 
1- сортирати поруке према опадајућој могућности. 
2- N је кардинал порука (број различитих порука)).
3- израчунати цео број n_0 као 2<=n_0<=D и (N-n_0)/(D-1) је цео број. 
4- изабрати n_0 поруке најмање вероватноће и доделити им свима цифре.
5- заменити одабране поруке поруком која је композиција њихових вероватноћа, и поновити га. 
6- док има више од једне поруке, извршавати до 8.
7- изабрати поруке са најмањом вероватноћом и доделити им свима цифре.
8- заменити одабране поруке поруком која је композиција њихових вероватноћа, и поновити га. 
9- код сваке поруке дат је спајањем кода цифара скупа који је уметнут.

Literatura[uredi | uredi izvor]

D.A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., September 1952, pp 1098–1102. Huffman's original article.
Ken Huffman. Profile: David A. Huffman, Scientific American, September 1991, pp. 54–58
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 978-0-262-03293-3. Section 16.3, pp. 385–392.