Huffman koodid: näited taotluse

Praegu vähesed inimesed mõtlevad asjaolu, kuidas faili kokkusurumine. Võrreldes eelmise kasutada personaalarvuti on muutunud palju lihtsamaks. Ja peaaegu iga inimene, kes töötab koos failisüsteemi kasutab faile. Aga mõned inimesed mõtlevad, kuidas nad töötavad ja mis alusel on faili kokkusurumine. Kõige esimene versioon sellest protsessist olid Huffman koodid ja neid kasutatakse tänapäeval erinevaid populaarne archivers. Paljud kasutajad ei saa isegi mõelda, kui lihtne failide tihendamise toimub ja see töötab skeem. Selles artiklis vaatleme, kuidas compression on see, mida lisavärvingut kiirendada ja lihtsustada protsessi kodeerimine, samuti näha, mida põhimõtteliselt puu kodeerimine.

Ajalugu algoritm

Kõige esimene algoritm efektiivse kodeerimise elektrooniline teave on muutunud koodi Huffman ettepanek juba keset kahekümnenda sajandi, nimelt 1952. aastal. See oli tema, kes hetkel on põhielement enamiku programmide loodud suruma teavet. Praegu üks populaarsemaid allikatest, kasutades seda koodi on arhiivi ZIP, ARJ, RAR ja paljud teised. Samuti Huffman algoritmi kasutatakse tihendamiseks JPEG-piltide ja muude graafiliste objektide kohta. Noh, kõik faksid ka kasutades kaasaegseid kodeerimine, leiutas 1952. aastal. Vaatamata sellele, et kuna loomist kood võttis nii palju aega, et sellel päeval on kasutatud erinevaid uusi membraane ja seadmed vana ja kaasaegse liiki.

Põhimõte efektiivse kodeerimise

Alusel Huffman algoritm sisaldab kava, mis võimaldab teil asendada kõige usaldusväärsema, kõige sagedamini esinev sümbolid kodeeritud binaarne süsteem. Ja need, kes on vähem levinud, asendati enam koodid. Lähen kaua Huffman koodid toimub alles pärast süsteem kasutab kõiki minimaalsed väärtused. See meetod võimaldab teil minimeerida pikkus koodi iga sümbol algse sõnumi tervikuna. Oluline on, et alguses kodeerimine esinemise tõenäosus tähed tuleks juba teada. On neilt on valmis ja viimane sõnum. Nende andmete põhjal, siis teostatakse ehituse Huffman koodipuu, tuginedes mis toimub tähtede kodeering protsess arhiivi.

Huffman koodi, näiteks

Et illustreerida algoritmi, leiavad graafiline variant ehitamiseks kood puu. Et kasutada seda meetodit oleks tõhus, on vaja täpsustada mõiste teatud väärtusi, mis on vajalikud mõiste protsessi. Komplekt on sõlmede paljusus ja kaared, mis on suunatud alates sõlmest sõlme, mida nimetatakse graafik. Puu ise on graafik, millel on rida konkreetseid omadusi:

• Iga sõlme võib sisaldada mitte rohkem kui üks kaari;
• sõlm peab olema puu juur, mis on, ei tohiks see olla osa kaare üldse;
• kui vars hakata liikuma mööda kaared, protsess peaks võimaldama saada täiesti ükskõik sõlmed.

On ka selline asi, osa Huffman koodid lehena puu. See on sõlm, millest ei tohiks minna kaar. Kui kaks sõlmed on ühendatud kaarega, üks neist on vanem teise lapse, sõltuvalt kust sõlme kaar kustub ja mis on kantud. Kui kaks sõlmede on sama vanem sõlme, et nad on kutsutud õde saitidele. Kui lehed, väljub sõlmede mitu kaared, siis nimetatakse Binääripuu. Just nii on Huffman puu. Omapära ehitus üksused on, et kaalu iga vanem on võrdne kaalude summa kõigi oma järglast.

Algoritm ehitamiseks puu Huffman

Ehitust Huffman kood on sisendi tähestiku. Loodud nimekirja saite, mis on vaba tulevikus koodipuu. Kaal iga sõlme loetelu peab olema sama esinemise tõenäosus tähed postitused vastab sellele sõlme. Sel juhul see, kes kaalub vähemalt on valitud mitu tasuta saite tuleviku puu. Sel juhul kui alammäärasid on täheldatud mitmeid saite, võite vabalt valida mistahes paarikaupa. Siis tuleb loomine vanem sõlme, mis peavad kaaluma nii palju kui summa kaalusid paari sõlmed. Pärast seda, vanemad saadavad nimekirja vaba tualettide ja lapsed on eemaldatud. Selles kaar on asjakohased näitajad, ühtesid ja nulle. Seda protsessi korratakse nii palju kui vaja, et hoida vaid ühe sõlme. Siis kirjuta välja kahendnumbrist ülevalt alla.

Tõhustamise kohta compression

Et suurendada tihendamise efektiivsus on vaja kasutada puu hoone kood kasutada kõiki andmeid esinemise tõenäosus tähed konkreetse faili, mis on seotud puu ja ei võimalda asjaolu, et nad on hajutatud üle paljude tekstidokumente. Kui eelnevalt jalutuskäik läbi selle faili, saate kohe arvutada statistika, kui tihti on tähed rajatis suhtes compression.

Kiirendus kompressiooniprotsesside

Et kiirendada algoritmi mõiste tähed tuleks teha mitte nii esinemise tõenäosus konkreetse kirja ja selle esinemissageduse. Selle algoritmi muutub lihtsamaks ja teha nendega palju kiiremini. Samuti väldib seotud toimingud murdarv rajoon. Lisaks töötab selles režiimis, dünaamiline Huffman kood, või pigem algoritmi ennast ei kehti mingeid muudatusi. See on peamiselt tingitud asjaolust, et tõenäosused on võrdeline sagedusega. Tasub pöörata tähelepanu asjaolule, et lõpliku kaalu faili või nn Juursõlme on võrdne summaga arvu tähemärki töödeldava objekti.

järeldus

Huffman koodid - lihtne ja pikaajaline algoritm, mida kasutatakse veel paljud tuntud programmide ja ettevõtted. Selle lihtsuse ja selguse võimalik saavutada tõhusaid tulemusi suruma faile mis tahes mahus ja oluliselt vähendada ruumi salvestamise. Teiste sõnadega, Huffman algoritm - on pikka aega uuritud ja koo skeemi, mis kiiremas korras ei vähenda see päev. Ja võime vähendada failide suurusest, kanda neid üle võrgu või muude vahenditega on lihtne, kiire ja mugav. Töö algoritmi, saate suruma tahes teavet täiesti kahjustamata oma struktuuri ja kvaliteeti, kuid maksimaalse efekti vähendada kaalu faili. Teisisõnu, kodeerimise Huffman kood on olnud ja jääb kõige populaarsem ja asjakohase kokkusurumise faili suurus.