Application mga halimbawa: mga code Huffman

Sa sandaling ito, ilang mga tao isipin ang tungkol sa ang katunayan, kung paano gumagana ang file compression. Kung ikukumpara sa nakaraang paggamit ng mga personal na computer ay naging lubhang mas madaling. At halos bawat taong nagtatrabaho kasama ang file system ay gumagamit ng mga file. Ngunit ilang mga tao sa tingin tungkol sa kung paano gumagana ang mga ito at kung ano ang batayan ay file compression. Ang pinakaunang bersyon ng prosesong ito ay ang Huffman code, at ginagamit ang mga ito ngayon sa isang iba't ibang mga popular na archivers. Maraming mga gumagamit ay hindi kahit na sa tingin kung gaano kadali file compression maganap at ito ay gumagana sa isang scheme. Sa artikulong ito tinitingnan namin ang kung paano ang compression ay kung ano ang mga nuances ng tulong bilis up at pasimplehin ang proseso ng pag-encode, pati na rin makita kung ano ang prinsipyo ng puno coding.

algorithm kasaysayan

Ang pinakaunang algorithm ng mahusay na coding ng mga elektronikong impormasyon ay naging isang code Huffman ipinanukalang kasing aga ng kalagitnaan ng ikadalawampu siglo, lalo sa 1952. Ito ay siya na sa sandaling ito ay ang batayang elemento ng ang karamihan ng mga programa na nilikha upang i-compress ang impormasyon. Sa sandaling ito, isa sa mga pinaka-popular na mga pinagkukunan gamit ang code na ito ay archive ZIP, ARJ, RAR at marami pang iba. Gayundin, ang Huffman algorithm ay ginagamit upang i-compress ang JPEG-imahe at iba pang mga graphic na mga bagay. Well, ang lahat ng faxes ay gumagamit din ng modernong coding, na naimbento noong 1952. Sa kabila ng ang katunayan na ang simula ng paglikha ng mga code kinuha sa gayon karaming oras sa araw na ito ito ay ginagamit sa isang iba't ibang mga bagong lamad at ang mga kagamitan luma at modernong uri.

Ang prinsipyo ng mahusay na coding

Ang batayan ng Huffman algorithm ay nagsasama ng isang scheme na nagpapahintulot sa iyo upang palitan ang pinaka-kapani-paniwala, pinaka-madalas na nagaganap simbolo coded binary system. At ang mga taong ay mas karaniwan, pinalitan ng mas mahabang mga code. Pupunta mahabang Huffman code ay nangyayari lamang matapos ang sistema ay gumagamit ng lahat ng mga minimum na halaga. pamamaraan na ito ay nagbibigay-daan sa iyo upang i-minimize ang haba ng code para sa bawat simbolo ng ang orihinal na mensahe bilang isang buo. Ang mahalagang punto ay na sa simula ng coding posibilidad ng paglitaw ng mga titik ay dapat na nai-kilala. Ito ay mula sa mga ito ay magiging handa at ang pangwakas na mensahe. Batay sa mga data, dinala ito sa pagtatayo ng code puno Huffman, sa batayan ng kung saan ay gaganapin titik proseso ng encoding sa archive.

Huffman code, halimbawa

Upang ilarawan ang mga algorithm, isaalang-alang ang isang graphical na variant ng konstruksiyon ng puno code. Upang gamitin ang paraan upang maging mabisa, ito ay kinakailangan upang linawin ang kahulugan ng ilang mga halaga na kinakailangan para sa ang konsepto ng proseso. Ang hanay ng mayorya ng mga nodes at arcs, na kung saan ay itinuro mula sa node sa node, na tinatawag graph. Tree mismo ay isang graph na may isang hanay ng mga tukoy na mga katangian:

• sa bawat node ay maaaring magsama ng hindi hihigit sa isa sa mga arcs;
• isa sa mga nodes ay dapat na ang mga ugat ng puno, iyon ay, hindi ito dapat maging bahagi ng arc sa lahat;
• kung ang stem simulan ang paglipat sa kahabaan ng mga arko, ang proseso ay dapat na payagan upang makakuha ng ganap na sa alinman sa mga node.

Mayroon ding tulad ng isang bagay, bahagi ng Huffman code bilang dahon ng puno. Ito ay isang node mula sa kung saan ay hindi dapat pumunta sa anumang arc. Kung dalawa nodes ay konektado sa pamamagitan ng isang arc, isa sa mga ito ay ang magulang ng ibang bata, depende sa kung saan buko ang arc napupunta out, at ano ang kasama. Kung dalawa nodes ay may parehong magulang na node, sila ay tinatawag na kapatid na babae site. Kung, sa dahon, dahon mula sa mga nodes sa ilang mga arcs, pagkatapos ito ay tinatawag na isang binary puno. Para lang ay puno Huffman. Ang kakaibang uri ng ang konstruksiyon ng mga yunit ay na ang bigat ng bawat magulang ay katumbas ng sum ng mga timbang ng lahat ng mga bata sa kanyang mga node.

Isang algorithm para sa paggawa ng puno Huffman

Ang konstruksiyon ng Huffman code ay input mula sa mga titik ng alpabeto. Binuo ng isang listahan ng mga site na ay libre sa hinaharap puno code. Ang bigat ng bawat node sa listahan ay dapat na ang parehong bilang ang posibilidad ng paglitaw ng mga post titik naaayon sa node na ito. Sa kasong ito, ang isa na may bigat ng hindi bababa sa ay napili mula sa gitna ng ilang mga libreng sites ng puno hinaharap. Sa kasong ito, kung ang minimum rate ay sinusunod sa ilang mga site, maaari mong malayang pumili ng alinman sa mga pares. Pagkatapos ay dumating ang paglikha ng mga magulang na node, na dapat timbangin ng mas maraming bilang ang kabuuan ng mga weights ng mga pares ng mga node. Pagkatapos nito, ang mga magulang magpadala ng mga listahan na may libreng toilet, at ang mga bata ay inalis. Sa ganitong arc naaangkop tagapagpabatid, bago at mga zero. Ang prosesong ito ay paulit-ulit na hangga't kinakailangan upang panatilihin lamang ng isang solong node. Pagkatapos ay isulat ang mga binary na numero mula sa itaas hanggang sa ibaba.

Pagpapabuti ng kahusayan ng compression

Upang dagdagan ang compression kahusayan, ito ay kinakailangan sa panahon ng puno building code upang magamit ang lahat ng mga data sa ang posibilidad ng paglitaw ng mga titik sa isang partikular na file, naka-attach sa isang puno, at hindi payagan ang katunayan na ang mga ito ay nakakalat sa loob ng isang malaking bilang ng mga dokumento teksto. Kung ang pre-lakad sa pamamagitan ng file na ito, maaari mong agad na kalkulahin ang mga istatistika ng kung gaano kadalas may mga titik ng pasilidad napapailalim sa compression.

Acceleration ng proseso ng compression

Upang mapabilis ang algorithm, ang kahulugan ng ang mga titik ay dapat gawin nang hindi sa mga tuntunin ng ang posibilidad ng paglitaw ng isang partikular na sulat, at ang dalas ng paglitaw nito. Gamit ang algorithm ay nagiging mas madali, at gumagana sa mga ito nang mas mabilis. ito rin avoids ang operasyon kaugnay sa mga lumulutang-point division. Bilang karagdagan, nagtatrabaho sa mode na ito, ang mga dynamic Huffman code, o sa halip ang algorithm mismo ay hindi napapailalim sa anumang mga pagbabago. Ito ay unang-una dahil sa ang katunayan na ang mga probabilities ay direkta proporsyonal sa dalas. Ito ay nagkakahalaga ng nagbabayad ng pansin sa ang katunayan na ang pangwakas na bigat ng file, o ang tinatawag na root node ay katumbas ng sum ng bilang ng mga character sa object upang magamot.

konklusyon

Huffman code - simple at pang-itinatag algorithm, na kung saan ay pa rin na ginagamit ng maraming mga mahusay na kilala mga programa at mga kumpanya. Pagiging simple at kaliwanagan ay maaaring makamit ang epektibong mga resulta compress ang mga file ng anumang dami at makabuluhang bawasan ang puwang sa disk imbakan. Sa ibang salita, ang Huffman algorithm - ay mahaba ay investigated at trabaho diagram na pangangailangan ng madaliang pagkilos ay hindi mababawasan ng araw na ito. At sa pamamagitan ng kakayahan upang mabawasan ang sukat ng file, ilipat ang mga ito sa loob ng isang network o sa pamamagitan ng iba pang ibig sabihin nito ay mas simple, mabilis at maginhawa. Paggawa gamit ang algorithm, maaari mong i-compress ang anumang impormasyon ganap na walang pinsala sa kaayusan nito at kalidad, ngunit may maximum na epekto upang mabawasan ang bigat ng file. Sa ibang salita, ang coding ng Huffman code ay at ay mananatiling ang pinaka-popular at may-katuturang paraan ng pigain ang sukat ng file.