Huffman-koodit: esimerkkejä, sovellus

Tällä hetkellä harvat ajattelevatKuinka tiedostojen pakkaus toimii? Aiempiin verrattuna henkilökohtaisen tietokoneen käyttö on tullut paljon helpompaa. Ja lähes jokainen tiedostojärjestelmän kanssa työskentelevä henkilö käyttää arkistoja. Mutta harvat ihmiset ajattelevat, kuinka ne toimivat ja millä periaatteella tiedostojen pakkaus tapahtuu. Tämän prosessin ensimmäinen versio oli Huffman-koodit, ja niitä käytetään edelleen useissa suosituissa arkistoissa. Monet käyttäjät eivät edes ajattele kuinka helppoa tiedoston pakkaaminen on ja miten se toimii. Tässä artikkelissa tarkastellaan, kuinka pakkaus tapahtuu, mitkä vivahteet auttavat nopeuttamaan ja yksinkertaistamaan koodausprosessia, ja ymmärrämme myös koodauspuun rakentamisen periaatteen.

Algoritmin historia

Ensimmäinen algoritmi tehokkaan suorittamiseenSähköisen tiedon koodaus oli Huffmanin ehdottama koodi 1900-luvun puolivälissä, nimittäin vuonna 1952. Juuri tämä on tällä hetkellä useimpien tietojen pakkaamiseen luotujen ohjelmien tärkein peruselementti. Tällä hetkellä suosituimpia tätä koodia käyttäviä lähteitä ovat ZIP, ARJ, RAR ja monet muut arkistot.

Tätä Huffman-algoritmia käytetään myösJPEG-kuvien ja muiden graafisten objektien pakkaus. No, kaikki nykyaikaiset faksit käyttävät myös koodausta, joka keksittiin vuonna 1952. Huolimatta siitä, että koodin luomisesta on kulunut niin paljon aikaa, sitä käytetään edelleen uusimmissa kuorissa ja vanhoissa ja nykyaikaisissa laitteissa.

Tehokas koodausperiaate

Huffman-algoritmi perustuu piiriinjonka avulla voit korvata todennäköisimmät, useimmin esiintyvät merkit binäärijärjestelmäkoodeilla. Ja ne, jotka ovat vähemmän yleisiä, korvataan pidemmillä koodeilla. Siirtyminen pitkiin Huffman-koodeihin tapahtuu vasta, kun järjestelmä on käyttänyt kaikki minimiarvot. Tämän tekniikan avulla voit minimoida koodin pituuden jokaiselle alkuperäisen viestin merkille kokonaisuutena.

Tärkeintä on, että alussakoodaustodennäköisyydet kirjainten esiintymiselle on jo tiedettävä. Näistä kootaan lopullinen viesti. Näiden tietojen perusteella muodostetaan Huffman-koodipuu, jonka pohjalta suoritetaan arkiston kirjainten koodausprosessi.

Esimerkki Huffman koodista

Otetaan algoritmin havainnollistamiseksigraafinen versio koodipuun rakentamisesta. Jotta tämän menetelmän käyttö olisi tehokasta, on syytä selventää joidenkin tämän menetelmän käsitteen kannalta välttämättömien arvojen määrittelyä. Kaarien ja solmujen joukkoa, jotka on suunnattu solmusta solmuun, kutsutaan yleensä graafiksi. Puu itsessään on kaavio, jolla on joukko tiettyjä ominaisuuksia:

• kukin solmu voi sisältää enintään yhden kaarista;
• yhden solmuista on oltava puun juuri, eli se ei saa sisältää kaaria ollenkaan;
• Jos aloitat liikkumisen kaaria pitkin juuresta, tämän prosessin pitäisi antaa sinun päästä ehdottomasti mihin tahansa solmuun.

Myös tällainen käsite sisältyy koodeihinHuffman kuin puun lehti. Se edustaa solmua, josta ei pitäisi syntyä kaaria. Jos kaksi solmua on yhdistetty kaarella, toinen niistä on vanhempi, toinen lapsi, riippuen siitä, mistä solmusta kaari lähtee ja mihin se tulee. Jos kahdella solmulla on sama pääsolmu, niitä kutsutaan yleisesti sisarussolmuiksi. Jos lehtien lisäksi solmuissa on useita kaaria, tätä puuta kutsutaan binääriksi. Juuri tätä Huffman-puu on. Tämän rakenteen solmujen erikoisuus on, että kunkin vanhemman paino on yhtä suuri kuin sen kaikkien solmulapsien painojen summa.

Huffman-puun rakennusalgoritmi

Huffman-koodin rakenne on tehty kirjaimistasyöttöaakkoset. Muodostetaan luettelo solmuista, jotka ovat vapaita tulevassa koodipuussa. Tämän luettelon jokaisen solmun painon on oltava sama kuin kyseistä solmua vastaavan sanoman kirjaimen esiintymistodennäköisyys. Tässä tapauksessa useiden tulevan puun vapaiden solmujen joukosta valitaan se, joka painaa vähiten. Lisäksi, jos vähimmäisindikaattoreita havaitaan useissa solmuissa, voit vapaasti valita minkä tahansa pareista.

Sen jälkeen luodaan vanhempisolmu, jonka pitäisi painaa yhtä paljon kuin tämän solmuparin summa. Tämän jälkeen vanhempi lähetetään luetteloon vapailla solmuilla ja lapset poistetaan. Tässä tapauksessa kaaret saavat vastaavat indikaattorit, ykköset ja nollat. Tätä prosessia toistetaan vain niin kauan, että jäljelle jää vain yksi solmu. Sitten binäärinumerot kirjoitetaan ylhäältä alas.

Kompressiotehokkuuden parantaminen

Pakkauksen tehokkuuden parantamiseksi sinun onKun rakennat koodipuuta, käytä kaikkia tietoja, jotka koskevat kirjainten esiintymisen todennäköisyyttä tietyssä puuhun liitetyssä tiedostossa, äläkä anna niiden hajota suureen määrään tekstidokumentteja. Jos käyt ensin tämän tiedoston läpi, voit heti laskea tilastot siitä, kuinka usein pakattavan objektin kirjaimia esiintyy.

Pakkausprosessin nopeuttaminen

Algoritmin nopeuttamiseksi kirjainten tunnistaminenei tulisi suorittaa tietyn kirjaimen esiintymistodennäköisyyden mukaan, vaan sen esiintymistiheyden mukaan. Tämän ansiosta algoritmi yksinkertaistuu ja työskentely sen kanssa on huomattavasti nopeampaa. Se myös välttää liukuluku- ja jakooperaatiot.

Lisäksi työskentely tässä tilassa, dynaaminenHuffman-koodia tai pikemminkin itse algoritmia ei muuteta. Tämä johtuu pääasiassa siitä, että todennäköisyydet ovat suoraan verrannollisia taajuuksiin. Erityistä huomiota kannattaa kiinnittää siihen, että tiedoston tai ns. juurisolmun lopullinen paino on yhtä suuri kuin käsiteltävän objektin kirjainten lukumäärän summa.

johtopäätös

Huffman-koodit - yksinkertaiset ja vakiintuneetalgoritmi, jota monet tunnetut ohjelmat ja yritykset käyttävät edelleen. Sen yksinkertaisuuden ja selkeyden ansiosta voit saavuttaa tehokkaita pakkaustuloksia kaikenkokoisille tiedostoille ja vähentää merkittävästi niiden tilaa tallennuslevyllä. Toisin sanoen Huffman-algoritmi on pitkään tutkittu ja kehitetty järjestelmä, jonka relevanssi ei ole heikentynyt tähän päivään mennessä.

Ja kiitos mahdollisuuden pienentää tiedostokokoa,niiden välittäminen verkon tai muun keinon kautta tulee helpommaksi, nopeammaksi ja mukavammaksi. Algoritmin kanssa työskentelemällä voit pakata täysin mitä tahansa tietoa vahingoittamatta sen rakennetta ja laatua, mutta vähentää tiedoston painoa mahdollisimman paljon. Toisin sanoen Huffman-koodaus on ollut ja on edelleen suosituin ja olennaisin menetelmä tiedostokoon pakkaamiseen.