Huffman kodovi: primjeri primjena

U ovom trenutku, malo ljudi misle o tome, kako se sažimanje datoteke. U usporedbi s prethodnim korištenje osobnih računala postalo je puno lakše. I gotovo svaka osoba koja radi s datotečnog sustava koristi datoteke. No, malo ljudi misle o tome kako oni rade i na temelju čega je sažimanje datoteke. Prva verzija ovog procesa su Huffman kodove, i oni su se danas koriste u različitim popularnim archivers. Mnogi korisnici ni ne misle kako je lako sažimanje datoteke odvija i to radi na sustavu. 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 algoritam

Prvi algoritam učinkovitog kodiranja elektroničkih informacija postala je kod Huffman predložila još sredinom dvadesetog stoljeća, točnije 1952. godine. On je bio taj koji je u ovom trenutku je osnovni element većine programa stvorenih za kompresiju podataka. U ovom trenutku, jedan od najpopularnijih izvora koji koriste ovaj kod su arhivi ZIP, ARJ, RAR i mnogi drugi. Također, Huffman algoritam se koristi za sažimanje za JPEG-slike i druge grafičke objekte. Pa, svi faksovi također koriste suvremenu kodiranje, izumio u 1952. Unatoč činjenici da je od stvaranja koda je toliko vremena do danas se koristi u raznim novim membrane i opreme starih i suvremenih tipova.

Princip učinkovito kodiranje

Osnova Huffman algoritam uključuje shemu koja vam omogućuje da zamijenite najviše vjerodostojan, najčešće se javljaju znakovi kodirani binarni sustav. A oni koji su manje uobičajene, zamijenjen s dužim kodova. Odlazak duge Huffman kodove javlja tek nakon što je sustav koristi sve minimalne vrijednosti. Ova tehnika omogućuje da se smanji duljina koda za svaki simbol izvorne poruke u cjelini. Važno je da na početku vjerojatnosti kodiranja pojave slova treba već poznato. To je od njih će biti pripremljen i konačna poruka. Na temelju tih podataka, a provodi izgradnju Huffman koda stabla, na temelju kojih će se održati slova kodiranja u arhivi.

Huffman kod, primjerice

Za ilustraciju algoritma, razmislite grafički varijantu izgradnje koda stabla. Kako koristiti ovu metodu kako bi bila učinkovita, potrebno je pojasniti definiciju određene vrijednosti potrebnih za koncept procesa. Set od većeg broja čvorova i lukova, koji su usmjereni na čvor čvor iz naziva graf. Sam stablo je graf sa skupom specifičnih svojstava:

• svaki čvor može uključivati više od jednog od lukova;
• jedan od čvorova mora biti korijen stabla, to jest, to ne bi trebao biti dio luka na sve;
• ako je stabljika početi se kreće duž lukova, proces bi trebao omogućiti da se potpuno u bilo kojem od čvorova.

Tu je i takva stvar, dio Huffman kodova kao list drveta. To je čvor iz kojeg se ne bi trebao ići bilo 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 nadređeni čvor, oni su pozvani srodne stranice. Ako u lišću, lišće sa čvorovima nekoliko lukova, onda se to naziva binarno stablo. Samo tako je Huffman stablo. Osobitost izgradnju jedinica je da je težina svakog roditelja je jednaka zbroju težina svih njenih djece čvorova.

Algoritam za izgradnju stabla Huffman

Izgradnja Huffman kod je ulaz iz slova abecede. Generira popis web stranica koje su besplatno u budućnosti koda stabla. Težina svakog čvora na popisu moraju biti isti kao i vjerojatnosti pojave pisama postova odgovaraju ovom čvoru. U tom slučaju, onaj koji teži najmanje odabrana između nekoliko slobodnih mjesta budućeg stabla. U tom slučaju, ako se minimalne stope promatrati u nekoliko mjesta, možete slobodno izabrati bilo koji od parova. Tada dolazi stvaranje matične čvor, koji mora vagati koliko zbroj pondera par čvorova. Nakon toga, roditelji poslati popis sa slobodnim WC, a djeca su uklonjene. U tom luku su odgovarajući indikatori, jedinica i nula. Ovaj proces se ponavlja onoliko koliko je potrebno da bi samo jedan čvor. Zatim napisati binarne znamenke 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 je prethodno šetnja kroz ove datoteke, možete odmah izračunati statistiku koliko često postoje slova objekta podliježe kompresije.

Ubrzanje procesa kompresije

Da bi ubrzali algoritam, definicija slova treba biti učinjeno, ne u smislu vjerojatnosti pojave određenog pisma, i učestalost njegove pojave. Uz ovaj algoritam postaje lakše i raditi s njima puno brže. ona također izbjegava poslove povezane s podjelom s pomičnim zarezom. Osim toga, radi u ovom načinu rada, dinamičan Huffman kod, odnosno sama algoritam ne podliježe bilo kakvim promjenama. To je uglavnom zbog činjenice da su vjerojatnosti su izravno proporcionalna frekvenciji. 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

Huffman kodovi - jednostavno i dugo-osnovana algoritam, koji se još uvijek koristi od strane mnogih poznatih programa i tvrtki. Njegova jednostavnost i jasnoća može postići učinkovite rezultate komprimirati datoteke bilo koje volumena i značajno smanjiti prostor na disku za pohranu. Drugim riječima, Huffman algoritam - odavno istražuju i rade dijagram koji hitnost nije umanjena danas. A sa sposobnošću da smanje veličinu datoteke, prenijeti ih preko mreže ili na drugi način to je jednostavan, brzo i povoljno. Rad s algoritma, možete komprimirati podatke u potpunosti, bez štete za svoje strukture i kvalitete, ali s maksimalnim učinkom da se smanji datoteku težine. Drugim riječima, kodiranje s Huffman kodom bio je i ostao najpopularniji i relevantna metoda za sažimanje veličine datoteke.