Huffman kodi: piemēri, pielietojumi

Šobrīd par to domā maz cilvēkukā darbojas failu saspiešana. Salīdzinot ar pagātni, personālā datora lietošana ir kļuvusi daudz vienkāršāka. Un gandrīz visi, kas strādā ar failu sistēmu, izmanto arhīvus. Bet maz cilvēku domā par to, kā viņi strādā un kā tiek saspiesti faili. Pati šī procesa versija bija Hafmana kodi, un tie līdz šai dienai tiek izmantoti dažādos populāros arhīvos. Daudzi lietotāji pat nedomā par to, cik viegli ir saspiest failu un kā tas darbojas. Šajā rakstā aplūkosim, kā notiek saspiešana, kādas nianses palīdz paātrināt un vienkāršot kodēšanas procesu, kā arī izdomāsim, kāds ir kodēšanas koka veidošanas princips.

Algoritma vēsture

Pats pirmais algoritms efektīvas darbības veikšanaielektroniskās informācijas kodēšana kļuva par Hafmana piedāvāto kodu vēl divdesmitā gadsimta vidū, proti, 1952. gadā. Tas ir tas, kurš šobrīd ir lielākais informācijas elements, kas paredzēts informācijas saspiešanai. Pašlaik daži no populārākajiem avotiem, kas izmanto šo kodu, ir ZIP, ARJ, RAR arhīvi un daudzi citi.

Arī šis Huffman algoritms tiek piemērotsJPEG attēlu un citu grafisko objektu saspiešana. Nu, arī visos mūsdienu faksos tiek izmantots 1952. gadā izgudrots kodējums. Neskatoties uz to, ka kopš koda izveides ir pagājis tik daudz laika, tas joprojām tiek izmantots jaunākajās čaulās un uz veco un moderno tipu aprīkojuma.

Efektīvas kodēšanas princips

Huffmana algoritms ir balstīts uz shēmu,ļauj aizstāt visticamākās, visbiežāk sastopamās rakstzīmes ar binārās sistēmas kodiem. Un tie, kas ir mazāk izplatīti, tiek aizstāti ar garākiem kodiem. Pāreja uz garajiem Hafmana kodiem notiek tikai pēc tam, kad sistēma ir izmantojusi visas minimālās vērtības. Šis paņēmiens ļauj samazināt koda garumu katram sākotnējā ziņojuma rakstzīmei kopumā.

Svarīgs moments ir tas, ka sākumājau būtu jāzina burtu sastopamības kodēšanas varbūtība. Tieši no viņiem tiks sastādīts galīgais vēstījums. Pamatojoties uz šiem datiem, tiek izveidots Huffman koda koks, uz kura pamata tiks veikts burtu kodēšanas process arhīvā.

Hafmana koda piemērs

Lai ilustrētu algoritmu, ņemkoda koka veidošanas grafiskā versija. Lai izmantotu šo metodi, lai tā būtu efektīva, ir vērts precizēt dažu vērtību definīciju, kas nepieciešama šīs metodes koncepcijai. Loka un mezglu kopu kopu, kas tiek virzīti no mezgla uz mezglu, sauc par grafiku. Koks pats par sevi ir grafiks ar noteiktu īpašību kopumu:

• katrā mezglā var būt ne vairāk kā viens no lokiem;
• vienam no mezgliem jābūt koka saknei, tas ir, loki tajā vispār nedrīkst iekļūt;
• ja jūs sākat pārvietoties pa lokiem no saknes, šim procesam vajadzētu ļaut jums nokļūt pilnīgi jebkurā no mezgliem.

Kodos ir arī šāds jēdziensHufmans ir kā lapa kokā. Tas apzīmē mezglu, no kura nevajadzētu iziet nevienam lokam. Ja divus mezglus savieno loka, tad viens no tiem ir vecāks, otrs ir bērns, atkarībā no tā, no kura mezgla loka iziet un kurā tā nonāk. Ja diviem mezgliem ir viens un tas pats vecākais mezgls, tos parasti sauc par brāļa vai māsas mezgliem. Ja mezgliem papildus lapām ir vairāki loki, tad šo koku sauc par bināru. Tas ir tieši tas, kas ir Hafmana koks. Šīs konstrukcijas mezglu īpatnība ir tāda, ka katra vecāka svars ir vienāds ar visu tā mezglu bērnu svara summu.

Hafmana koka konstruēšanas algoritms

Huffman koda veidošana tiek veikta no burtiemievades alfabēts. Tiek izveidots saraksts ar tiem mezgliem, kuri ir brīvi nākotnes kodu kokā. Katra šī saraksta mezgla svaram jābūt tādam pašam kā attiecīgajam mezglam atbilstošā ziņojuma burta rašanās varbūtībai. Šajā gadījumā no vairākiem topošā koka mezgliem tiek izvēlēts tas, kas sver vismazāk. Turklāt, ja minimālie rādītāji tiek novēroti vairākos mezglos, varat brīvi izvēlēties jebkuru no pāriem.

Tad tiek izveidots vecāks.mezgls, kuram būtu jāsver tikpat daudz, cik sver šī mezglu pāra summa. Pēc tam vecāks tiek nosūtīts uz sarakstu ar bezmaksas mezgliem, un bērni tiek noņemti. Šajā gadījumā loki saņem atbilstošos rādītājus, vienus un nulles. Šis process tiek atkārtots tieši tik ilgi, cik nepieciešams, lai atstātu tikai vienu mezglu. Tad bināros ciparus raksta no augšas uz leju.

Kompresijas efektivitātes uzlabošana

Lai uzlabotu saspiešanas efektivitāti, jums tas jādaraveidojot kodu koku, izmantojiet visus datus par iespējamību, ka burti parādās konkrētā failā, kas pievienots kokam, un neļaujiet tos izkaisīt lielā skaitā teksta dokumentu. Ja pirmo reizi izejat cauri šim failam, varat nekavējoties aprēķināt statistiku par to, cik bieži tiek atrasti burti no saspiestā objekta.

Paātriniet saspiešanas procesu

Lai paātrinātu algoritmu, identificē burtusnepieciešams veikt nevis pēc konkrētas vēstules parādīšanās varbūtības rādītājiem, bet gan pēc tā rašanās biežuma. Tas padara algoritmu vienkāršāku un daudz ātrāku darbu. Tas arī ļauj izvairīties no peldošā komata un dalīšanas operācijām.

Turklāt, darbojoties šajā režīmā, dinamiskāHuffmana kods vai drīzāk pats algoritms netiek pakļauts izmaiņām. Tas galvenokārt ir saistīts ar faktu, ka varbūtības ir tieši proporcionālas frekvencēm. Īpašu uzmanību ir vērts pievērst tam, ka faila vai tā sauktā saknes mezgla gala svars būs vienāds ar burtu skaita summu apstrādājamajā objektā.

Secinājums

Hafmana kodi - vienkārši un sen izveidotialgoritms, kuru joprojām izmanto daudzas pazīstamas programmas un uzņēmumi. Tās vienkāršība un skaidrība ļauj sasniegt efektīvus jebkura lieluma failu saspiešanas rezultātus un ievērojami samazināt to vietu atmiņas diskā. Citiem vārdiem sakot, Huffmana algoritms ir ilgi pētīta un labi izstrādāta shēma, kuras atbilstība līdz mūsdienām nemazinās.

Pateicoties spējai samazināt faila lielumu,to pārraide tīklā vai ar citiem līdzekļiem kļūst vienkāršāka, ātrāka un ērtāka. Strādājot ar algoritmu, jūs varat saspiest pilnīgi jebkuru informāciju, nekaitējot tās struktūrai un kvalitātei, bet maksimāli samazinot faila svaru. Citiem vārdiem sakot, Huffman kodēšana ir bijusi un joprojām ir vispopulārākā un jaunākā metode faila lieluma saspiešanai.