Amakhodi we-Huffman: izibonelo, uhlelo lokusebenza

Okwamanje, bambalwa abantu bacabanga ukuthi i-compress isebenza kanjani. Uma kuqhathaniswa nesikhathi esidlule, ukusebenzisa ikhompyutha yomuntu siqu kuye kwaba lula kakhulu. Futhi cishe wonke umuntu osebenza nesistimu yefayili isebenzisa ingobo yomlando. Kodwa bambalwa abantu bacabanga ukuthi basebenze kanjani nokuthi yisiphi isimiso ukucindezelwa kwamafayela. Inguqulo yokuqala yale nqubo kwakuyikhodi yamaHuffman, futhi isasetshenziswa ezinqolobaneni ezihlukahlukene ezidumile. Abasebenzisi abaningi abacabangi ngisho nokuthi kulula kanjani ukucindezela ifayela futhi ngokusho ukuthi yiluphi uhlelo olusebenzayo. Kule ngqikithi, sizobheka indlela ukucindezela kusebenza ngayo, yiziphi izimo ezihamba phambili ezisiza ukusheshisa nokwenza ngcono inqubo yokufaka ikhodi, futhi uqonde ukuthi yisiphi isimiso sokwakha umuthi wokubhala.

Umlando we-algorithm

I-algorithm yokuqala yokuqala yokwenza ikhodi esebenzayo yokwaziswa kwe-elekthronikhi kwakuyikhodi ehlongozwa nguHuffman phakathi nekhulu lama-20, okuyi-1952. Okwamanje kuyisici esiyisisekelo sezinhlelo eziningi ezidalwe ukucindezela ulwazi. Okwamanje, omunye wemithombo ethandwa kakhulu esebenzisa le khodi yizinqolobane ze-ZIP, ARJ, RAR nabanye abaningi. Le algorithm ye-Huffman nayo isetshenziselwa ukucindezela izithombe ze-JPEG nezinye izinto ezibonakalayo. Kuhle futhi zonke izinkampani zanamuhla zisebenzisa i-coding, eyakhiwe ngo-1952. Naphezu kweqiniso lokuthi njengoba ikhodi idalwe isikhathi esiningi kakhulu, kuze kube yilolu suku lisetshenziselwa amagobolondo amasha kanye nemishini yezindala nezindala zanamuhla.

Isimiso sokwenza ikhodi esebenzayo

Isisekelo se-algorithm ye-Huffman yisimiso esikuvumela ukuba ususe izimpawu ezingenzeka kakhulu, ezivame ukuhlangana nazo namakhodi wesistimu kanambambili . Futhi lezo ezingavamile kakhulu ziyashintshwa ngamakhodi amade. Ukushintshela kumakhodi ase-Huffman amade kwenzeka ngemva kokuba uhlelo lusebenzisa wonke amanani amancane. Le nqubo ikuvumela ukuba unciphise ubude bekhodi kumlingisi ngamunye womlayezo wokuqala. Iphuzu elibalulekile ukuthi ekuqaleni kokufaka ikhodi, amathuba okutholakala kwezinhlamvu kufanele aziwe kakade. Kungenxa yalokhu ukuthi umyalezo wokugcina uzokwenziwa. Ngokusekelwe kulolu datha, umuthi wekhodi kaHuffman wakhiwe, ngesisekelo lapho inqubo yokubhala amagama e-archive izokwenziwa.

Ikhodi kaHuffman, isibonelo

Ukufanekisa i-algorithm, ake sithathe okungafaniyo kokwakha umuthi wekhodi. Ukusebenzisa le ndlela kwakuphumelele, kuyakusiza ukucacisa incazelo yamanye amanani adingekayo kumqondo walendlela. Iqoqo lama-arcs nama-node aqondiswa kusuka ku-node kuya ku-node ngokuvamile ibizwa ngokuthi igrafu. Isihlahla ngokwayo igrafu eneqoqo lezinto ezithile:

• In node ngayinye ayikwazi ukungena ngaphezu kweyodwa yama-arcs;
• Enye yalezi nodes kufanele ibe yimpande yomuthi, okungukuthi, akufanele kube khona ama-arcs kuwo;
• Uma kusuka empandeni ukuqala ukuhamba nge-arcs, le nqubo kufanele ivumele ukuba ifike ngokuphelele kunoma yiziphi izinombolo.

Kukhona nomqondo onjalo, ohlanganisa amakhodi kaHuffman, njengeqabunga lomuthi. Kuyinto node okungekho i-arc okufanele ibaleke ngayo. Uma ama-node amabili axhunyiwe i-arc, omunye wabo ungumzali, omunye umntwana, kuye ngokuthi iyiphi i-node i-arc evela kuyo, nokuthi iyiphi. Uma ama-node amabili ane-node efanayo yomzali, ngokuvamile ebizwa ngokuthi ama-nodes angama-fraternal. Uma, ngaphezu kwamaqabunga, kunezinhlobo eziningana kumanothi, lesi sihlahla sabizwa ngokuthi sinambambili. Lena impela umuthi kaHuffman. Ukuziqhenya kwamanothi alokhu kwakhiwa ukuthi isisindo somzali ngamunye siningana nesisindo sesisindo sazo zonke izingane zayo ezinamahloni.

I-Algorithm yokwakha umuthi ngokusho kukaHuffman

Ukwakhiwa kwekhodi yeHuffman kwenziwa ngezinhlamvu ze-alfabhethi yokufaka. Uhlu lwama-node olutholakala esihlahleni sekhodi esizayo ludalwa. Isisindo se-node ngayinye kulolu hlu kufanele sifane namathuba okutholakala kwencwadi yomlayezo ohambelana nale node. Kulokhu, phakathi kwezimbalwa ezimbalwa zamahhala esihlahla esizayo, lowo olinganisa okungenani ukhethiwe. Ngesikhathi esifanayo, uma izinkomba ezincane zikhonjelwa emaqenjini ambalwa, kungenzeka ukuthi ukhethe ngokukhululekile noma yikuphi okubili. Ngemuva kwalokho, i-node yomzali idalwe, okumele ibe nesisindo esiningi njengoba inani lalezi zindidi zilingana. Emva kwalokhu, umzali uthunyelwa kuhlu olunezinombolo zamahhala, futhi izingane zisusiwe. Ngesikhathi esifanayo, ama-arcs athola ama-indices afanayo, lawo nama-zero. Le nqubo iphindwa ngokuphindaphindiwe njengoba kudingekile ukushiya i-node eyodwa kuphela. Khona-ke izinombolo zobunambambili zibhaliwe phansi kusukela phezulu.

Ukwenza ngcono ukusebenza kahle

Ukuze ukwandise ukusebenza kahle kokucindezela, kuyadingeka, ngesikhathi sokwakha umuthi wekhodi, ukusebenzisa yonke imininingwane ngokuphathelene namathuba okubhalwa kwezincwadi ezivela efayeleni elithile elihlanganiswe esihlahleni, futhi ungazivumeli ukuba zihlakazeke ngenani elikhulu lemibhalo yombhalo. Uma uqala ukuhamba kuleli fayela, ungakwazi ngokushesha ukubala izibalo ukuthi kaningi kangakanani izincwadi ezivela entweni okufanele zicindezelwe.

Ukusheshisa kwenqubo yokucindezela

Ukusheshisa umsebenzi we-algorithm, izinhlamvu kumele zizinqunywe hhayi ngama-indices okungenzeka ukuthi kwenzeke kuncwadi ethile, kodwa ngokuphindaphindiwe kokuvela kwayo. Ngenxa yalokhu, i-algorithm iba lula, futhi ukusebenza nayo ishesha kakhulu. Lokhu futhi kugwema imisebenzi ehambisana nama-float and floating floating. Ngaphezu kwalokho, ukusebenza kule modeli, ikhodi yeHuffman enamandla, noma kunalokho i-algorithm ngokwalo, ayihambisani nanoma yiziphi izinguquko. Lokhu kubangelwa ukuthi ama-probability alingana ngokuqondile namazinga. Kumele uqaphele ngokukhethekile ukuthi isisindo sokugcina sefayili noma okuthiwa izimpande zesikhwama sizolingana nesamba senani lezinhlamvu into okuzocutshungulwa.

Isiphetho

Amakhodi kaHuffman ayi-algorithm elula futhi esungulwe isikhathi eside esasetshenziswa izinhlelo eziningi nezinkampani ezidumile. Ukulula nokucaca kwayo kuvumela ukufeza imiphumela ephumelelayo yokucindezela kwamafayela kwanoma yimaphi amavolumu futhi ukunciphisa kakhulu isikhala esithathwe kuso kwisidiski sokugcina. Ngamanye amazwi, i-algorithm ye-Huffman yikimu elifundela isikhathi eside futhi elenzelwe kahle, okubaluleka kwalo akuyehla nanamuhla. Futhi ngenxa yokwazi ukunciphisa usayizi wamafayela, ukudlulisela kuwo wonke inethiwekhi noma ngezinye izindlela, kuba lula, ngokushesha futhi okulula kakhulu. Ukusebenza ne-algorithm, ungakwazi ukucindezela ngokuphelele noma yiluphi ulwazi ngaphandle kokulimaza isakhiwo nesimo sayo, kodwa ngomphumela omkhulu wokunciphisa isisindo sefayela. Ngamanye amazwi, ikhodi ye-Huffman ikhodi yesikhombisi yayisetshenziswa futhi ihlala indlela ethandwa kakhulu futhi yangempela yokucindezela usayizi wefayela.