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ā kompresijas darbi, kādas nianses palīdz paātrināt un vienkāršot kodēšanas procesu, un mēs arī sapratīsim, kāds ir kodēšanas koka veidošanas princips.

Algoritma vēsture

Pirmais algoritms efektīvaiElektroniskās informācijas kodēšana bija kods, ko Huffmans ierosināja divdesmitā gadsimta vidū, proti, 1952. gadā. Pašlaik tā ir galvenā elementa daļa visās programmās, kas izveidotas informācijas saspiešanai. Šobrīd viens no populārākajiem avotiem, izmantojot šo kodu, ir ZIP, ARJ, RAR arhīvi un daudzi citi.

Šis Huffman algoritms tiek izmantots arīJPEG attēlu un citu grafisko objektu kompresija. Nu, visas mūsdienu faksa iekārtas izmanto arī kodēšanu, kas izgudrots 1952. gadā. Neskatoties uz to, ka kopš koda izveides ir pagājis tik daudz laika, līdz šai dienai tas tiek izmantots jaunākajos apvalkos un veco un mūsdienu tipu aprīkojumā.

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 kodeksosHuffmans, tāpat kā koka lapas. Tas ir mezgls, no kura nav jāgaida loka. Ja divi mezgli ir savienoti ar loku, tad viens no tiem ir vecāks, otrais bērns, atkarībā no tā, no kura mezgla nāk no loka, un kura ir tā. Ja diviem mezgliem ir viens un tas pats mezgls, tos parasti sauc par brāļu mezgliem. Ja papildus lapām mezglos ir vairāki loki, šis koks tiek dēvēts par bināro. Tas ir tieši Huffmaņa 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.

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ā. Katra šī saraksta mezgla svaram jābūt tādam pašam kā šī mezgla ziņojuma vēstules rašanās varbūtība. Š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šamskoku būvnormatīvu laikā izmantot visus datus par varbūtību burtiem konkrētajā failā, kas piestiprināta pie koka, un neļauj to, ka tie ir izkaisīti pa lielu skaitu teksta dokumentiem. Ja iepriekš pastaiga pa šo failu, jūs varat uzreiz aprēķināt statistikas datus par to, cik bieži ir burti no apsaimniekošanas objekta uz saspiešanu.

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ā darba režīmā, dinamiskāHafmana 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.