Teabe tihendamise meetodid. Teabe tihendamise protsess selle mahu vähendamiseks

Kõik tihendusalgoritmid töötavad sisendteabevoo alusel, et saada mõne teisenduse kaudu kompaktsem väljundvoog. Kompressiooniprotsesside peamised tehnilised omadused ja nende töö tulemused on järgmised:

· tihendusaste – algse ja saadud voogude mahtude suhe;

·tihenduskiirus - aeg, mis kulub sisendvoos teatud hulga info tihendamiseks, kuni sellest saadakse samaväärne väljundvoog;

·tihenduskvaliteet on väärtus, mis näitab, kui tihedalt on väljundvoog tihendatud, kui sellele sama või mõne muu algoritmi abil uuesti tihendatakse.

Algoritme, mis kõrvaldavad andmete salvestamise liiasuse, nimetatakse andmete tihendamise algoritmideks või arhiveerimisalgoritmideks. Praegu on tohutul hulgal andmete tihendamise programme, mis põhinevad mitmel põhimeetodil.

Kõik andmete tihendamise algoritmid jagunevad järgmisteks osadeks:

) kadudeta pakkimisalgoritmid, mille kasutamisel taastatakse andmed vastuvõtvas otsas vähimategi muudatusteta;

) kadudega tihendusalgoritmid, mis eemaldavad andmevoost teabe, millel on andmete olemusele vähe mõju või mis on inimesele täiesti hoomamatu.

On kaks peamist kadudeta arhiveerimismeetodit:

Huffmani algoritm, mille eesmärk on tihendada baitide jadasid, mis ei ole üksteisega seotud,

Lempel-Ziv algoritm (inglise: Lempel, Ziv), mis keskendus mis tahes tüüpi tekstide tihendamisele, see tähendab "sõnade" korduva kordamise faktile - baitide jadadele.

Peaaegu kõik populaarsed kadudeta arhiveerimisprogrammid (ARJ, RAR, ZIP jne) kasutavad nende kahe meetodi kombinatsiooni - LZH-algoritmi.

Huffmani algoritm.

Algoritm põhineb asjaolul, et mõned tähemärgid standardsest 256 tähemärgist vabas tekstis võivad esineda sagedamini kui keskmine kordusperiood, teised vastavalt harvemini. Seega, kui tavaliste märkide salvestamiseks kasutatakse alla 8 pikkuseid bitijadasid ja haruldaste märkide salvestamiseks pikki bitijadasid, siis faili kogumaht väheneb.

Lempel-Ziv algoritm. Klassikaline Lempel-Ziv algoritm -LZ77, mis sai oma nime avaldamisaasta järgi, on äärmiselt lihtne. See on sõnastatud järgmiselt: kui sarnane baitide jada on juba esinenud eelmises väljundvoos ning kirje selle pikkuse ja nihke kohta praegusest positsioonist on lühem kui see jada ise, siis on viide (nihe, pikkus), ja mitte jada ise, kirjutatakse väljundfaili.

4. Faili tihendamise suhe

Arhiivifailides sisalduva teabe tihendamine saavutatakse liiasuse kõrvaldamise teel mitmel viisil, näiteks koodide lihtsustamisega, nendest konstantsete bittide kõrvaldamisega või korduvate märkide või korduva märgijada esitamisega kordusteguri ja vastavate märkide järgi. Sellise info pakkimise algoritmid on realiseeritud spetsiaalsetes arhiveerimisprogrammides (tuntuimad neist on arj/arjfolder, pkzip/pkunzip/winzip, rar/winrar) on kasutatud nii ühte kui ka mitut faili, mis on tihendatud. vorm paigutatakse nn arhiivifaili või arhiivi.

Failipakendamise eesmärk on tavaliselt tagada info kompaktsem paigutamine kettale, vähendades arvutivõrkude sidekanalite kaudu info edastamise aega ja vastavalt ka kulusid. Seetõttu on konkreetse arhiiviprogrammi tõhususe peamine näitaja faili tihendamise aste.

Faili tihendamise astet iseloomustab koefitsient Kc, mis on defineeritud kui tihendatud faili mahu Vc ja algse faili mahu Vo suhe, väljendatuna protsentides (mõned allikad kasutavad vastupidist suhet):

Ks=(Vc/Vo)*100%

Tihendusaste sõltub kasutatavast programmist, tihendusmeetodist ja lähtefaili tüübist.

Kõige paremini tihendatud failid on graafilised pildid, tekstifailid ja andmefailid, mille tihendussuhe võib ulatuda 5–40% -ni; käivitatavate programmide ja laadimismoodulite faile tihendatakse vähem - Kc = 60–90%. Arhiivifaile peaaegu ei tihendata. Seda pole raske seletada, kui tead, et enamik arhiveerimisprogramme kasutab tihendamiseks LZ77 (Lempel-Ziv) algoritmi variante, mille olemuseks on baitide (loe: märkide) korduvate jadade spetsiaalne kodeerimine. Selliste korduste esinemissagedus on kõrgeim tekstides ja punktgraafikas ning arhiivides on see praktiliselt nulli viidud.

Lisaks erinevad arhiveerimisprogrammid endiselt tihendusalgoritmide rakendamise poolest, mis vastavalt mõjutab tihendusastet.

Mõned arhiveerimisprogrammid sisaldavad lisaks tööriistu, mille eesmärk on vähendada tihendusastet Kc. Seega rakendab WinRAR programm pidevat (tahket) arhiveerimismehhanismi, mille abil on võimalik saavutada tavameetoditega võrreldes 10 - 50% kõrgem tihendusaste, eriti kui pakitud on märkimisväärne hulk sama tüüpi väikeseid faile.

Arhiveerijate omadused on pöördvõrdeliselt sõltuvad suurused. See tähendab, et mida suurem on tihenduskiirus, seda madalam on tihendusaste ja vastupidi.

Arvutiturul pakutakse palju arhiive – igaühel on oma toetatud vormingute komplekt, omad plussid ja miinused ning oma austajate ring, kes usuvad kindlalt, et nende kasutatav arhiiv on parim. Me ei heiduta kedagi ega midagi – proovime lihtsalt erapooletult hinnata populaarsemaid arhiive nii funktsionaalsuse kui ka tõhususe osas. Nende hulka kuuluvad WinZip, WinRAR, WinAce, 7-Zip – need juhivad tarkvaraserverites allalaadimiste arvu. Vaevalt on soovitatav kaaluda teisi arhiive, kuna neid kasutavate kasutajate protsent (allalaadimiste arvu järgi otsustades) on väike.

Enne faili või kausta tihendamise alustamist on väga oluline mõista kõiki sellest saadavaid eeliseid ja mõista Windows 7-s saadaolevaid tihendusmeetodeid:

• NTFS-failide tihendamine
• Kausta tihendamine (zip).

Andmete tihendamine vähendab faili suurust, minimeerides üleliigseid andmeid. Tekstifailis sisaldavad üleliigsed andmed sageli teatud märke, nagu tühik või tavalised vokaalid (e ja a), aga ka märgijadasid. Andmete tihendamine loob failist tihendatud versiooni, minimeerides need üleliigsed andmed.

Neid kahte tihendusmeetodit võrreldakse allpool. Lisaks käsitletakse erinevate failide ja kaustade mõju tihendatud failide ja kaustade jõudlusele.

NTFS-failisüsteem toetab failide tihendamist failipõhiselt. Failide tihendamise algoritm on siin kadudeta pakkimisalgoritm, mis tähendab, et faili tihendamisel ja lahtipakkimisel ei lähe andmed kaduma. Teiste algoritmide puhul läheb tihendamise ja sellele järgneva dekompressiooni ajal osa andmetest kaotsi.

NTFS-i tihendamisel, mis on saadaval NTFS-failisüsteemi kasutavatel kõvaketastel, on järgmised piirangud ja funktsioonid.

• Pakkimine on faili või kausta atribuut.
• NTFS-köites olevad kaustad ja failid on tihendatud või mitte.
• Uued tihendatud kaustas loodud failid tihendatakse vaikimisi.
• Tihendatud kausta olek ei pruugi kajastada selles kaustas olevate failide tihendamise olekut. Näiteks saab kaustu tihendada ilma nende sisu tihendamata ja mõned või kõik tihendatud kaustas olevad failid saab lahti pakkida.
• Töötage NTFS-i tihendatud failidega ilma neid lahti pakkimata, kuna need lahti ja uuesti tihendatakse ilma kasutaja sekkumiseta.
• Kui tihendatud fail avatakse, pakkib süsteem selle automaatselt lahti.
• Faili sulgemisel tihendab Windows selle uuesti.
• Äratundmise hõlbustamiseks kuvatakse NTFS-i tihendatud failide ja kaustade nimed erineva värviga.
• NTFS-tihendatud failid ja kaustad jäävad tihendatuks, ainult NTFS-köitel.
• NTFS-i tihendatud faile ei saa krüpteerida.
• Faili tihendatud baidid ei ole rakendustele juurdepääsetavad; nad näevad ainult tihendamata andmeid.
• Pakitud faile avavad rakendused saavad nendega töötada nii, nagu need oleksid tihendamata.
• Tihendatud faile ei saa teise failisüsteemi kopeerida.

Märge: NTFS-i tihendamise juhtimiseks saate kasutada kompaktset käsurea tööriista.

Tihendatud failide ja kaustade teisaldamine ja kopeerimine.

Teisaldatud või kopeeritud tihendatud failid ja kaustad võivad muuta nende tihendamise olekut. Allpool on viis olukorda, mis uurivad tihendatud failide ja kaustade kopeerimise ja teisaldamise mõju.

Kopeerimine NTFS-i partitsiooni sees.

Kuidas tihendatud faili või kausta olek muutub, kui kopeerite selle NTFS-i partitsiooni? Kui kopeerite faili või kausta NTFS-failisüsteemis, pärib partitsioon, fail või kaust sihtkausta tihendusoleku. Näiteks kui kopeerite tihendatud faili või kausta lahtipakkitud kausta, pakitakse fail või kaust automaatselt lahti.

Liikumine NTFS-i partitsiooni sisse.

Mis juhtub faili või kausta tihendamise olekuga, kui see teisaldatakse NTFS-i partitsioonis?

Kui teisaldate faili või kausta NTFS-i partitsioonis, säilitab fail või kaust oma esialgse tihendusoleku. Näiteks kui teisaldate tihendatud faili või kausta tihendamata kausta, jääb fail tihendatuks.

NTFS-i partitsioonide kopeerimine või teisaldamine.

Mis juhtub tihendatud faili või kaustaga, kui kopeerite või teisaldate selle NTFS-i partitsioonide vahel?

Kui teisaldate faili või kausta NTFS-sektsioonide vahel, pärib fail või kaust sihtkausta tihendusoleku. Kuna Windows 7 käsitleb partitsioonide vahelist liikumist koopiana, millele järgneb kustutamistoiming, pärivad failid sihtkausta tihendusoleku.

Kui kopeerite faili kausta, mis juba sisaldab sama nimega faili, võtab kopeeritud fail sihtfaili tihendusatribuudi, olenemata kausta tihendusolekust.

Kopeerige või liikuge FAT- ja NTFS-köidete vahel.

Mis juhtub faili tihendamisega, mida kopeeritakse või teisaldatakse FAT- ja NTFS-köidete vahel?

FAT-partitsioonile kopeeritud tihendatud failid muutuvad tihendamata, kuna FAT-mahud ei toeta tihendamist. Kui aga kopeerite või teisaldate faile FAT-partitsioonist NTFS-sektsiooni, pärivad need selle kausta tihendusatribuudi, kuhu need kopeerite.

Failide kopeerimisel arvutab NTFS-failisüsteem kettaruumi tihendamata faili suuruse põhjal. See on oluline, sest kopeerimise käigus faile ei tihendata ja süsteem peab tagama piisava ruumi. Kui proovite kopeerida tihendatud faili NTFS-i sektsiooni ja tihendamata faili jaoks pole vaba ruumi, kuvatakse teile veateade, mis teavitab teid, et faili jaoks pole piisavalt kettaruumi.

Head päeva.
Täna tahan puudutada andmete kadudeta pakkimise teemat. Hoolimata asjaolust, et Habré kohta oli juba artikleid, mis olid pühendatud mõnele algoritmile, tahtsin sellest veidi üksikasjalikumalt rääkida.
Püüan anda nii matemaatilise kirjelduse kui ka kirjelduse tavalisel kujul, et igaüks leiaks enda jaoks midagi huvitavat.

Selles artiklis käsitlen tihendamise põhiaspekte ja peamisi algoritmide tüüpe.

Kokkusurumine. Kas see on meie ajal vajalik?

Muidugi jah. Muidugi mõistame kõik, et nüüd on meil juurdepääs nii suuremahulistele andmekandjatele kui ka kiiretele andmeedastuskanalitele. Kuid samal ajal kasvab edastatava teabe maht. Kui mõni aasta tagasi vaatasime 700-megabaidiseid filme, mis mahuvad ühele plaadile, siis tänapäeval võivad HD-kvaliteediga filmid võtta kümneid gigabaite.
Kõige kokkupressimisest pole muidugi suurt kasu. Kuid ikkagi on olukordi, kus tihendamine on äärmiselt kasulik, kui see pole vajalik.

• Dokumentide saatmine e-posti teel (eriti suurtes kogustes dokumente mobiilseadmetega)
• Dokumentide avaldamisel veebisaitidel on vajadus liiklust kokku hoida
• Kettaruumi säästmine juhtudel, kui salvestusruumi asendamine või lisamine on keeruline. Näiteks juhtub see juhtudel, kui kapitalikulude eelarve koostamine pole lihtne ja kettaruumi pole piisavalt

Muidugi võime mõelda veel palju erinevaid olukordi, mille puhul kokkupressimisest kasu oleks, aga meile piisab neist paarist näitest.

Kõik tihendusmeetodid võib jagada kahte suurde rühma: kadudeta pakkimine ja kadudeta pakkimine. Kadudeta pakkimist kasutatakse juhtudel, kui teavet on vaja biti haaval taastada. Selline lähenemine on ainuvõimalik näiteks tekstiandmete tihendamisel.
Teatud juhtudel ei ole aga täpset info taastamist vaja ning lubatud on kasutada kadudeta pakkimist realiseerivaid algoritme, mis erinevalt kadudeta pakkimisest on enamasti lihtsamini teostatavad ja tagab suurema arhiveerimise.

Niisiis, liigume edasi kadudeta pakkimisalgoritmide kaalumise juurde.

Universaalsed kadudeta tihendusmeetodid

Üldiselt on tihendusalgoritmide aluseks kolm põhivalikut.
Esimene rühm meetodid – voo teisendus. See hõlmab uute sissetulevate tihendamata andmete kirjeldamist juba töödeldud andmete kaudu. Sel juhul tõenäosusi ei arvutata, sümbolid kodeeritakse ainult juba töödeldud andmete põhjal, nagu näiteks LZ-meetodites (nimetatud Abraham Lempeli ja Jacob Zivi järgi). Sel juhul asendatakse teatud alamstringi teine ​​ja edasised esinemised, mis on kodeerijale juba teada, viidetega selle esimesele esinemisele.

Teine rühm meetodid on statistilised tihendusmeetodid. Need meetodid jagunevad omakorda adaptiivseteks (või keermestatud) ja plokkideks.
Esimeses (adaptiivses) versioonis toimub uute andmete tõenäosuste arvutamine andmete põhjal, mida on kodeerimisel juba töödeldud. Need meetodid hõlmavad Huffmani ja Shannon-Fano algoritmide adaptiivseid versioone.
Teisel (ploki) juhul arvutatakse iga andmeploki statistika eraldi ja lisatakse tihendatud plokile endale. Nende hulka kuuluvad Huffmani, Shannon-Fano ja aritmeetilise kodeerimise meetodite staatilised versioonid.

Kolmas rühm meetodid on niinimetatud ploki teisendusmeetodid. Sissetulevad andmed jagatakse plokkideks, mis seejärel muudetakse tervikuna. Kuid mõned meetodid, eriti need, mis põhinevad plokkide ümberkorraldamisel, ei pruugi andmemahu märkimisväärset (või üldse) vähenemist põhjustada. Pärast sellist töötlemist paraneb aga andmestruktuur oluliselt ning hilisem tihendamine teiste algoritmidega on edukam ja kiirem.

Andmete tihendamise üldpõhimõtted

Kõik andmete tihendamise meetodid põhinevad lihtsal loogilisel põhimõttel. Kui kujutame ette, et kõige sagedamini esinevad elemendid on kodeeritud lühemate koodidega ja harvemini esinevad elemendid pikemate koodidega, siis kulub kõigi andmete salvestamiseks vähem ruumi kui siis, kui kõik elemendid oleksid sama pikkusega koodidega.
Täpset seost elementide sageduste ja optimaalsete koodipikkuste vahel kirjeldab nn Shannoni lähtekoodi teoreem, mis määrab maksimaalse kadudeta tihendamise piiri ja Shannoni entroopia.

Natuke matemaatikat

Kui elemendi s i esinemise tõenäosus on võrdne p(s i), siis oleks kõige soodsam seda elementi esitada log 2 p(s i) bittides. Kui kodeerimisel on võimalik tagada, et kõigi elementide pikkus väheneb log 2 p(s i) bitini, siis on kogu kodeeritud jada pikkus kõigi võimalike kodeerimismeetodite puhul minimaalne. Veelgi enam, kui kõigi elementide F = (p(s i)) tõenäosusjaotus on muutumatu ja elementide tõenäosused on üksteisest sõltumatud, saab koodide keskmise pikkuse arvutada järgmiselt.

Seda väärtust nimetatakse tõenäosusjaotuse F entroopiaks ehk allika entroopiaks antud ajahetkel.
Kuid tavaliselt ei saa elemendi ilmumise tõenäosus olla sõltumatu, vastupidi, see sõltub teatud teguritest. Sel juhul omandab tõenäosusjaotus F iga uue kodeeritud elemendi s i puhul teatud väärtuse F k, st iga elemendi jaoks F = F k ja H = H k.

Teisisõnu võime öelda, et allikas on olekus k, mis vastab teatud tõenäosuste hulgale p k (s i) kõigi elementide s i korral.

Seetõttu saame seda muudatusettepanekut arvesse võttes väljendada koodide keskmist pikkust kui

Kus P k on allika leidmise tõenäosus olekus k.

Nii et praeguses etapis teame, et tihendamine põhineb sageli esinevate elementide asendamisel lühikeste koodidega ja vastupidi, ning teame ka, kuidas määrata koodide keskmist pikkust. Aga mis on kood, kodeerimine ja kuidas see juhtub?

Mäluvaba kodeerimine

Mäluvabad koodid on kõige lihtsamad koodid, mille alusel saab teostada andmete tihendamist. Mäluvabas koodis asendatakse kodeeritavas andmevektoris iga märk koodisõnaga, mis pärineb kahendjadade või sõnade eesliidete komplektist.
Minu arvates pole see kõige selgem määratlus. Vaatame seda teemat veidi üksikasjalikumalt.

Olgu ette antud mõni tähestik , mis koosneb teatud (lõplikust) arvust tähtedest. Nimetame selle tähestiku iga lõpliku märgijada (A=a 1 , a 2 ,… ,a n) Ühesõnaga, ja arv n on selle sõna pikkus.

Olgu antud ka teine ​​tähestik . Samamoodi tähistame sõna selles tähestikus kui B.

Tutvustame veel kahte tähistust kõigi mittetühjade sõnade hulga jaoks tähestikus. Olgu - mittetühjade sõnade arv esimeses tähestikus ja - teises.

Olgu antud ka vastendus F, mis seostab iga esimese tähestiku sõna A mõne teise sõnaga B=F(A). Siis kutsutakse sõna B kood sõnad A ja kutsutakse üleminek algsõnalt selle koodile kodeerimine.

Kuna sõna võib koosneda ühest tähest, saame tuvastada esimese tähestiku tähtede ja teise tähestiku vastavate sõnade vastavuse:
a 1<->B 1
a 2<->B 2
…
a n<->Bn

Seda kirjavahetust nimetatakse skeem, ja tähistage ∑.
Sel juhul nimetatakse sõnu B 1, B 2,…, B n elementaarkoodid, ja neid kasutava kodeerimise tüüp on tähestikuline kodeerimine. Loomulikult on enamik meist seda tüüpi kodeerimisega kokku puutunud, isegi kui me ei tea kõike, mida eespool kirjeldasin.

Niisiis, oleme otsustanud kontseptsioonide üle tähestik, sõna, kood, Ja kodeerimine. Nüüd tutvustame kontseptsiooni eesliide.

Olgu sõnal B vorm B=B"B". Siis nimetatakse B-ks algust või eesliide sõnad B ja B"" on selle lõpp. See on üsna lihtne määratlus, kuid tuleb märkida, et iga sõna B puhul võib nii mõnda tühja sõna ʌ ("ruum") kui ka sõna B pidada nii alguseks kui ka lõpuks.

Niisiis, oleme jõudnud lähedale mäluta koodide definitsiooni mõistmisele. Viimane määratlus, millest peame aru saama, on eesliidete komplekt. Skeemil ∑ on eesliide omadus, kui mis tahes 1≤i, j≤r, i≠j korral ei ole sõna B i sõna B j eesliide.
Lihtsamalt öeldes on prefiksi hulk lõplik hulk, milles ükski element ei ole ühegi teise elemendi eesliide (või algus). Sellise komplekti lihtne näide on näiteks tavaline tähestik.

Niisiis, oleme käsitlenud põhimääratlusi. Niisiis, kuidas toimub mäluvaba kodeerimine?
See toimub kolmes etapis.

1. Algsõnumi sümbolitest koostatakse tähestik Ψ ja tähestiku sümbolid järjestatakse nende sõnumis ilmumise tõenäosuse kahanevas järjekorras.
2. Iga tähemärk a i tähestikust Ψ on seotud kindla sõnaga B i eesliidete hulgast Ω.
3. Iga märk kodeeritakse, millele järgneb koodide ühendamine üheks andmevooks, mis saadakse tihendamise tulemusel.

Üks seda meetodit illustreerivatest kanoonilistest algoritmidest on Huffmani algoritm.

Huffmani algoritm

Huffmani algoritm kasutab sisendandmeplokis identsete baitide esinemissagedust ja sobitab sageli esinevaid lühema pikkusega bitiahelate plokke ja vastupidi. See kood on minimaalselt üleliigne kood. Vaatleme juhtumit, kui olenemata sisendvoost koosneb väljundvoo tähestik ainult kahest märgist - nullist ja ühest.

Esiteks peame Huffmani algoritmiga kodeerimisel konstrueerima ahela ∑. Seda tehakse järgmiselt.

1. Kõik sisestustähestiku tähed on järjestatud tõenäosuse kahanevas järjekorras. Kõiki väljundvoo tähestiku sõnu (see tähendab, millega kodeerime) peetakse algselt tühjaks (tuletan teile meelde, et väljundvoo tähestik koosneb ainult tähemärkidest (0,1)).
2. Sisendvoo kaks väikseima esinemise tõenäosusega sümbolit a j-1 ja a j kombineeritakse üheks "pseudosümboliks" tõenäosusega lk võrdne selles sisalduvate sümbolite tõenäosuste summaga. Seejärel lisame sõna B j-1 algusesse 0 ja sõna B j algusesse 1, mis on edaspidi vastavalt märkide a j-1 ja a j koodid.
3. Eemaldame need märgid algse sõnumi tähestikust, kuid lisame genereeritud pseudosümboli sellele tähestikule (loomulikult tuleb see tähestikusse sisestada õigesse kohta, arvestades selle tõenäosust).

2. ja 3. samme korratakse seni, kuni tähestikus on alles vaid 1 pseudomärk, mis sisaldab kõiki tähestiku algseid märke. Veelgi enam, kuna igal sammul ja iga märgi jaoks muudetakse vastavat sõna B i (liides ühe või nulli), siis pärast selle protseduuri lõppu vastab iga tähestiku a i algusmärk teatud koodile B i .

Et paremini illustreerida, vaatame väikest näidet.
Olgu meil tähestik, mis koosneb ainult neljast tähemärgist – (a 1, a 2, a 3, a 4). Oletame ka, et nende sümbolite ilmnemise tõenäosused on võrdsed p 1 =0,5; p2 = 0,24; p3 = 0,15; p 4 =0,11 (kõikide tõenäosuste summa on ilmselgelt võrdne ühega).

Niisiis, koostame selle tähestiku diagrammi.

1. Ühendame kaks väikseima tõenäosusega sümbolit (0,11 ja 0,15) pseudosümboliks p".
2. Ühendame kaks väikseima tõenäosusega sümbolit (0,24 ja 0,26) pseudosümboliks p"".
3. Eemaldame kombineeritud märgid ja sisestame saadud pseudomärgi tähestikusse.
4. Lõpuks ühendame ülejäänud kaks sümbolit ja saame puu tipu.

Selle protsessi illustratsioon näeks välja umbes selline:

Nagu näete, omistame iga liitmise korral ühendatavatele tähemärkidele koodid 0 ja 1.
Nii saame pärast puu ülesehitamist hõlpsalt iga tähemärgi koodi hankida. Meie puhul näevad koodid välja järgmised:

A 1 = 0
a 2 = 11
a 3 = 100
a 4 = 101

Kuna ükski neist koodidest ei ole ühegi teise eesliide (see tähendab, et meil on kurikuulus eesliide), saame iga koodi väljundvoos unikaalselt tuvastada.
Seega oleme taganud, et kõige sagedamini esinev märk on kodeeritud lühima koodiga ja vastupidi.
Kui eeldada, et algselt kasutati iga märgi salvestamiseks ühte baiti, siis saame arvutada, kui palju saime andmeid vähendada.

Olgu meil sisendiks 1000 tähemärgist koosnev string, milles märk a 1 esines 500 korda, a 2 - 240, a 3 - 150 ja a 4 - 110 korda.

Algselt võttis see rida 8000 bitti. Pärast kodeerimist saame stringi pikkusega ∑p i l i = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 bitti. Seega õnnestus meil andmeid tihendada 4,54 korda, kulutades voo iga tähemärgi kodeerimiseks keskmiselt 1,76 bitti.

Tuletan meelde, et Shannoni järgi on koodide keskmine pikkus . Asendades oma tõenäosusväärtused sellesse võrrandisse, saame keskmise koodi pikkuse, mis on võrdne 1,75496602732291, mis on väga-väga lähedane meie saadud tulemusele.
Arvestada tuleb aga sellega, et lisaks andmetele endile on meil vaja salvestada kodeeringutabel, mis suurendab veidi kodeeritud andmete lõplikku suurust. Ilmselgelt saab erinevatel juhtudel kasutada erinevaid algoritmi variatsioone - näiteks mõnikord on efektiivsem kasutada etteantud tõenäosustabelit ja mõnikord on vaja see koostada dünaamiliselt, tihendatud andmeid läbides.

Järeldus

Niisiis püüdsin selles artiklis rääkida üldistest põhimõtetest, mille kohaselt toimub kadudeta tihendamine, ja uurisin ka üht kanoonilist algoritmi - Huffmani kodeerimist.
Kui artikkel on Habro kogukonna maitsele, siis kirjutan hea meelega jätku, kuna kadudeta pakkimisega on seotud veel palju huvitavat; Need on nii klassikalised algoritmid kui ka esialgsed andmete teisendused (näiteks Burrows-Wheeleri teisendus) ja loomulikult ka spetsiifilised heli, video ja piltide tihendamise algoritmid (minu arvates kõige huvitavam teema).

Kirjandus

• Vatolin D., Ratushnyak A., Smirnov M. Yukin V. Andmete tihendamise meetodid. Arhiveerimisseade, piltide ja videote tihendamine; ISBN 5-86404-170-X; 2003. aasta
• D. Salomon. Andmete, kujutiste ja heli tihendamine; ISBN 5-94836-027-Х; 2004. aasta

Üks levinumaid süsteemiprogrammide tüüpe on programmid, mis on mõeldud failide arhiveerimiseks, pakkimiseks neisse salvestatud teabe tihendamise teel.

Teabe tihendamine on failis salvestatud teabe teisendamise protsess, mille tulemusena väheneb selle liiasus ja vastavalt sellele on salvestamiseks vaja vähem mälu.

Teabe tihendamine failides saavutatakse liiasuse kõrvaldamise teel mitmel viisil, näiteks koodide lihtsustamise, konstantsete bittide kõrvaldamise või korduvate märkide või korduvate märgijadade esitamise teel kordusteguri ja vastavate märkide järgi. Sellise teabe tihendamiseks kasutatakse erinevaid algoritme.

Kokkupakkida saab nii ühte kui ka mitut faili, mis kokkusurutud kujul asetatakse nn arhiivifail või arhiivi.

Arhiivifail on spetsiaalselt organiseeritud fail, mis sisaldab ühte või mitut tihendatud või tihendamata faili ja teenuseteavet failinimede, nende loomise või muutmise kuupäeva ja kellaaja, suuruste jms kohta.

Failipakendamise eesmärk on tavaliselt tagada info kompaktsem paigutamine kettale, vähendades arvutivõrkude sidekanalite kaudu info edastamise aega ja vastavalt ka kulusid. Lisaks lihtsustab failide rühma pakkimine ühte arhiivifaili oluliselt nende ülekandmist ühest arvutist teise, vähendab failide kettale kopeerimise aega, võimaldab kaitsta teavet volitamata juurdepääsu eest ja aitab kaitsta arvutiviirustega nakatumise eest.

Under surveaste mõista tihendatud faili ja originaali suuruste suhet, väljendatuna protsentides.

Kompressiooniaste oleneb kasutatavast tihendusprogrammist, tihendusmeetodist ja lähtefaili tüübist. Parimad kokkusurutud failid on graafilised pildid, tekstifailid, andmefailid, mille tihendussuhe võib ulatuda 5 - 40%, käivitatavate programmide faile ja laadimismooduleid tihendatakse vähem - 60 - 90%. Arhiivifaile peaaegu ei tihendata. Arhiveerimisprogrammid erinevad kasutatavate tihendusmeetodite poolest, mis omakorda mõjutab tihendussuhet.

Arhiveerimine (pakendamine) – lähtefailide paigutamine (allalaadimine) arhiivifaili tihendatud või pakkimata kujul.

Lahtipakkimine (lahtipakkimine) on failide taastamine arhiivist täpselt sellisena, nagu need olid enne arhiivi laadimist. Lahtipakkimisel ekstraheeritakse failid arhiivist ja paigutatakse kettale või RAM-i.

Faile pakkivaid ja lahti pakkivaid programme nimetatakse arhiveerimisprogrammideks.

Suured arhiivifailid saab paigutada mitmele kettale (köidetele). Selliseid arhiive nimetatakse mitmeköiteline. Köide on mitmeköitelise arhiivi lahutamatu osa. Luues arhiivi mitmest osast, saate selle osad salvestada mitmele kandjale.

Arhiiviprogrammide peamised tüübid

Praegu on kasutusel mitukümmend arhiveerimisprogrammi, mis erinevad funktsioonide loetelu ja tööparameetrite poolest, kuid parimatel neist on ligikaudu samad omadused. Kõige populaarsemate programmide hulka kuuluvad: Zip (ja selle modifikatsioon WinZip), WinRAR, Arj (ja selle sordid), G-Zip, 7-Zip.

Arhiiviprogrammid võimaldavad teil luua ka arhiive, millest failide väljavõtmiseks pole vaja ühtegi programmi, kuna arhiivifailid ise võivad sisaldada lahtipakkimisprogrammi. Selliseid arhiivifaile nimetatakse isepakkivateks. Isepahanduv arhiivifail on käivitatav käivitatav moodul, mis suudab iseseisvalt lahti pakkida selles olevad failid ilma arhiiviprogrammi kasutamata.

Iseavanev arhiiv sai nime SFX arhiiv(Iseavandamine). Seda tüüpi arhiivid luuakse tavaliselt EXE-failivormingus.

Paljud arhiveerimisprogrammid pakivad failid lahti, laadides need kettale, kuid on ka selliseid, mis on mõeldud pakitud käivitatava mooduli (programmi) loomiseks. Sellise pakkimise tulemusel luuakse sama nime ja laiendiga programmifail, mis RAM-i laadides ise lahti pakkib ja koheselt tööle hakkab. Samas on võimalik ka programmifail tagasi pakkimata vormingusse teisendada. Selliste arhiivide hulka kuuluvad programmid Upx, PKLITE, LZEXE.

Programmi EXPAND, mis on osa Windowsi operatsioonisüsteemi utiliitidest, kasutatakse Microsofti tarnitavate tarkvaratoodete failide lahtipakkimiseks.

Arhiveerimisprogrammi haldamise viisid

Arhiveerimisprogrammi juhitakse ühel järgmistest viisidest:

• - käsurea kasutamine, milles genereeritakse käivitamiskäsk, mis sisaldab arhiveerimisprogrammi nime, juhtkäsku ja selle konfiguratsiooniklahve, samuti arhiivi- ja lähtefailide nimesid;
• - sisseehitatud kesta ja dialoogipaneelide kasutamine, mis ilmuvad pärast programmi käivitamist ja võimaldavad juhtida menüüde ja funktsiooniklahvide abil, mis loob kasutajale mugavamad töötingimused;
• - Exploreri kontekstimenüü kasutamine Windowsi operatsioonisüsteemis.

Miks on vaja teavet tihendada ja kuidas seda teha?

Aga tõesti, miks? Arvutame näiteks välja, kui palju mälu võtab enda alla televisiooni kvaliteedilt lähedane pilt. Olgu selle eraldusvõime 800x6009 pikslit ja värvivarjundite arv on umbes 16 tuhat (High Color), st iga piksli värvi tähistab kahebaidine kood. 800x600=480000 elementi. 480000x2 baiti = 960000 baiti – see on veidi alla 1 megabaidi. Tundub, et mitte nii palju – laserkettale mahub üle 650 sellise pildi. Mis siis, kui me räägime filmist? Standardne filmiprojektsiooni kiirus on 24 kaadrit sekundis. See tähendab, et CD-le saab salvestada fragmenti pikkusega 650:24=27 sekundit. Kus see hea on?! Kuid see pole kaugeltki ainus juhtum, kui teavet on "liiga palju". Seega on andmete tihendamise üheks põhjuseks soov mahutada samasse mälumahtu rohkem infot. On ka teine ​​põhjus. Teabe tihendamine kiirendab selle edastamist. Aga sellest lähemalt järgmises peatükis.

Andmete tihendamiseks (compression10) on mitu meetodit. Kõik need võib jagada kahte rühma – kadudeta ja kadudeta pakkimine. Esimesel juhul kordab lahtipakkitud sõnum täpselt algset. Loomulikult saab sel viisil töödelda igasugust teavet. Kadudega tihendamine on võimalik ainult juhtudel, kui teatud moonutused on vastuvõetavad – mis täpselt sõltub konkreetsest andmetüübist.

Peaaegu kõik kadudeta pakkimismeetodid põhinevad ühel kahest üsna lihtsast ideest.

Üks neist ilmus esmakordselt Huffmani poolt 1952. aastal välja pakutud teksti tihendamise meetodil. Teate, et vaikimisi on iga tekstimärk kodeeritud ühe baidina. Kuid tõsiasi on see, et mõned tähed on tavalisemad, teised aga vähem levinud. Näiteks vene keeles kirjutatud tekstis on igas tuhandes tähemärgis keskmiselt 90 tähte "o", 72 tähte "e" ja ainult 2 tähte "f". Tekib kõige rohkem lünki: sada seitsekümmend neli. Kui kasutate kõige tavalisemate märkide jaoks lühemaid koode (alla 8 bitti) ja pikki koode (üle 8 biti) vähem levinud märkide jaoks, võtab tekst tervikuna vähem mälu kui tavalise kodeeringu korral.

Mitmed tihendusmeetodid põhinevad baitide või baitide jadade kordamisel. Neist lihtsaimat, RLE11, kasutatakse laialdaselt piltide tihendamisel. Selle meetodi abil tihendatud fail salvestab, mitu korda samu baite korratakse. Näiteks "RRRRRGGGBBBBBBRRRBRRRRRRRR" asemel salvestatakse "5R3G6B3R2B7R"12. Ilmselgelt töötab see meetod kõige paremini, kui pilt sisaldab suuri ühevärvilisi alasid.

Teised meetodid põhinevad sellel, et kui teatud baitide jada esineb failis mitu korda, saab selle kirjutada ühe korra spetsiaalsesse tabelisse ja siis lihtsalt näidata: “võta tabeli sellisest ja sellisest kohast nii palju baite. "13.

Kadudeta pakkimismeetodid ei vähenda faili suurust kuigi palju. Tavaliselt ei ületa tihendusaste 1/3-1/4. Palju paremaid tulemusi saab saavutada kadudeta pakkimisega. Sel juhul tehakse spetsiaalsete uuringute põhjal kindlaks, millist teavet saab ohverdada.

Näiteks on leitud, et inimese nägemine on väga tundlik heleduse ja palju vähem värvitooni muutuste suhtes. Seetõttu on fotopiltide (ja üldiselt piltide, millel pole teravaid värvide vahelisi piire) tihendamisel võimalik välistada info mõne piksli värvi kohta. Lahti pakkides määrake see naabrite järgi. Praktikas kasutab kõige sagedamini kasutatav meetod keerukamat töötlemist - JPEG14. See võimaldab pilti kümneid kordi tihendada. Võttes arvesse inimese infotaju iseärasusi, töötatakse välja ka videopiltide (nüüd on levinumad MPEG15 meetodid) ja heli kadudega pakkimismeetodid.

Loomulikult saavad kadudeta pakkimist kasutada ainult teatud tüüpi andmete töötlemiseks loodud programmid (näiteks graafilised redaktorid). Kuid mis tahes suvaliste failide puhul kasutatakse ka kadudeta pakkimismeetodeid (kompressorprogrammid ARJ, ZIP, RAR, StuffIt jne on laialt tuntud).

Pange tähele, et te ei tohiks proovida tihendada faile, mis on juba tihendatud: nende suurus kas väheneb veidi või isegi suureneb.

Märkmed

Tegelikult on telepildis 625 rida.

Compressus (lat.) - kokkusurumine.

Run-Length Encoding (inglise keel) – jada pikkuse kodeerimine.

Tegelikkuses kasutatakse muidugi värvikoode ja koode, mis näitavad, mitu korda järgmist baiti korratakse või mitu järgmistest baitidest on mittekorduvad.

Sellel ideel põhineb LZW-meetod, mida kasutatakse laialdaselt erinevate andmete tihendamiseks, mis on saanud nime selle arendajate perekonnanimede esitähtede järgi: Lempel, Ziv ja Welch.

Joint Photographic Experts Group (inglise) – fotograafiaekspertide ühine rühm, mis töötas välja samanimelise kujutise tihendamise meetodi.

Liikuva pildi ekspertide rühm