Huffman númer: dæmi, umsókn

Í augnablikinu, fáir hugsa um hvernig samþjöppun virkar. Í samanburði við fortíðina hefur notkun einkatölvu orðið miklu auðveldara. Og nánast allir sem vinna með skráarkerfið nota skjalasafn. En fáir hugsa um hvernig þeir virka og hvaða meginregla er samþjöppun skráa. Fyrsta útgáfa af þessu ferli var Huffman númerin, og þau eru enn notuð í ýmsum vinsælum skjalavörum. Margir notendur hugsa ekki einu sinni hversu auðvelt það er að þjappa skránni og samkvæmt hvaða kerfi það virkar. Í þessari grein munum við líta á hvernig samþjöppun virkar, hvaða blæbrigði hjálpa til við að flýta fyrir og einfalda kóðunarferlið, og við munum einnig skilja hvað meginreglan um að byggja upp erfðatré er.

Saga reikniritsins

Fyrsta reiknirit fyrir skilvirka kóðun rafrænna upplýsinga var kóðinn sem Huffman lagði fram um miðjan tuttugustu öld, þ.e. árið 1952. Það er nú helsta grundvallarþátturinn í flestum forritum sem eru búnar til til að þjappa upplýsingum. Í augnablikinu eru einn af vinsælustu heimildir sem nota þessa kóða skjalasafn í ZIP, ARJ, RAR og mörgum öðrum. Þessi Huffman reiknirit er einnig notað til að þjappa JPEG-myndum og öðrum grafískum hlutum. Jæja og öll nútíma fax notar einnig kóðann, fundin upp árið 1952. Þrátt fyrir þá staðreynd að þar sem kóðinn var búinn svo mikill tími hefur liðið, að þessum degi er hann notaður í nýjustu skeljarum og búnaði af gömlum og nútíma gerðum.

Meginreglan um skilvirka erfðaskrá

Grunnur fyrir Huffman reiknirit er kerfi sem gerir þér kleift að skipta út líklegustu, oftast áberandi táknum með kóða tvöfalt kerfisins. Og þeir sem eru minna algengar komi í stað lengri kóða. Umskipti í langan Huffman kóða eiga sér stað aðeins eftir að kerfið notar öll lágmarksgildi. Þessi tækni gerir þér kleift að draga úr lengd kóðans fyrir hverja staf af upprunalegu skilaboðum í heild. Mikilvægt atriði er að í upphafi kóðunarinnar ætti líkurnar á að bréf sé að vera þegar þekkt. Það er af þessum sökum að endanleg skilaboð verða tekin upp. Byggt á þessum gögnum er Huffman kóða tré byggt, á grundvelli þess sem ferlið við kóðun bókstafa í skjalinu verður framkvæmt.

Kóði Huffman, dæmi

Til að lýsa reikniritinu, skulum við taka myndræna afbrigði af því að byggja upp kóða tré. Til að nota þessa aðferð var árangursrík, er það þess virði að skýra skilgreiningu á sumum gildum sem nauðsynlegar eru fyrir hugtakið þessa aðferð. Boga og hnútar sem eru beint frá hnút til hnút eru venjulega kölluð graf. Tréið sjálft er graf með ákveðnum eiginleikum:

• Í hverri hnút er ekki hægt að slá inn fleiri en einn af boga;
• Eitt af hnútum verður að vera rót trésins, það er, það ætti ekki að vera nein boga í henni;
• Ef frá rótinni til að byrja að flytja meðfram boga, ætti þetta ferli að leyfa að komast alveg inn í einhvern hnúta.

Það er líka svo hugtak, sem er innifalið í Huffman kóða, sem blaða tré. Það er hnútur sem enginn boga ætti að flýja frá. Ef tveir hnúður eru tengdir með hring, þá er einn þeirra foreldri, hinn barnið, eftir því hvaða hnútur boga kemur frá og hver sá er í. Ef tveir hnúður hafa sömu foreldrahnútur, eru þeir venjulega kölluð fraternal hnúður. Ef, auk laufanna, eru nokkrir boga í hnútunum, er þetta tré kallað tvöfalt. Þetta er einmitt tré Huffman. Eiginleikar hnúta þessa byggingar eru að þyngd hvers foreldris er jöfn summu þyngdar allra knattspyrnu barna sinna.

Reiknirit til að byggja upp tré samkvæmt Huffman

Uppbygging Huffman kóðans er gerð úr bókstöfum innsláttar stafrófsins. Listi yfir þau hnúður sem eru ókeypis í framtíðinni, kóða tré er búið til. Þyngd hverrar hnút á þessum lista ætti að vera sú sama og líkurnar á að bréf skilaboðanna sem samsvara þessum hnút séu til staðar. Í þessu tilviki, meðal fáeinna frjálsa hnúta framtíðar trésins, er sá sem vegur minnst er valinn. Á sama tíma, ef lágmarksvísirnar koma fram í nokkrum hnútum, þá er hægt að velja frjálslega eitthvað af pörunum. Eftir það er móðurhnúturinn búinn til, sem ætti að vega eins mikið og summan af þessu par hnúta vega. Eftir þetta er foreldri sendur á listann með ókeypis hnúður og börnin eru eytt. Á sama tíma fá boga samsvarandi vísitölur, sjálfur og núll. Þetta ferli er endurtekið nákvæmlega eins lengi og nauðsyn krefur til að fara aðeins einum hnút. Þá eru tvöfaldur tölur skrifaðir niður frá toppnum.

Efling þjöppunar skilvirkni

Til að auka skilvirkni samþjöppunar er nauðsynlegt að nota öll gögn varðandi líkur á bréfum sem birtast í tiltekinni skrá sem tengist trénu og ekki leyfa þeim að dreifa yfir fjölda textaskjala þegar þau byggja upp kóða tré. Ef þú gengur fyrst í gegnum þessa skrá getur þú strax reiknað út tölfræði um hversu oft bréf frá hlutnum sem á að þjappa eru.

Hröðun á þjöppunarferlinu

Til að flýta fyrir reikniritinu þarf bréfin að ákvarða ekki vísitölur líkurnar á því að tiltekið bréf sé til staðar, en eftir tíðni þess. Þökk sé þessu er reiknirit auðveldara, og vinna með það er mjög flýtt. Þetta forðast einnig aðgerðir sem tengjast fljótandi kommu og skiptingu. Að auki er ekki hægt að vinna í þessari stillingu, dynamic Huffman kóða eða frekar reikniritið sjálft. Þetta stafar aðallega af því að líkurnar eru í réttu hlutfalli við tíðin. Það er þess virði að leggja sérstaka áherslu á þá staðreynd að endanleg þyngd skráarinnar eða svokölluð rótarhnútur verði jöfn summan af fjölda stafa í hlutnum sem á að vinna.

Niðurstaða

Kóða Huffman er einföld og langvarandi reiknirit sem enn er notuð af mörgum frægum forritum og fyrirtækjum. Einfaldleiki þess og skýrleiki gerir kleift að ná árangri niðurstöðum úr þjöppun skrár af einhverjum bindi og til að draga verulega úr plássinu sem þeim er geymt á geymsluplötunni. Með öðrum orðum er Huffman reikniritið langt rannsakað og vel hönnuð kerfi, sem hefur ekki áhrif á þennan dag. Og þökk sé getu til að draga úr stærð skráa, flytja þau yfir netið eða með öðrum hætti, verður það auðveldara, hraðari og þægilegra. Vinna með reikniritinu, þú getur þjappað algerlega allar upplýsingar án þess að skaða uppbyggingu og gæði, en með hámarksáhrifum að draga úr þyngd skráarinnar. Með öðrum orðum, Huffman kóða erfðaskrá var og er vinsælasta og raunverulega aðferðin við skráarstærð samþjöppun.