Huffman còdan: eisimpleirean iarrtas

Aig an àm seo, chan eil mòran dhaoine a 'smaoineachadh mu dheidhinn an dearbh, mar a tha a' dèanamh am faidhl dlùthadh. An coimeas ris a roimhe cleachdadh an coimpiutair pearsanta air a bhith mòran nas fhasa. Agus cha mhòr a h-uile neach ag obair le siostam am faidhle a 'cleachdadh faidhlichean. Ach beagan dhaoine a 'smaoineachadh mu dheidhinn mar a tha iad ag obair agus dè a' bhunait a tha am faidhl dlùthadh. A 'chiad dreach den phròiseas seo bha an Huffman còdan, agus tha iad a cleachdadh an-diugh ann an diofar mòr-chòrdte archivers. Tha mòran luchd-cleachdaidh nach eil fiù 's smaoineachadh air dè cho furasta am faidhl dlùthadh a' gabhail àite agus tha e ag obair air an sgeama. Anns an aiste seo tha sinn a 'coimhead air mar a tha an dlùthadh tha nuances cuideachadh a' luathachadh a dhèanamh nas sìmplidhe agus am pròiseas còdachadh, cho math ri fhaicinn dè am prionnsabal a 'chraobh chòdaidh.

Eachdraidh algairim

Tha a 'chiad algairim èifeachdach còdadh fiosrachadh eileagtronaigeach air a bhith a code Huffman a mholadh cho tràth ri am meadhan an fhicheadamh linn,' se sin ann an 1952. B 'e esan a tha' aig an àm seo tha bonn-eileamaid den mhòr-chuid de na prògraman a chruthachadh gus compress am fiosrachadh. Aig an àm seo, aon de na stòran as motha fèill a 'cleachdadh còd seo tha tasglainn Zip, ARJ, RAR agus mòran eile. Cuideachd, an Huffman algairim air a chleachdadh gus compress JPEG-ìomhaighean agus nithean eile grafaigeach. Uill, tha a h-uile facs cuideachd a 'cleachdadh nuadh còdadh, a chruthachadh ann an 1952. Ged a bhon a 'cruthachadh a' chòd a thug e cho mòran ùine gus an là'n diugh tha e air a chleachdadh ann an caochladh ùr membranes agus uidheamachd seann agus nuadh-seòrsa.

Tha am prionnsapal èifeachdach còdadh

Tha bun-stèidh nan Huffman algairim gabhail a-steach sgeama a leigeas leibh a dhol an àite a 'chuid as motha bhrìoghmhor, gu tric a' chuid as motha a 'tachairt samhlaidhean a chòdadh Binary siostam. Agus an fheadhainn a tha cho cumanta, a chur an àite na b 'fhaide còdan. A 'dol fada Huffman còdan dìreach an dèidh an siostam a' cleachdadh na h-uile 'char as lugha luachan. Alt seo a 'leigeil leat lùghdachadh fad an còd airson gach samhla a' chiad teachdaireachd gu lèir. Tha àite cudromach a tha aig toiseach a 'còdadh coltachd a nochdas de na litrichean a bu chòir a bhith mar-thà aithnichte. Tha e bhuapa thèid a dheasachadh agus a 'chuairt dheireannach an teachdaireachd. Stèidhichte air an dàta sin, tha e air a dhèanamh a 'togail Huffman Còd a' chraobh, air an stèidh a thèid a chumail litrichean còdachadh pròiseas anns an tasglann.

Huffman còd, mar eisimpleir

Gus sealltainn an algairim, beachdachadh air grafaigeach coltach togail an còd craobh. Airson a 'cleachdadh an dòigh seo gu bhith èifeachdach, tha e riatanach a bhith a' soilleireachadh air a 'mhìneachadh air cuid de na luachan a dh'fheumar airson bun-bheachd a' phròiseas. Tha an seata de an iomadalachd nan àiteachan agus arcs, a tha air an stiùireadh bho node gu node, ris an canar an graf. Tha a 'chraobh a th' graf le seata de feartan sònraichte:

• anns gach node dòcha gabhail a-steach nach eil barrachd air aon de na arcs;
• aon de na àiteachan a dh'fheumas a bhith bun na craoibh, 'se sin, cha bu chòir dha a bhith na phàirt de arc aig a h-uile;
• ma tha an claigeann-toisich a 'tòiseachadh a' gluasad sìos an arcs, bu chòir am pròiseas a cheadachadh gus faighinn gu tur ann an gin de na h-àiteachan.

Tha e cuideachd a leithid a rud, pàirt de Huffman còdan mar dhuilleach na craoibhe. 'S e node bho nach bu chòir a dhol sam bith arc. Ma tha dà àiteachan a tha air an ceangal le arc, tha aon dhiubh pàrant eile de na leanabh, a rèir bho a node an arc dol a-mach, agus dè tha a 'gabhail a-steach. Ma tha dà àiteachan tha an aon phàrant node, tha iad a ghairm a phiuthar làraich. Ma tha, ann an duilleach, a 'fàgail bho àiteachan de ghrunn arcs, an uair sin tha e air a ghairm Binary craobh. Dìreach mar sin tha an Huffman craobh. Tha sònraichte de thogail na h-aonadan a tha an cuideam gach pàrant a tha co-ionann ris an t-suim de na cuideaman de na h-uile a 'chlann àiteachan.

An algairim airson togail a 'chraobh Huffman

Tha an obair togail air a 'chòd Huffman taic bho na litrichean na h-aibidil. Cruthachadh liosta de làraichean a tha saor san àm ri teachd code craobh. Tha cuideam gach node anns an liosta a dh'fheumas a bhith an aon rud mar a tha an coltachd a nochdas de na litrichean dreuchdan a rèir a node seo. Anns a 'chùis seo, am fear a cuideam a' char as lugha a tha a thaghadh bho am measg grunn Saor an-asgaidh làraich san àm ri teachd craobh. Anns a 'chùis seo, ma tha a' char as lugha ìrean amharc ann an grunn làraichean-lìn, faodaidh sibh saor thaghadh sam bith de na càraidean. An sin thig an cruthachadh pàrant node, a dh'fheumas a cudthrom cho math an t-suim de na cuideaman an paidhir de àiteachan. Às dèidh sin, pàrantan a chur an liosta le saor taighean-beaga, agus a 'chlann a thoirt air falbh. Ann an seo tha iomchaidh comharran arc, agus an fheadhainn zeros. Tha am pròiseas seo a-rithist cho math feum a chumail aon node. An sin sgrìobh a-mach an Binary meuran-aireamh bho mhullach gu bonn.

Leasachadh na èifeachdas dlùthadh

Ann gus meudachadh air an dlùthadh èifeachdas, tha e riatanach aig àm craobh togalach còd a chleachdadh fad na h-dàta air an coltachd a nochdas de na litrichean ann faidhle àraidh, ceangailte ris a 'chraoibh, agus nach eil a' leigeil air gur e tha iad sgapte thar àireamh mhòr de sgrìobhainnean teacsa. Ma tha an ro-coiseachd tro fhaidhle seo, faodaidh tu obrachadh a-mach anns a 'bhad na staitistig cho tric' sa tha na litrichean an goireas ùmhlachd do na dlùthadh.

Luathachadh a 'dlùthadh phròiseas

Airson luathachadh an algairim, a 'mìneachadh de na litrichean nach bu chòir a dhèanamh a thaobh an coltachd a nochdas sònraichte litir, agus an tricead a' tachairt. Le seo algairim a 'fàs na b' fhasa, agus ag obair còmhla riutha fada nas luaithe. tha e cuideachd a 'seachnadh an obair co-cheangailte leis a' flodradh-phuing sgaradh. A thuilleadh air sin, ag obair ann am modh seo, an fiùghantach Huffman code, no an àite an algairim fhèin nach eil cuspair ri atharrachaidhean sam bith. 'S e seo sa mhòr-chuid mar thoradh air gu bheil an coltas a tha dìreach co-roinneil ris an tricead. 'S fhiach pàigheadh aire gu bheil a' chuairt dheireannach de chuideam an fhaidhle, no a 'cho-ainm freumh node co-ionann ris an t-suim air an àireamh de charactaran ann an nì a thèid a làimhseachadh.

co-dhùnadh

Huffman còdan - sìmplidh agus fad-stèidheachadh algairim, a tha fhathast air a chleachdadh le mòran ainmeil prògraman agus companaidhean. Tha simplidheachd agus soilleireachd a choileanadh èifeachdach toraidhean compress faidhlichean sam bith tomhas-lìonaidh agus lùghdachadh mòr air an àite-stòraidh diosg. Ann am briathran eile, tha an Huffman algairim - air a bhith fada a bhith a 'rannsachadh agus obair diagram a tha a' chabhag Chan eil lùghdachadh le bhith an latha seo. Agus leis a 'chomas a lùghdachadh meud na faidhlichean a ghluasad thairis iad lìonra eile no le bhith a' ciallachadh gu bheil e nas sìmplidh, luath agus goireasach. Ag obair còmhla ris an algairim, faodaidh sibh fiosrachadh sam bith a compress tur gun chron a thoirt a-structar agus càileachd, ach le as àirde tron bhuaidh a lùghdachadh cuideam faidhle. Ann am briathran eile, a 'còdadh an Huffman còd air a bhith agus tha e fhathast a' chuid as motha agus a 'còrdadh buntainneach dòigh compressing an meud an fhaidhle.