Hafmaņa kodi: piemēri, lietojumprogrammas

Šobrīd maz cilvēki domā par to,kā kompresijas darbi. Salīdzinājumā ar pagātni personālo datoru ir kļuvis daudz vieglāk. Un praktiski ikviens, kas strādā ar failu sistēmu, izmanto arhīvus. Taču daži cilvēki domā par to, kā viņi strādā, un par to, kurš princips ir failu saspiešana. Pati pirmā šī procesa versija bija Hafmaņa kodi, un tos joprojām izmanto dažādos tautas arhīvos. Daudzi lietotāji pat nedomā, cik viegli ir saspiest failu un saskaņā ar kuru shēmu tā darbojas. Šajā rakstā mēs aplūkosim, kā kompresija tiek veikta, kādas nianses palīdz paātrināt un vienkāršot kodēšanas procesu, un mēs noskaidrosim, kas ir kodēšanas koka konstruēšanas princips.

Algoritma vēsture

Pirmais algoritms efektīvaielektroniskās informācijas kodēšanas kļuvusi ko Huffman ierosināja vēl vidū divdesmitā gadsimta, proti, 1952. gadā kodu. Tas bija viņš, kurš šobrīd ir pamats lielākajai daļai programmām, kas radītas, lai saspiestu informāciju elements. Šobrīd viens no populārākajiem avotiem, izmantojot šo kodu ir arhīvu ZIP, ARJ, RAR un daudzi citi.

Šis Huffman algoritms tiek izmantots arīJPEG attēlu un citu grafisko objektu kompresija. Nu, visi faksi arī izmantojot modernas kodēšana, izgudroja 1952. gadā. Neskatoties uz to, ka kopš izveide kodu paņēma tik daudz laika, lai šo dienu tas tiek izmantots dažādu jaunu membrānu un iekārtu veco un moderno veidiem.

Efektīvas kodēšanas princips

Huffmana algoritma pamats ir shēma,Tas ļauj aizstāt visbiežāk sastopamos simbolus ar binārās sistēmas kodiem. Un tie, kas ir retāk sastopami, tiek aizstāti ar ilgākiem kodiem. Pāreja uz ilgiem Hafmana kodiem notiek tikai pēc tam, kad sistēma izmanto visas minimālās vērtības. Šis paņēmiens ļauj minimizēt koda garumu katra sākotnējā ziņojuma rakstzīmju kopumā.

Svarīgi ir tas, ka sākumājau būtu jāzina burtu sastopamības varbūtība. Tieši no tiem tiks apkopota gala ziņa. Balstoties uz šiem datiem, tiek izveidots Huffmana kodu koks, uz kura pamata tiks veikts burtu kodēšanas process arhīvā.

Huffmana kods, piemērs

Lai ilustrētu algoritmu, pieņemsimkoda koka konstrukcijas grafiskā versija. Lai šo metodi izmantotu efektīvi, ir lietderīgi precizēt dažu šīs metodes jēdzienu vajadzīgo vērtību definīciju. Loka un mezglu kopums, kas tiek virzīts no mezgla uz mezglu, parasti sauc par grafiku. Pati koks ir diagramma ar noteiktu rekvizītu komplektu:

• katrā mezglā var ievadīt ne vairāk kā vienu no lokiem;
• vienam no mezgliem jābūt koka saknēm, tas ir, loka nav jāievada vispār;
• ja no saknes, lai sāktu pārvietoties pa lokiem, šim procesam vajadzētu ļaut pilnīgi iekļūt kādā no mezgliem.

Ir arī tāds jēdziens, kas iekļauts kodeksosHuffman, tāpat kā lapas no koka. Tas ir mezgls, no kura nevajadzētu doties jebkurā loka. Ja divi mezgli ir savienoti ar loka, kas ir viens no tiem ir mātes otras bērnam, atkarībā no tā, no kuras mezglu loka iet ārā, un kas ir iekļauti. Ja diviem mezgliem ir tas pats mātes mezglā, tos sauc māsu vietām. Ja lapām, lapas no mezgliem vairāku lokiem, tad to sauc par bināro koku. Tieši tāpēc ir Huffman koks. Par būvniecības vienību īpatnība ir tāda, ka katra vecāka svars ir vienāds ar summu svaru visu savu bērnu mezgliem.

Koka konstrukcijas algoritms atbilstoši Huffmanam

Hafmana koda konstrukcija ir veidota no burtiemno ievades alfabēta. Tiks izveidots to mezglu saraksts, kuri ir brīvi nākamajā koda kokā. Katras mezgla sarakstā svars ir tāda pati kā varbūtību ar burtu amatu, kas atbilst šajā mezglā. Šajā gadījumā ir izvēlēts viens no mazākajiem nākotnes koka mezgliem. Tajā pašā laikā, ja minimālie rādītāji tiek novēroti vairākos mezglos, tad ir iespējams brīvi izvēlēties kādu no pāriem.

Tad vecāku radīšanamezglu, kuram vajadzētu nosvērt tik 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 dzēsti. Tajā pašā laikā lūkas saņem atbilstošus indeksus, tos un nulles. Šo procesu atkārto tieši tik ilgi, cik nepieciešams, lai atstātu tikai vienu mezglu. Pēc tam binārie skaitļi tiek ierakstīti no augšas uz leju.

Kompresijas efektivitātes uzlabošana

Lai palielinātu kompresijas efektivitāti, ir nepieciešamslaiks, lai izveidotu koda koku, lai izmantotu visus datus par burtu varbūtību, kas parādās konkrētā kokā pievienotā failā, un neļaut tiem izkliedēt lielu skaitu teksta dokumentu. Ja jūs vispirms izmantojat šo failu, varat nekavējoties aprēķināt statistiku par to, cik bieži tiek saskarē saspiestā objekta burti.

Saspiešanas procesa paātrināšana

Lai paātrinātu algoritmu, burtu definīcijaNepieciešams veikt rādītājus par šīs vai šīs vēstules rašanās varbūtību un tās rašanās biežumu. Pateicoties tam, algoritms kļūst vienkāršāks, un darbs ar to ir ievērojami paātrināts. Tas arī novērš darbības, kas saistītas ar peldošajām komām un sadalīšanu.

Turklāt šajā režīmā darbojas dinamisksHafmana kods vai drīzāk pats algoritms netiek pakļauts izmaiņām. Tas galvenokārt saistīts ar faktu, ka varbūtības ir tieši proporcionālas frekvencēm. Ir vērts pievērst īpašu uzmanību faktam, ka faila galīgais svars vai tā sauktais saknes mezgls būs vienāds ar apstrādāto objektu burtu summu.

Secinājums

Huffmana kodi - vienkārši un ilgstošialgoritms, kuru joprojām izmanto daudzas pazīstamas programmas un uzņēmumi. Tās vienkāršība un skaidrība ļauj sasniegt efektīvus saspiešanas rezultātus jebkura izmēra failiem un ievērojami samazināt telpu, ko tie aizņem uzglabāšanas diskā. Citiem vārdiem sakot, Huffman algoritms ir ilgi izpētīta un labi izstrādāta shēma, kuras atbilstība līdz šodienai nav mazāka.

Pateicoties spējai samazināt failu lielumu,to pārraide tīklā vai citos veidos kļūst vienkāršāka, ātra un ērta. Strādājot ar algoritmu, jūs varat saspiest absolūti jebkādu informāciju, nekaitējot tā struktūrai un kvalitātei, bet ar maksimālu efektu, samazinot faila svaru. Citiem vārdiem sakot, Huffman kodu kodēšana bija un joprojām ir populārākā un faktiskā faila lieluma saspiešanas metode.