Hafmanovi kodovi
U oblasti komunikacija i računarske tehnike, Hafmanovo kodiranje predstavlja algoritam za kodiranje simbola bez gubitka informacija. Iako je Hafmanovo kodiranje vrlo efikasno postoje algoritmi koji koriste relacije između pojedinih simbola i na taj način poboljšavaju efikasnost algoritma. Hafmanov kod se bazira na redundansi po kojoj se određeni karakteri češće javljaju od ostalih. Hafmanovi kodovi redukuju broj bitova koji se šalju, ali je kod njih neophodno znati vednost verovatnoće pojavljivanja.
Istorijat
urediHafmanov algoritam je nastao 1953. Razvio ga je Dejvid Hafman dok je bio na doktorskim studijama na MIT i objavio u radu "A Method for the Construction of Minimum-Redundancy Codes".
Hafmanov algoritam
uredi
Cilj Hafmanovog algoritma je minimizacija težinske eksterne dužine puta što u stvari predstavlja zbir proizvoda nivoa i težina za sve eksterne čvorove stabla.
Hafmanov algoritam kreće od šume h stabala sa po jednim eksternim čvorom. U svakoj iteraciji iz reda u kome se nalaze stabla vade se dva korena sa najmanjim težinama, zatim se pravi čvor sa težinom koja je jednaka zbiru težina izabranih čvorova. Sada je novonastali čvor koren novog stabla čiji su levo i desno podstablo izabrana dva čvora. Novonastalo stablo se sada vraća u red i u novim iteracijama konkuriše ravnopravno sa ostalim stablima. U svakoj novoj iteraciji se uzimaju nova dva korena od kojih se pravi novo stablo sa korenom čija je težina jednaka zbiru težina korena izabranih stabala. Ovako se u svakoj iteraciji smanjuje broj stabala za jedan sve dok u redu ne ostane samo jedno stablo. Ako na početku imamo šumu od h stabala, potrebna nam je h-1 iteracija da bi dobili krajnje stablo. Ovakvo stablo ima koren čija je težina jednaka zbiru težina svih eksternih čvorova koji su se na početku nalazili u redu, a koji takođe sada čine listove novonastalog stabla. Ovako nastalo stablo ima minimalnu težinsku eksternu dužinu puta.
Ovo je pohlepni algoritam i može se generalizovati i na stabla višeg reda. S obzirom da u redu može postojati više elemenata sa istom težinom onda može postojati i više stabala sa istom minimalnom težinskom eksternom dužinom puta. Međutim ako želimo da dobijemo stablo koje ujedno ima i najmanju visinu stabla onda elemente sa istom težinom treba da uklanjamo po FIFO redosledu.
Ovo stablo služi kao model donošenja binarnih odluka. Listovi su konačne odluke i ne dolazi se do svih istom verovatnoćom. Stablo realizuje optimalnu proceduru odlučivanja.
Složenost algoritma je u najboljem slučaju О(хlog х). Složenost zavisi od implementacije reda i najefikasnije je kada se red implementira kao binarni heap.
Hafmanovi kodovi
uredi
Koriste se za kompresiju podataka. Kompresijom podataka prilikom čuvanja ili prenosa se štedi na memoriji. Jedan od primera su poruke koje čine azbučna slova. Prilikom kodovanja poruke mora se voditi računa da procesi kodovanja i dekodovanja budu jednostavni, a opet dužina poruke treba da bude minimalna. Svaki simbol se predstavlja nekim binarnim kodom. Sada se za svaki simbol mora odrediti verovatnoća Rh. U ovom slučaju je najbolje da to bude verovatnoća pojavljivanja datog simbola. Zbir svih verovatnoća mora naravno da bude 100. Svaki znak može da ima proizvoljan kod. Zbog lakog dekodovanja koriste se prefiksni kodovi. To znači da kod ni jednog simbola ne sme da se koristi kao početak koda nekog drugog simbola. Proces dekodovanja se sada svodi na to da se kreće od početka binarne sekvence i uzima onoliko znakova koliko je potrebno da se dobije validan kod.
Prefiksni kodovi se dobijaju primenom Hafmanovog algoritma pa se takvi kodovi još nazivaju i Hafmanovim kodovima. Sada svaki simbol predstavlja eksterni čvor koji se stavlja u red i od kojih se gradi stablo. Težine ovih čvorova su, u stvari, njihove verovatnoće pojavljivanja. U stablu dobijenom primenom Hafmanovog algoritma listovi su zadati simboli. Binarni kod svakog simbola dobija se kao putanja od korena do tog simbola tako što svaki put kada se ide ulevo podstablo nekog čvora u kod se ubacuje 0, a kada se ide udesno podstablo u bacuje se 1. U binarnom stablu put do svakog eksternog čvora je jedinstven pa smo time obezbedili da dobijeni kodovi budu prefiksni
Osobine Hafmanovog kodiranja
urediHafmanovo kodiranje pronalazi optimalan sistem kodiranja zasnovan na relativnoj verovatnoći pojavljivanja svakog elementa. Predstavlja entropijsko kodiranje simbola bez gubitka informacija. Hafmanovo kodiranje je najefikasniji metod kompresije simbola koji nisu u tesnom odnosu, u svojoj klasi. On pripada klasi preslikavanja karaktera neke tekstualne kolekcije u bitove za poznate verovatnoće pojavljivanja svakog karaktera. Najduži Hafmanov kod se dobija kada se distribucija verovatnoća pojavljivanja odvija po pravilu generisanja Fibonačijevih brojeva.
Vrste Hafmanovog kodiranja
urediNa osnovu toga da li su verovatnoće pojavljivanja simbola poznate unapred ili se dinamički dobijaju tokom izvršavanja algoritma, Hafmanov algoritam se deli na statički i dinamički.
Statičko Hafmanovo kodiranje
urediNa početku se gradi tabela verovatnoća pojavljivanja znakova koje kodiramo. Tabela treba da bude uređena. Karakteri koji se češće javljaju kodiraju se kraćim sekvencama, a oni koji se ređe koriste kodiraju se dužim sekvencama. Sada se primenjuje Hafmanov algoritam na osnovu tabele.
Dinamičko Hafmanovo kodiranje
uredi
Za razliku od statičkog kodiranja gde se tabela verovatnoća pojavljivanja znakova određuje na početku rada algoritma kod dinamičkog se verovatnoće pojavljivanja izračunavaju i menjaju dinamički u toku rada algoritma.
Primer rada algoritma
uredi
Literatura
uredi- D.A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., September (1952). стр. 1098–1102. Huffman's original article.
- Ken Huffman. Profile: David A. Huffman, Scientific American, September (1991). стр. 54–58
- Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest & Clifford Stein (2001). Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Section 16.3. стр. 385–392.
