Huffman codes: mifano ya maombi

Kwa sasa, watu wachache kufikiria kweli, jinsi gani ya faili compression. Ikilinganishwa na matumizi ya awali ya kompyuta binafsi imekuwa rahisi zaidi. Na karibu kila mtu kufanya kazi na mfumo wa faili inatumia mafaili. Lakini watu wachache kufikiri kuhusu jinsi inavyofanya kazi na kwa misingi gani ni faili compression. toleo la kwanza sana ya mchakato huu walikuwa codes Huffman, na wao kutumika leo katika aina mbalimbali za archivers maarufu. Watumiaji wengi hawana hata kufikiria jinsi gani rahisi faili compression unafanyika na ni kazi ya mpango huo. Katika makala hii sisi kuangalia jinsi compression ni nini yanatathmini msaada kasi ya juu na kurahisisha mchakato wa encoding, pamoja na kuona nini kanuni ya coding miti.

historia algorithm

algorithm ya kwanza kabisa ya ufanisi coding wa habari za elektroniki imekuwa code Huffman mapendekezo mapema katikati ya karne ya ishirini, yaani katika 1952. Yeye ndiye kwa sasa ni kipengele msingi wa wengi wa programu iliyoundwa kubana habari. Kwa sasa, moja ya vyanzo maarufu kwa kutumia nambari ya hii ni nyaraka ZIP, ARJ, rar na wengine wengi. Pia, algorithm hii ni kutumika kwa Huffman compression JPEG-picha na vitu vingine vya picha. Naam, faksi wote pia kutumia coding kisasa, zuliwa katika 1952. Licha ya ukweli kwamba tangu kuundwa kwa kanuni alichukua muda sana hadi leo ni kutumika katika aina ya utando mpya na vifaa vya zamani na ya sasa aina.

kanuni ya coding ufanisi

msingi wa Huffman algorithm ni pamoja mpango kwamba utapata nafasi zaidi ya kuaminika, sana sana huwaathiri alama coded binary mfumo. Na wale ambao ni chini ya kawaida, kubadilishwa na codes mrefu. Kwenda codes mrefu Huffman hutokea tu baada ya matumizi ya mfumo wa thamani zote kiwango cha chini. Mbinu hii inaruhusu kupunguza urefu wa kanuni kwa kila ishara ya ujumbe wa awali kwa ujumla. The muhimu uhakika yaani kuwa katika the mwa the coding uwezekano wa tukio la the barua lazima tayari linalojulikana. Ni kutoka kwao itakuwa tayari na ujumbe wa mwisho. Kulingana na takwimu hizi, ni kufanyika ujenzi wa Huffman code mti, kwa misingi ya ambayo itakuwa uliofanyika barua usimbaji mchakato katika kumbukumbu.

Huffman code, mfano

Kwa mfano algorithm, fikiria lahaja graphical wa ujenzi wa mti code. Kwa kutumia njia hii ili kuwa na ufanisi, ni muhimu kufafanua maana ya maadili fulani muhimu kwa ajili ya dhana ya mchakato. seti ya wingi wa nodes na Arcs, ambayo ni moja kwa moja kutoka kwa nodi na nodi, aitwaye graph. mti yenyewe ni graph na seti ya mali maalum:

• katika kila nodi ni pamoja si zaidi ya moja ya arcs;
• moja ya nodes lazima mizizi ya mti, yaani, ni lazima kuwa sehemu ya safu kabisa,
• kama shina kuanza kusonga pamoja arcs, mchakato lazima kuruhusu kupata kabisa katika yoyote ya nodi.

Kuna pia kama a kitu, sehemu ya the Huffman codes kama a jani la the miti. Ni nodi ambayo lazima kwenda safu yoyote. Kama sehemu mbili ni kushikamana na safu, mmoja wao ni mzazi wa mtoto mmoja, kulingana na ambayo nodi safu huenda nje, na nini ni pamoja. Kama sehemu mbili na moja mzazi nodi, ni kuitwa maeneo dada. Kama, kwa majani, majani kutoka nodes ya arcs kadhaa, baadaye huitwa mti binary. Hivyo tu mti Huffman. hupita upeo wa ujenzi wa vitengo ni kwamba uzito wa kila mzazi ni sawa na jumla ya uzito wa watoto wake wote nodi.

algorithm kwa ujenzi wa mti Huffman

ujenzi wa kanuni Huffman ni maoni kutoka kwa herufi za alfabeti. Yanayotokana orodha ya tovuti ambazo ni bure katika mti code baadaye. uzito wa kila nodi katika orodha lazima kuwa sawa na uwezekano wa kutokea kwa barua posts sambamba na nodi hii. Katika hali hii, mtu ambaye ina uzito angalau ni kuchaguliwa kutoka miongoni mwa maeneo kadhaa bila ya mti wa baadaye. Katika hali hii, kama viwango vya kima cha chini cha huonekana kwa maeneo kadhaa, unaweza uhuru kuchagua yoyote ya jozi. Hapo ndipo viumbe wa mzazi nodi, ambayo lazima uzito kama kiasi kama jumla ya uzito ya jozi ya nodi. Baada ya hapo, wazazi kupeleka orodha na vyoo bure, na watoto ni kuondolewa. Katika safu hii ni viashiria sahihi, ndio na zeros. Utaratibu huu mara kwa mara nyingi kama inahitajika kuweka tu nodi moja. Kisha kuandika tarakimu binary kutoka juu hadi chini.

Kuboresha ufanisi wa compression

Ili kuongeza compression ufanisi, ni muhimu wakati wa mti jengo code kutumia data zote kwenye uwezekano wa tukio la barua katika faili fulani, zinatokana na mti, na si kuruhusu ukweli kwamba ni walilazimika juu idadi kubwa ya nyaraka za maandishi. Kama kabla ya kutembea kwa njia ya faili hili, unaweza mara moja mahesabu ya takwimu ya jinsi mara nyingi kuna barua ya somo kituo na mbano.

Kuongeza kasi ya mchakato wa compression

Ili kuongeza kasi ya algorithm, ufafanuzi wa barua lazima kufanyika si katika suala la uwezekano wa kutokea kwa barua maalum, na mzunguko wa tukio hilo. Pamoja na algorithm hii inakuwa rahisi, na kufanya kazi pamoja nao kwa kasi zaidi. pia huepuka shughuli zinazohusiana na mgawanyo yaliyo-uhakika. Aidha, kufanya kazi katika hali hii, nguvu Huffman code, au tuseme algorithm yenyewe si chini ya mabadiliko yoyote. Hii ni hasa kutokana na ukweli kwamba probabilities ni moja kwa moja sawia na frequency. Ni thamani ya kulipa kipaumbele na ukweli kwamba uzito wa mwisho wa faili, au kinachojulikana mzizi nodi ni sawa na jumla ya idadi ya herufi katika kitu kutibiwa.

hitimisho

codes Huffman - rahisi na ya muda imara algorithm, ambayo bado hutumiwa na programu nyingi yanajulikana na makampuni. unyenyekevu wake na uwazi inaweza kufikia matokeo bora kubana files ya kiasi yoyote na kwa kiasi kikubwa kupunguza nafasi kwenye hifadhi disk. Kwa maneno mengine, Huffman algorithm - kwa muda mrefu yamechunguzwa na kazi mchoro ambayo uharaka si kupunguzwa kwa leo. Na kwa uwezo wa kupunguza ukubwa wa faili, kuhamisha yao juu ya mtandao au kwa njia nyingine ni rahisi zaidi, kwa haraka na rahisi. Kufanya kazi na algorithm, unaweza compress taarifa yoyote kabisa bila madhara kwa muundo wake na ubora, lakini kwa athari upeo kupunguza uzito file. Kwa maneno mengine, coding ya kanuni Huffman imekuwa na inaendelea kuwa njia maarufu na muhimu ya compressing ukubwa wa faili.