Huffmanovi kodovi: primjeri, aplikacije

Trenutačno malo ljudi razmišlja o tome kako kompresija funkcionira. U usporedbi s prošlošću, korištenje osobnog računala postalo je puno lakše. I praktički svaka osoba koja radi s datotečnim sustavom koristi arhive. No, malo ljudi razmišlja o tome kako rade i na koji princip je kompresija datoteka. Prva verzija tog procesa bila je Huffmanov kod, a oni se još koriste u raznim popularnim arhivatorima. Mnogi korisnici čak ni ne misle kako je lako komprimirati datoteku i prema tome koja shema funkcionira. U ovom članku ćemo pogledati kako se kompresija je ono nijanse koje bi se ubrzao i pojednostavio proces kodiranja, kao i vidjeti što je princip kodiranja stabla.

Povijest algoritma

Prvi algoritam za učinkovito kodiranje elektroničkih informacija bio je kod koji je Huffman predložio sredinom dvadesetog stoljeća, odnosno 1952. godine. Trenutačno je glavni osnovni element većine programa stvorenih za komprimiranje informacija. Trenutno, jedan od najpopularnijih izvora koji koriste ovaj kôd su ZIP, ARJ, RAR arhivi i mnogi drugi. Također se koristi i ovaj Huffmanov algoritam komprimiranje JPEG slika i drugih grafičkih objekata. Pa, svi moderni fax aparati također koriste kodiranje, izmislio 1952. Unatoč činjenici da od stvaranja koda toliko vremena je prošlo, do danas se koristi u najnovijim školjkama i opremi starih i modernih tipova.

Načelo učinkovitog kodiranja

Huffmanov algoritam temelji se na shemi koja omogućuje zamjenu najvjerojatnijih, najčešćih simbola binarni kodovi sustav. A oni koji su manje uobičajeni zamjenjuju se duljim kodovima. Prijelaz na duge Huffmanove kodove događa se tek nakon što sustav koristi sve minimalne vrijednosti. Ova tehnika omogućuje vam da minimizirate duljinu koda za svaki znak izvorne poruke u cjelini. Važno je napomenuti da je na početku kodiranja vjerojatno već poznata vjerojatnost pojave slova. Iz njih će se sastaviti konačna poruka. Na temelju tih podataka izrađen je Huffmanov kodni šum, na temelju kojeg će se provesti proces kodiranja pisama u arhivi.

Huffmanov kod, primjer

Da bismo ilustrirali algoritam, uzmimo grafičku varijantu konstruiranja stabla koda. Da bi se ova metoda koristila djelotvorna, vrijedno je pojasniti definiciju nekih vrijednosti potrebnih za koncept ove metode. Skup lukova i čvorova koji su usmjereni od čvora do čvora obično se naziva grafikon. Sam stablo je grafikon s nizom određenih svojstava:

• u svakom čvoru može ući samo jedan od luka;
• jedan od čvorova mora biti korijen stabla, to jest, niti jedan luk ne bi trebao ući uopće;
• ako se od korijena počne kretati duž lukova, ovaj proces bi trebao dopustiti da se potpuno u bilo koji od čvorova.

Tu je i takav koncept, koji je uključen u Huffmanove kodove, kao list stabla. To je čvor od kojeg ne treba izbjeći luk. Ako su dva čvora povezana luk, jedan od njih je roditelj drugog djeteta, ovisno o tome iz kojeg čvora luk se gasi, a što je uključen. Ako dva čvora imaju isti roditeljski čvor, obično se nazivaju bratski čvorovi. Ako, pored lišća, u čvorovima postoji nekoliko lukova, ovo se stablo zove binarno. Ovo je točno stablo Huffmana. Posebnost čvorova ove konstrukcije je da je težina svakog roditelja jednaka zbroju težine svih njegovih čvorova.

Algoritam za izgradnju stabla prema Huffmanu

Izrada Huffmanovog koda izrađena je od slova ulazne abecede. Izrađen je popis onih čvorova koji su besplatni u budućem stablu koda. Težina svakog čvora na ovom popisu mora biti jednaka vjerojatnosti pojavljivanja slova poruke koja odgovara ovom čvoru. U ovom slučaju, između nekoliko slobodnih čvorova budućeg stabla odabire se ona koja teži najmanje. Istodobno, ako se minimalni pokazatelji promatraju u nekoliko čvorova, onda je moguće slobodno odabrati bilo koji par. Nakon toga se stvara roditeljski čvor koji treba težiti onoliko koliko zbroj parova čvorova teži. Nakon toga roditelj se šalje na popis s besplatnim čvorovima, a djeca se brišu. Istodobno, lukovi dobivaju odgovarajuće indekse, one i nula. Ovaj se postupak ponavlja točno onoliko dugo koliko je potrebno ostaviti samo jedan čvor. Nakon toga, binarni brojevi se zapisuju od vrha do dna.

Poboljšanje učinkovitosti kompresije

Kako bi se povećala učinkovitost kompresije, potrebno je vrijeme drvo građevinskim propisima koristiti sve podatke o vjerojatnosti pojave slova u određenu datoteku, vezan za drvo, a ne dopustiti činjenicu da su se raspršili preko velikog broja tekstualnih dokumenata. Ako prvi put prođete ovu datoteku, možete odmah izračunati statistiku o tome koliko često se susreću slova iz objekta koji se stisne.

Ubrzanje procesa kompresije

Ubrzati rad algoritam, definicija slova se ne bi trebala provoditi prema indeksima vjerojatnosti pojavljivanja određenog slova, već prema učestalosti njezine pojave. Zahvaljujući tome, algoritam postaje jednostavniji, a rad s njim uvelike se ubrzava. To također izbjegava operacije povezane s plutajućim zarezima i podjelom. Osim toga, radeći u ovom načinu rada, dinamički Huffmanov kod, odnosno sam algoritam, ne podliježe nikakvim promjenama. To je uglavnom zbog činjenice da su vjerojatnosti izravno proporcionalne frekvencijama. To je vrijedno plaćati pozornost na činjenicu da je konačna težina datoteke, ili tzv root čvor jednak je zbroju broja znakova u objektu koji se tretiraju.

zaključak

Huffmanovi kodovi jednostavni su i dugoročni algoritam koji još uvijek koriste mnogi poznati programi i tvrtke. Njegova jednostavnost i jasnoća omogućuju postizanje učinkovitih rezultata kompresije za datoteke bilo koje veličine i značajno smanjuju prostor koji zauzimaju na disku za pohranu. Drugim riječima, Huffmanov algoritam je dugo proučavana i dobro osmišljena shema, čija se važnost ne smanjuje do danas. Zahvaljujući mogućnosti smanjenja veličine datoteka, prijenosa ih preko mreže ili na druge načine, postaje jednostavnija, brža i praktičnija. Rad s algoritmom možete komprimirati apsolutno sve informacije bez oštećenja njegove strukture i kvalitete, ali s maksimalnim učinkom smanjenja težine datoteke. Drugim riječima, kodiranje Huffman kodova bilo je i ostaje najpopularnija i aktualna metoda kompresije veličine datoteke.