Huffman codau: Cais enghreifftiau

Ar hyn o bryd, ychydig o bobl yn meddwl am y ffaith, sut mae cywasgu ffeiliau. O'i gymharu â'r defnydd blaenorol y cyfrifiadur personol wedi dod yn llawer haws. Ac mae bron pob person sy'n gweithio gyda'r system ffeiliau yn defnyddio ffeiliau. Ond mae ychydig o bobl yn meddwl am sut y maent yn gweithio ac ar ba sail yn cywasgu ffeiliau. Mae'r fersiwn cyntaf y broses hon oedd y codau Huffman, ac maent yn cael eu defnyddio heddiw mewn amrywiaeth o archivers poblogaidd. Nid yw llawer o ddefnyddwyr yn hyd yn oed yn meddwl pa mor hawdd cywasgu ffeiliau yn digwydd ac mae'n gweithio ar gynllun. Yn yr erthygl hon rydym yn edrych ar sut y mae'r cywasgu yw'r hyn arlliwiau help cyflymder i fyny ac i symleiddio'r broses o amgodio, yn ogystal â gweld yr hyn yr egwyddor y codio goeden.

algorithm hanes

Mae'r algorithm cyntaf o codio effeithlon o wybodaeth electronig wedi dod cod Huffman arfaethedig mor gynnar â chanol yr ugeinfed ganrif, sef yn 1952. Ef a ar hyn o bryd yw'r elfen sylfaenol y rhan fwyaf o'r rhaglenni a grëwyd i gywasgu'r wybodaeth. Ar hyn o bryd, un o'r ffynonellau mwyaf poblogaidd gan ddefnyddio'r cod hwn yw archifau ZIP, ARJ, ADA a llawer o rai eraill. Hefyd, mae'r algorithm Huffman cael ei ddefnyddio i gywasgu JPEG-delweddau a gwrthrychau graffig eraill. Wel, pob negeseuon ffacs hefyd yn defnyddio codio modern, a ddyfeisiwyd yn 1952. Er gwaethaf y ffaith bod ers y cod greu yn cymryd cymaint o amser hyd heddiw mae'n cael ei ddefnyddio mewn amrywiaeth o pilenni newydd a'r offer hen a modern math.

Mae'r egwyddor o codio effeithlon

Mae sail y algorithm Huffman cynnwys cynllun sy'n eich galluogi i gymryd lle y rhai mwyaf credadwy, gan amlaf symbolau digwydd deuaidd codio system. A'r rhai sydd yn llai cyffredin, disodli gyda chodau hirach. Mynd codau Huffman hir digwydd dim ond ar ôl i'r system yn defnyddio holl werthoedd lleiaf. Mae'r dechneg hon yn eich galluogi i leihau hyd y cod ar gyfer pob symbol y neges wreiddiol yn ei chyfanrwydd. Y pwynt pwysig yw bod ar ddechrau'r y tebygolrwydd o ddigwydd codio o'r llythyrau dylai eisoes yn hysbys. Mae'n o'r bydd yn eu paratoi'n a'r Neges olaf. Yn seiliedig ar y data hwn, mae'n cynnal y goeden cod Huffman adeiladu, ar y sail y bydd un ohonynt yn cael ei gynnal llythyrau broses amgodio yn yr archif.

cod Huffman, enghraifft

I ddangos y algorithm, yn ystyried amrywiad graffigol o adeiladu y goeden cod. I ddefnyddio'r dull hwn fod yn effeithiol, mae angen egluro'r diffiniad o werthoedd penodol sy'n angenrheidiol ar gyfer y cysyniad y broses. Mae set o lluosogrwydd nodau ac arcau, sy'n cael eu cyfeirio o nod i nod, a elwir yn graff. Mae'r goeden ei hun yn graff gyda set o eiddo penodol:

• ym mhob nod gynnwys dim mwy nag un o'r arcau;
• rhaid i un o'r nodau fod gwraidd y goeden, hynny yw, ni ddylai fod yn rhan o'r arc o gwbl;
• os yw'r coesyn yn dechrau symud ar hyd y arcau, dylai'r broses ganiatáu i fynd yn llwyr yn unrhyw un o'r nodau.

Mae yna hefyd y fath beth, yn rhan o'r codau Huffman fel deilen o'r goeden. Mae'n nod lle na ddylai fynd unrhyw arc. Os bydd dau nodau yn cael eu cysylltu gan arc, un ohonynt yn rhiant y plentyn arall, yn dibynnu ar lle gwgn gan yr arc yn mynd allan, a beth sydd wedi'i gynnwys. Os oes dau nodau yn cael yr un rhiant nod, maent yn cael eu galw'n safleoedd chwaer. Os, yn y dail, dail o'r nodau sawl arcau, yna fe'i gelwir yn goeden ddeuaidd. Yn union felly y mae y goeden Huffman. Mae'r nodwedd arbennig o'r unedau gwaith adeiladu yw bod y pwysau pob rhiant yn hafal i gyfanswm y pwysau ei holl nodau blant.

Algorithm gyfer adeiladu'r Huffman goeden

Mae'r gwaith o adeiladu y cod Huffman yn mewnbwn gan y llythrennau'r wyddor. Gynhyrchir rhestr o safleoedd sydd yn rhad ac am ddim yn y goeden cod dyfodol. Mae'n rhaid i'r pwysau bob nod yn y rhestr yr un fath ag y tebygolrwydd o ddigwydd o swyddi llythyrau sy'n cyfateb i nod hwn. Yn yr achos hwn, yr un sy'n pwyso lleiaf ei ddewis o blith nifer o safleoedd rhad ac am y goeden yn y dyfodol. Yn yr achos hwn, os bydd y cyfraddau isaf yn cael eu dilyn mewn sawl safle, byddwch yn gallu rhydd ddewis unrhyw un o'r parau. Yna daw'r y rhiant nôd, y mae'n rhaid iddo bwyso cymaint ag y swm y pwysau y pâr o nodau greu. Ar ôl hynny, mae rhieni yn anfon y rhestr gyda'r toiledau am ddim, ac mae'r plant yn cael eu symud. Yn yr arc hwn yn ddangosyddion priodol, rhai a sero. Ailadroddir y broses hon gymaint ag sydd ei angen i gadw dim ond un nod sengl. Yna ysgrifennwch y digidau deuaidd o'r top i'r gwaelod.

Gwella effeithlonrwydd cywasgu

Er mwyn cynyddu effeithlonrwydd cywasgu, mae angen yn ystod y cod adeiladu coeden i ddefnyddio'r holl ddata ar y tebygolrwydd o ddigwydd o'r llythyrau mewn ffeil benodol, ynghlwm wrth goeden, a pheidio â gadael i'r ffaith eu bod yn cael eu gwasgaru dros nifer fawr o ddogfennau testun. Os bydd y cyn y daith gerdded drwy'r y ffeil, gallwch gyfrifo'r ystadegau o sut yn union aml mae llythyrau o'r cyfleuster yn amodol ar y cywasgu.

Cyflymiad y broses cywasgu

Er mwyn cyflymu'r broses o algorithm, dylai'r diffiniad o'r llythyrau yn cael ei wneud nid yn nhermau y tebygolrwydd o ddigwydd o lythyr penodol, a pha mor aml iddo ddigwydd. Gyda'r algorithm hwn yn dod yn haws, ac yn gweithio gyda hwy yn gynt o lawer. mae hefyd yn osgoi'r gweithrediadau sy'n gysylltiedig â'r is-adran fel y bo'r angen-pwynt. Yn ogystal, yn gweithio yn y modd hwn, nid y cod Huffman deinamig, neu yn hytrach yr algorithm ei hun yn amodol ar unrhyw newidiadau. Mae hyn yn bennaf oherwydd y ffaith bod y tebygolrwydd yn cyfrannedd union pa mor aml. Mae'n werth talu sylw at y ffaith bod y pwysau terfynol y ffeil, neu'r hyn a elwir yn nod gwraidd yn hafal i swm y nifer o gymeriadau yn y gwrthrych i gael eu trin.

casgliad

Codau Huffman - syml ac yn hir-sefydledig algorithm, a ddefnyddir o hyd gan lawer o raglenni a chwmnïau adnabyddus. Gall ei symlrwydd ac eglurder yn cyflawni canlyniadau effeithiol cywasgu ffeiliau o unrhyw gyfaint ac yn sylweddol yn lleihau'r gofod ar storio ddisg. Mewn geiriau eraill, mae'r algorithm Huffman - wedi cael ei ymchwilio hir ac nid diagram gwaith a brys yn cael ei leihau gan y diwrnod hwn. A chyda'r gallu i leihau maint y ffeil, eu trosglwyddo dros rwydwaith neu drwy ddulliau eraill ei fod yn fwy syml, yn gyflym a chyfleus. Gan weithio gyda'r algorithm, gallwch cywasgu unrhyw wybodaeth yn gyfan gwbl heb niweidio ei strwythur ac ansawdd, ond gydag effaith mwyaf posibl i leihau'r ffeil pwysau. Mewn geiriau eraill, mae'r codio y cod Huffman wedi bod, ac yn parhau i fod y dull mwyaf poblogaidd a pherthnasol o gywasgu maint y ffeil.