Arhiveerijad. Andmete tihendamise meetodite ülevaade
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.
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 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.
- Algsõnumi sümbolitest koostatakse tähestik Ψ ja tähestiku sümbolid järjestatakse nende sõnumis ilmumise tõenäosuse kahanevas järjekorras.
- Iga tähemärk a i tähestikust Ψ on seotud kindla sõnaga B i eesliidete hulgast Ω.
- 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.
- 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)).
- 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.
- 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).
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.
- Ühendame kaks väikseima tõenäosusega sümbolit (0,11 ja 0,15) pseudosümboliks p".
- Ühendame kaks väikseima tõenäosusega sümbolit (0,24 ja 0,26) pseudosümboliks p"".
- Eemaldame kombineeritud märgid ja sisestame saadud pseudomärgi tähestikusse.
- 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
ARHIVEERID
Teabe tihendamine on failis salvestatud teabe muutmise protsess, vähendades andmete liiasust. Selle protsessi eesmärk on vähendada andmetega hõivatud mahtu.
Arhiivifail on spetsiaalselt loodud fail, mis sisaldab ühte või mitut faili tihendatud kujul.
Kompressiooniaste: K c = V c / V o * 100%
Kc- tihendusaste, V c- tihendatud faili maht, V o- faili esialgne suurus.
Kompressiooniaste sõltub:
1) kasutatav programm - arhiveerija,
2) tihendusmeetod,
3) lähtefaili tüüp: tekst, graafika, video, heli jne.
Faile pakkivaid ja lahti pakkivaid programme nimetatakse arhiveerijateks. Kõige tavalisemad on: ARJ, ZIP, RAR. Arhiivifailide laiend ühtib nende loomiseks kasutatud arhiivi nimega.
Arhiveerijad võimaldavad luua isepakkevaid arhiivifaile, st. Nende lahtipakkimiseks ei pea te arhiiviprogrammi käivitama, sest need ise sisaldavad lahtipakkimisprogrammi. Neid arhiive nimetatakse SFX-arhiivideks
(Iseavandamine). Selliste failide laiend on *.EXE.
Info tihendamise põhimõtted
Igas tekstis on korduvaid märke. Võimalik on määrata üks märk ja korduste arv. Graafilistele failidele rakendades on selle algoritmi efektiivsus veelgi suurem. Kui vaatate monitori, näete palju korduvaid sama värvi täppe. PCX-i graafiline failivorming põhineb sellel teabe tihendamise põhimõttel. Kaasaegsed arhiivid tõstavad esile mitte ainult korduvaid tegelasi, vaid ka märgiahelaid ja üksikuid sõnu.
Kui tekstis ei kasutata kõiki PC tähestiku märke, siis saab nende kodeerimiseks kasutada ühte baiti, 8 bitti või väiksemat numbrit. Seda põhimõtet kasutatakse telegraafiaparaadis, kus kasutatakse ainult vene suuri tähti, nende esitamiseks piisab 5 bitist, mis võimaldab kahes baidis kirjutada kolm märki.
3. Järgnev põhimõte kasutab mustrit, et tähed esinevad tekstis erineva sagedusega. Näiteks selles tekstis on tühik kõige levinum märk, sümbolid “a” ja “ja” on väga levinud. Neid sageli esinevaid märke saab esitada lühikese bitijadana, samas kui teisi märke saab kodeerida pikema jadana. Näiteks:
4. Füüsiliselt eraldab arvuti ruumi failide paigutamiseks kettale klastritesse – 4 kB suuruste plokkidena. Vähem esile tuua on võimatu. Näiteks kui faili suurus on 8193 baiti (8 kB ja 1 bait), võtab see füüsiliselt enda alla 16 kB või 16384 baiti. Failide rühma ühendamine võimaldab teil nende jääkide pealt kokku hoida. See võimaldab väikeste failide pakkimisel suurt kokkuhoidu.
Kokku ei kasutata failide eraldi paigutamisel 6 kB, mis on 100% failide sisust. Teisel juhul jääb kasutamata 2 kB, 33%.
Arhiveerija zip
Failide pakkimine pkzip [võtmed]<имя архива>[failide teed]
Klahvid: -rp arhiveerimine alamkataloogidega, säilitades samal ajal struktuuri
S P.W.D. arhiivi paroolikaitse (PWD)
A lisage arhiivi failid
M teisalda failid arhiivi
V arhiivi sisu vaatamine
Kui kõik kataloogis olevad failid arhiveeritakse, tuleb mask määrata *.*
pkunzip-failide lahtipakkimine [lülitid]<имя архива>[failinimed]
Klahvid: -d lahtipakkimine alamkataloogidega, säilitades samas struktuuri
SPWD arhiivi parool (PWD)
Arhiveerija arj
arj<команда>[klahvid]<имя архива>[failinimed]
Arj arhiveerija jaoks teeb üks fail nii lahti- kui pakkimistoiminguid.
Meeskonnad: a arhiveerimine
e lahtipakkimine ilma kataloogistruktuuri säilitamata
x lahtipakkimine, säilitades samal ajal struktuuri
l arhiivi sisu vaatamine
m teisaldage failid arhiivi
d kustutage failid arhiivist
Klahvid: -r pakkimine alamkataloogidega, säilitades samas struktuuri
V arhiivi jaotus köideteks mahuga (kui see on määratud)
standardsete diskettide (360, 720, 1200, 1440) suurus on näidatud kilobaitides, mittestandardsete diskettide suurus on näidatud baitides
V on märgitud mitmeköitelise arhiivi lahtipakkimisel
G P.W.D. arhiivi parool ( P.W.D.)
Failide pakkimine
Failide lahtipakkimine
©2015-2019 sait
Kõik õigused kuuluvad nende autoritele. See sait ei pretendeeri autorlusele, kuid pakub tasuta kasutamist.
Lehe loomise kuupäev: 2016-08-08
Loeng nr 4. Teabe tihendamine
Info tihendamise põhimõtted
Andmete tihendamise eesmärk on pakkuda allika genereeritud andmete kompaktset esitust, et neid saaks säästlikumalt salvestada ja sidekanalite kaudu edastada.
Olgu meil 1 (üks) megabaidi suurune fail. Peame sellest hankima väiksema faili. Pole midagi keerulist - käivitame arhiivi, näiteks WinZipi, ja selle tulemusel saame näiteks 600 kilobaidi suuruse faili. Kuhu kadus ülejäänud 424 kilobaiti?
Teabe tihendamine on üks viise selle kodeerimiseks. Üldiselt jagunevad koodid kolme suurde rühma – tihenduskoodid (efektiivsed koodid), mürakindlad koodid ja krüptokoodid. Info tihendamiseks mõeldud koodid jagunevad omakorda kadudeta koodideks ja kadudeta koodideks. Kadudeta kodeerimine tähendab absoluutselt täpset andmete taastamist pärast dekodeerimist ja seda saab kasutada mis tahes teabe tihendamiseks. Kadudeta kodeerimisel on tavaliselt palju suurem tihendusaste kui kadudeta kodeerimisel, kuid see võimaldab dekodeeritud andmetel mõningaid kõrvalekaldeid originaalist.
Kompressiooni tüübid
Kõik teabe tihendamise meetodid võib jagada kahte suurde mittekattuvasse klassi: tihendamine koos kaotus teave ja tihendamine ilma kaotuseta teavet.
Pakkimine ilma teabe kadumiseta.
Meid huvitavad need tihendusmeetodid eelkõige seetõttu, et neid kasutatakse tekstidokumentide ja -programmide edastamisel, tehtud töö kliendile üleandmisel või arvutisse salvestatud infost varukoopiate tegemisel.
Selle klassi tihendusmeetodid ei saa lubada teabe kadumist, seega põhinevad nad ainult selle liiasuse kõrvaldamisel ja teabel on peaaegu alati liiasus (kuigi, kui keegi pole seda juba varem tihendanud). Kui poleks koondamist, poleks ka midagi kokku suruda.
Siin on lihtne näide. Vene keeles on 33 tähte, kümme numbrit ning kümmekond kirjavahemärki ja muid erimärke. Teksti jaoks, mis on kirjutatud ainult suurte vene tähtedega(nagu telegrammides ja radiogrammides) piisaks kuuekümnest erinevast tähendusest. Iga märk on aga tavaliselt kodeeritud baidiga, mis sisaldab 8 bitti ja suudab väljendada 256 erinevat koodi. See on esimene koondamise põhjus. Meie "telegraafi" teksti jaoks piisaks kuuest bitist tähemärgi kohta.
Siin on veel üks näide. Rahvusvahelises märgikodeeringus ASCII Sama arv bitte (8) on eraldatud mis tahes märgi kodeerimiseks, samas kui kõik on juba ammu ja hästi teadnud, et kõige sagedamini esinevad märgid on mõttekas kodeerida vähemate tähemärkidega. Nii näiteks on morsekoodis sageli esinevad tähed “E” ja “T” kodeeritud ühe märgiga (vastavalt punkt ja kriips). Ja sellised haruldased tähed nagu “Yu” (- -) ja “C” (- -) on kodeeritud nelja tähemärgiga. Ebaefektiivne kodeerimine on koondamise teine põhjus. Teabe tihendamist teostavad programmid saavad sisestada oma kodeeringu (erinevate failide puhul erinev) ja lisada tihendatud failile kindla tabeli (sõnastiku), millest lahtipakkimisprogramm saab teada, kuidas selles failis on teatud märgid või nende rühmad kodeeritud. Algoritme, mis põhinevad teabe ümberkodeerimisel, nimetatakse Huffmani algoritmid.
Korduvate fragmentide olemasolu on koondamise kolmas alus. See on tekstides haruldane, kuid tabelites ja graafikas on koodide kordamine tavaline. Nii et kui näiteks arvu 0 korratakse kakskümmend korda järjest, siis pole mõtet panna kahtekümmend null baiti. Selle asemel panevad nad ühe nulli ja koefitsiendiks 20. Selliseid korduste tuvastamisel põhinevaid algoritme nimetatakse nn. meetodidRLE (Jookse Pikkus Kodeerimine).
Graafilisi illustratsioone eristavad eriti suured korduvad identsete baitide jadad, kuid mitte fotograafilised (seal on palju müra ja naaberpunktid erinevad parameetrite poolest oluliselt), vaid need, mida kunstnikud joonistavad “sileda” värviga, nagu animafilmides.
Kompressioon koos teabe kadumisega.
Kadunud pakkimine tähendab, et pärast kokkusurutud arhiivi lahtipakkimist saame dokumendi, mis erineb veidi sellest, mis meil alguses oli. On selge, et mida suurem on tihendusaste, seda suurem on kadu ja vastupidi.
Loomulikult ei ole sellised algoritmid rakendatavad tekstidokumentide, andmebaasitabelite ja eriti programmide jaoks. Väikesed moonutused lihtsas vormindamata tekstis saab kuidagi üle elada, kuid kasvõi ühe biti moonutamine programmis muudab selle täiesti töövõimetuks.
Samas on materjale, milles kümnekordse tihenduse saamiseks tasub ohverdada paar protsenti infost. Nende hulka kuuluvad fotograafilised illustratsioonid, videod ja muusikalised kompositsioonid. Teabe kadu tihendamise ja sellele järgneva dekompressiooni ajal sellistes materjalides tajutakse täiendava "müra" ilmnemisena. Kuid kuna teatud "müra" on nende materjalide loomisel endiselt olemas, ei tundu selle kerge suurenemine alati kriitiline ja failide suuruse kasv on tohutu (muusika puhul 10-15 korda, foto- ja videomaterjalide puhul 20-30 korda) .
Kadunud pakkimisalgoritmid hõlmavad selliseid tuntud algoritme nagu JPEG ja MPEG. Fotopiltide tihendamiseks kasutatakse JPEG-algoritmi. Selle meetodiga tihendatud graafikafailidel on JPG-laiend. MPEG-algoritme kasutatakse video ja muusika tihendamiseks. Need failid võivad olenevalt konkreetsest programmist olla erineva laiendiga, kuid tuntuimad on .MPG video ja .MPG muusika jaoks.
Kadudega tihendamisalgoritme kasutatakse ainult tarbijate ülesannete jaoks. See tähendab näiteks, et kui foto edastatakse vaatamiseks ja muusika taasesitamiseks, siis saab kasutada sarnaseid algoritme. Kui need edastatakse edasiseks töötlemiseks, näiteks toimetamiseks, ei ole lähtematerjalis teabe kadu vastuvõetav.
Vastuvõetava tihenduskadu suurust saab tavaliselt kontrollida. See võimaldab katsetada ja saavutada optimaalse suuruse/kvaliteedi suhte. Ekraanil reprodutseerimiseks mõeldud fotoillustratsioonide puhul ei ole 5% teabe kadu tavaliselt kriitiline ning mõnel juhul on talutav ka 20-25%.
Tihendusalgoritmid ilma teabe kadumiseta
Shannon-Fano kood
Edasiseks aruteluks on mugav ette kujutada meie lähtetekstifaili märkide allikana, mis ilmuvad selle väljundis ükshaaval. Me ei tea ette, milline märk on järgmine, kuid teame, et tõenäosusega p1 ilmub täht "a", tõenäosusega p2 - täht "b" jne.
Lihtsamal juhul käsitleme kõiki tekstimärke üksteisest sõltumatuna, s.t. järgmise sümboli ilmumise tõenäosus ei sõltu eelmise sümboli väärtusest. Sisuka teksti puhul see muidugi paika ei pea, aga praegu kaalume väga lihtsustatud olukorda. Sel juhul peab paika väide "sümbol kannab rohkem teavet, seda väiksem on selle ilmumise tõenäosus".
Kujutagem ette teksti, mille tähestik koosneb ainult 16 tähest: A, B, C, D, D, E, F, Z, I, K, L, M, N, O, P, R. Kõik need tähed võivad olla kodeerige vaid 4 bitiga: 0000 kuni 1111. Kujutage nüüd ette, et nende märkide ilmumise tõenäosused jagunevad järgmiselt:
Nende tõenäosuste summa on loomulikult ühtsus. Jagame need sümbolid kahte rühma nii, et iga grupi sümbolite kogutõenäosus on ~0,5 (joonis). Meie näites on need sümbolirühmad A-B ja G-R. Joonisel olevaid märgirühmi tähistavaid ringe nimetatakse tippudeks ehk sõlmedeks ja nende sõlmede struktuuri ennast kahendpuuks (B-puu). Määrame igale sõlmele oma koodi, määrates ühe sõlme numbriga 0 ja teise numbriga 1.
Jagame taas esimese rühma (A-B) kaheks alarühmaks, et nende kogutõenäosused oleksid üksteisele võimalikult lähedal. Lisame esimese alarühma koodile numbri 0 ja teise alarühma koodile numbri 1. 
Kordame seda toimingut seni, kuni meie “puu” igas tipus on järel ainult üks sümbol. Meie tähestiku täielikul puul on 31 sõlme.
Märgikoodide (puu kõige parempoolsemate sõlmede) koodid on ebavõrdse pikkusega. Seega on täht A, mille tõenäosus on p=0,2 meie kujuteldava teksti puhul, kodeeritud vaid kahe bitiga ja täht P (joonisel pole kujutatud), mille tõenäosus on p=0,013, kodeeritakse koodiga. koguni kuuebitine kombinatsioon.
Seega on põhimõte ilmne – sageli esinevad märgid on kodeeritud väiksema arvu bittidega ja harva esinevad suurema arvuga. Selle tulemusena on keskmine bittide arv sümboli kohta võrdne
kus ni on i-ndat märki kodeerivate bittide arv, pi on i-nda märgi ilmumise tõenäosus.
Huffmani kood.
Huffmani algoritm rakendab elegantselt statistilise kodeerimise üldist ideed prefiksikomplektide abil ja toimib järgmiselt:
1. Kirjutame üles kõik tähestiku märgid nende tekstis ilmumise tõenäosuse suurenemise või vähendamise järjekorras.
2. Kombineerime järjestikku kaks väikseima esinemise tõenäosusega sümbolit uueks liitsümboliks, mille tõenäosuse oletame võrdseks selle moodustavate sümbolite tõenäosuste summaga. Lõpuks ehitame puu, mille igal sõlmel on kõigi selle all olevate sõlmede kogutõenäosus.
3. Jälgime tee iga puu lehe juurde, märkides suuna igale sõlmele (näiteks paremale - 1, vasakule - 0). Saadud jada annab igale sümbolile vastava koodisõna (joonis).
Ehitame koodipuu järgmise tähestikuga sõnumi jaoks:
Meetodite puudused
Nagu eelmine arutelu viitab, on koodide suurim väljakutse vajadus iga tihendatava andmetüübi jaoks tõenäosustabelite järele. See pole probleem, kui teate, et tihendate inglis- või venekeelset teksti; me lihtsalt varustame kodeerija ja dekoodriga inglis- või venekeelse teksti jaoks sobiva koodipuu. Üldiselt, kui sisendandmete sümbolite tõenäosus on teadmata, töötavad staatilised Huffmani koodid ebaefektiivselt.
Selle probleemi lahenduseks on kodeeritud andmete statistiline analüüs, mis tehakse andmete esimesel läbimisel, ja selle põhjal koodipuu koostamine. Tegelik kodeerimine toimub teisel käigul.
Veel üks koodide puudus on see, et nende koodisõna minimaalne pikkus ei tohi olla väiksem kui üks, samas kui sõnumi entroopia võib olla 0,1 või 0,01 bitti tähe kohta. Sel juhul muutub kood oluliselt üleliigseks. Probleemi lahendab algoritmi rakendamine märgiplokkidele, kuid siis muutub kodeerimise/dekodeerimise protseduur keerulisemaks ja koodipuu, mis tuleb lõpuks koos koodiga salvestada, oluliselt laieneb.
Need koodid ei võta arvesse tähemärkidevahelisi seoseid, mis esinevad peaaegu igas tekstis. Näiteks kui kohtame ingliskeelses tekstis q-tähte, siis võime julgelt väita, et selle järele tuleb u-täht.
Run Length Encoding (RLE) on üks vanimaid ja lihtsamaid arhiveerimisalgoritme. RLE tihendamine toimub identsete baitide ahelate asendamisel loenduri, väärtuse paaridega. ("punane, punane, ..., punane" on kirjutatud kui "N punast").
Üks algoritmi rakendusi on järgmine: nad otsivad kõige harvemini esinevat baiti, nimetavad seda prefiksiks ja asendavad identsete märkide ahelad kolmikutega "eesliide, loendur, väärtus". Kui see bait ilmub lähtefailis üks või kaks korda järjest, siis asendatakse see paariga "prefiks, 1" või "prefiks, 2". Jääb üks kasutamata "eesliide, 0" paar, millega saab näidata pakitud andmete lõppu.
Exe-failide kodeerimisel saate otsida ja pakkida selliseid järjestusi nagu AxAyAzAwAt..., mida sageli leidub ressurssides (Unicode-stringid)
Algoritmi positiivsed küljed hõlmavad asjaolu, et see ei nõua töö ajal lisamälu ja käivitatakse kiiresti. Algoritmi kasutatakse PCX, TIFF, BMP vormingutes. PCX pakkkodeeringu huvitav omadus on see, et mõne pildi arhiveerimise astet saab oluliselt parandada lihtsalt pildipaletis värvide järjekorda muutes.
LZW-kood (Lempel-Ziv & Welch) on tänapäeval üks levinumaid kadudeta tihenduskoode. Just LZW-koodi abil toimub tihendamine sellistes graafilistes vormingutes nagu TIFF ja GIF; LZW modifikatsioonide abil täidavad paljud universaalsed arhiivid oma ülesandeid. Algoritmi töö põhineb sisendfailist korduvate märgijadade otsimisel, mis on kodeeritud 8–12-bitistes kombinatsioonides. Seega on see algoritm kõige tõhusam teksti- ja graafikafailide puhul, mis sisaldavad suuri ühevärvilisi alasid või korduvaid pikslite jadasid.
Teabekao puudumine LZW-kodeerimisel on viinud sellel põhineva TIFF-vormingu laialdasele kasutamisele. See formaat ei sea mingeid piiranguid pildi suurusele ja värvisügavusele ning seda kasutatakse laialdaselt näiteks trükkimisel. Teine LZW-põhine formaat, GIF, on primitiivsem – see võimaldab salvestada pilte, mille värvisügavus ei ületa 8 bitti/piksel. GIF-faili alguses on palett - tabel, mis määrab vastavuse värviindeksi - numbri vahemikus 0 kuni 255 ja tegeliku 24-bitise värviväärtuse vahel.
Kadunud tihendusalgoritmid
JPEG-algoritmi töötas välja ettevõtete rühm, mida nimetatakse Joint Photographic Experts Groupiks. Projekti eesmärk oli luua ülitõhus tihendusstandard nii must-valgete kui ka värviliste piltide jaoks ning see eesmärk saavutati arendajate poolt. Praegu kasutatakse JPEG-d laialdaselt seal, kus on vaja suurt tihendusastet – näiteks Internetis.
Erinevalt LZW-algoritmist on JPEG-kodeering kadudega kodeering. Kodeerimisalgoritm ise põhineb väga keerulisel matemaatikal, kuid üldjoontes saab seda kirjeldada järgmiselt: pilt jagatakse 8 * 8 piksliteks ruutudeks ning seejärel teisendatakse iga ruut 64 piksli pikkuseks järjestikuseks ahelaks. Järgmisena allutatakse igale sellisele ahelale nn DCT teisendus, mis on üks diskreetse Fourier' teisenduse variante. See seisneb selles, et pikslite sisendjada saab esitada mitme sagedusega siinus- ja koosinuskomponentide (nn harmooniliste) summana. Sel juhul peame teadma ainult nende komponentide amplituude, et rekonstrueerida sisendjada piisava täpsusega. Mida rohkem harmoonilisi komponente me teame, seda väiksem on lahknevus originaali ja tihendatud kujutise vahel. Enamik JPEG-koodereid võimaldab teil tihendustaset reguleerida. See saavutatakse väga lihtsal viisil: mida suurem on tihendusaste, seda vähem harmoonilisi esindab iga 64-piksline plokk.
Loomulikult on seda tüüpi kodeeringu tugevuseks kõrge tihendusaste, säilitades samal ajal algse värvisügavuse. Just see omadus on toonud kaasa selle laialdase kasutamise Internetis, kus faili suuruse vähendamine on ülimalt oluline, multimeediumientsüklopeediates, kus on vaja salvestada võimalikult palju graafikat piiratud mahus.
Selle vormingu negatiivne omadus on pildikvaliteedi olemuslik halvenemine, mida ei saa mingil juhul kõrvaldada. Just see kurb tõsiasi ei luba seda kasutada trükkimisel, kus kvaliteet on ülimalt tähtis.
Kuid JPEG-vorming ei ole lõpliku faili suuruse vähendamise püüdlustes täiuslikkuse piir. Viimasel ajal on intensiivselt uuritud nn laineteisendust (ehk laineteisendust). Keerulistele matemaatilistele põhimõtetele tuginedes pakuvad lainekooderid suuremat tihendamist kui JPEG ja väiksema teabekaoga. Vaatamata lainekete teisenduse matemaatika keerukusele on see tarkvararakenduses lihtsam kui JPEG. Kuigi lainetihenduse algoritmid on alles oma varajases arengujärgus, on neil ees suur tulevik.
Fraktaalne kokkusurumine
Fraktaalkujutise tihendamine on kadudega kujutiste tihendamise algoritm, mis põhineb itereeritavate funktsioonisüsteemide (IFS, mis on tavaliselt afiinsed teisendused) rakendamisel piltidele. See algoritm on tuntud selle poolest, et mõnel juhul võimaldab see saavutada väga kõrge tihendusastme (parimad näited on kuni 1000-kordne vastuvõetava visuaalse kvaliteediga) loodusobjektide reaalsete fotode jaoks, mis on teistele pilditihendusalgoritmidele kättesaamatud. põhimõte. Patenteerimise keerulise olukorra tõttu ei kasutatud algoritmi laialdaselt.
Fraktalarhiveerimine põhineb asjaolul, et itereeritud funktsioonide süsteemi koefitsiente kasutades esitatakse pilt kompaktsemal kujul. Enne arhiveerimisprotsessi vaatamist vaatame, kuidas IFS pilti koostab.
Rangelt võttes on IFS 3D-afiinsete teisenduste komplekt, mis muudab ühe pildi teiseks. Kolmemõõtmelise ruumi punktid (x koordinaat, y koordinaat, heledus) läbivad teisenduse.
Fraktaalkodeerimise meetodi aluseks on isesarnaste alade tuvastamine pildil. Võimalust rakendada itereeritud funktsioonisüsteemide (IFS) teooriat kujutise tihendamise probleemile uurisid esmakordselt Michael Barnsley ja Alan Sloan. Nad patenteerisid oma idee 1990. ja 1991. aastal. Jacquin esitles fraktaalkodeerimismeetodit, mis kasutab domeeni ja vahemiku alampildiplokkide süsteeme, ruudukujulisi plokke, mis katavad kogu pildi. See lähenemisviis sai aluseks enamikule tänapäeval kasutatavatele fraktaalkodeerimismeetoditele. Seda täiustasid Yuval Fisher ja mitmed teised teadlased.
Selle meetodi kohaselt jagatakse pilt mittekattuvate järgu alampiltide komplektiks (vahemiku alamkujutisteks) ja määratakse kattuvate domeeni alampiltide komplekt. Iga auastmeploki jaoks leiab kodeerimisalgoritm sobivaima domeeniploki ja afiinse teisenduse, mis teisendab selle domeeniploki etteantud auastmeplokiks. Pildi struktuur on kaardistatud auastmeplokkide, domeeniplokkide ja teisenduste süsteemiks.
Idee on järgmine: oletame, et algne pilt on mingi tihenduskaardistuse fikseeritud punkt. Siis saab pildi enda asemel kuidagi selle kaardistuse meelde jätta ja selle taastamiseks piisab, kui seda vastendust korduvalt rakendada mis tahes lähtepildile.
Banachi teoreemi järgi viivad sellised iteratsioonid alati kindlasse punkti ehk algkujutisse. Praktikas seisneb kogu raskus pildilt sobivaima tihenduskaardistuse leidmises ja selle kompaktses salvestamises. Tavaliselt on kaardistamise otsingualgoritmid (st tihendusalgoritmid) väga toore jõuga ja arvutuslikult kulukad. Samal ajal on taastamisalgoritmid üsna tõhusad ja kiired.
Lühidalt võib Barnsley pakutud meetodit kirjeldada järgmiselt. Pilt on kodeeritud mitme lihtsa teisendusega (meie puhul afiinne), see tähendab, et selle määravad nende teisenduste koefitsiendid (meie puhul A, B, C, D, E, F).
Näiteks Kochi kõvera kujutist saab kodeerida nelja afiinse teisendusega, me defineerime selle üheselt ainult 24 koefitsiendiga.
Selle tulemusena läheb punkt kindlasti originaalpildi musta ala sisse. Olles seda toimingut mitu korda teinud, täidame kogu musta ruumi, taastades sellega pildi.
Kaks kõige kuulsamat IFS-iga saadud pilti on Sierpinski kolmnurk ja Barnsley sõnajalg. Esimene on antud kolme ja teine viie afiinse teisendusega (ehk meie terminoloogias läätsed). Iga teisendus määratakse sõna otseses mõttes mõne baidi kaupa, samas kui nende abiga konstrueeritud pilt võib hõivata mitu megabaiti.
Selgub, kuidas arhiveerija töötab ja miks see nii palju aega võtab. Tegelikult on fraktaalkompressioon pildilt sarnaste alade otsimine ja nende jaoks afiinsete teisendusparameetrite määramine.
Halvimal juhul, kui optimeerimisalgoritmi ei kasutata, on vaja loetleda ja võrrelda kõik võimalikud erineva suurusega pildifragmendid. Isegi väikeste piltide puhul saame diskreetsust arvesse võttes astronoomiliselt palju võimalusi, mida tuleb sorteerida. Isegi teisendusklasside järsk kitsendamine, näiteks ainult teatud arvu kordi skaleerides, ei võimalda vastuvõetavat aega saavutada. Lisaks kaob pildikvaliteet. Valdav enamus fraktaaltihenduse valdkonnas tehtud uuringutest on nüüd suunatud kvaliteetse pildi saamiseks kuluva arhiveerimisaja lühendamisele.
Fraktaaltihendusalgoritmi, nagu ka teiste kadudega tihendusalgoritmide puhul on väga olulised mehhanismid, mille abil saab tihendusastet ja kao astet reguleerida. Praeguseks on selliseid meetodeid välja töötatud üsna suur hulk. Esiteks saate piirata teisenduste arvu, tagades teadlikult, et tihendusaste ei oleks fikseeritud väärtusest madalam. Teiseks võite nõuda, et olukorras, kus töödeldava fragmendi ja selle parima lähenduse vahe on üle teatud läviväärtuse, tuleb see fragment purustada (selle jaoks tuleb paigaldada mitu läätse). Kolmandaks saate keelata näiteks neljast punktist väiksemate fragmentide jagamise. Nende tingimuste läviväärtusi ja prioriteeti muutes saate väga paindlikult reguleerida pildi tihendussuhet: bitipõhisest sobitamisest kuni mis tahes tihendustasemeni.
Võrdlus JPEG-ga
Tänapäeval on kõige levinum graafika arhiveerimisalgoritm JPEG. Võrdleme seda fraktaalkompressiooniga.
Esiteks pange tähele, et mõlemad algoritmid töötavad 8-bitiste (halliskaala) ja 24-bitiste täisvärvipiltide puhul. Mõlemad on kadudeta tihendusalgoritmid ja pakuvad sarnaseid arhiveerimiskiirusi. Nii fraktalalgoritmil kui ka JPEG-il on võimalus kadude suurendamise kaudu tihendusastet suurendada. Lisaks on mõlemad algoritmid väga hästi paralleelsed.
Erinevused algavad siis, kui võtame arvesse aega, mis kulub algoritmide arhiveerimiseks/arhiveerimiseks. Seega tihendab fraktalalgoritm sadu ja isegi tuhandeid kordi kauem kui JPEG. Pildi lahtipakkimine, vastupidi, toimub 5-10 korda kiiremini. Seega, kui pilti tihendatakse ainult üks kord, kuid edastatakse võrgu kaudu ja tihendatakse mitu korda lahti, on kasulikum kasutada fraktalalgoritmi.
JPEG kasutab kujutise koosinusfunktsiooni jaotust, nii et kaod selles (isegi määratud minimaalsete kadude korral) ilmnevad lainetena ja halodena teravate värviüleminekute piiril. Just selle efekti jaoks ei meeldi inimestele seda kvaliteetseks printimiseks ettevalmistatud piltide tihendamisel kasutada: seal võib see efekt väga märgatavaks muutuda.
Fraktalalgoritm on sellest puudusest vaba. Pealegi tuleb pildi printimisel iga kord läbi viia skaleerimisoperatsioon, kuna prindiseadme raster (või joon) ei ühti pildi rastriga. Konversiooni käigus võivad tekkida ka mitmed ebameeldivad efektid, millega saab võidelda kas pilti programmiliselt skaleerides (odavate prindiseadmete puhul nagu tavalised laser- ja tindiprinterid) või varustades prindiseadme oma protsessori, kõvaketta ja komplektiga. pilditöötlusprogrammid (kallite fototüüpi masinate jaoks). Nagu võite arvata, siis fraktalalgoritmi kasutamisel selliseid probleeme praktiliselt ei teki.
Laialdaselt kasutusel oleva JPEG-i asendamine fraktalalgoritmiga ei toimu niipea (vähemalt viimase väikese arhiveerimiskiiruse tõttu), kuid multimeediarakenduste vallas, arvutimängudes on selle kasutamine igati õigustatud.
Info tihendamise põhimõtted
Iga teabe tihendamise meetodi aluseks on teabeallika mudel või täpsemalt liiasusmudel. Teisisõnu, teabe tihendamiseks kasutatakse teatud teavet selle kohta, millist tüüpi teavet tihendatakse – ilma selle teabe kohta teavet omamata on võimatu teha absoluutselt mingeid eeldusi selle kohta, milline teisendus vähendab sõnumi mahtu. Seda teavet kasutatakse tihendamise ja lahtipakkimise protsessis. Liiasusmudelit saab koostada või parameetreid muuta ka tihendusfaasis. Meetodeid, mis võimaldavad sisendandmetel põhinevat informatsiooni liiasusmudelit muuta, nimetatakse adaptiivseteks. Mitteadaptiivsed algoritmid on tavaliselt väga spetsiifilised, neid kasutatakse hästi määratletud ja muutumatute omadustega töötamiseks. Valdav enamus üsna universaalsetest algoritmidest on ühel või teisel määral kohanduvad.
Iga teabe tihendamise meetod sisaldab kahte pöördteisendust:
- kompressiooni muundamine;
- kompressiooni muundamine.
Tihendusteisendus tagab, et algsest sõnumist saadakse tihendatud sõnum. Dekompressioon tagab, et esialgne sõnum (või selle lähend) saadakse tihendatud sõnumist.
Kõik tihendusmeetodid on jagatud kahte põhiklassi
- ilma kaotuseta,
- kaotustega.
Põhiline erinevus nende kahe vahel on see, et kadudeta pakkimine võimaldab algse sõnumi täpset rekonstrueerimist. Kadudega kokkusurumine võimaldab teil saada algsest sõnumist ainult teatud ligikaudse väärtuse, st erineb algsest sõnumist, kuid jääb mõne etteantud vea piiresse. Need vead tuleb kindlaks määrata teise mudeliga – vastuvõtja mudeliga, mis määrab, millised andmed ja millise täpsusega on adressaadi jaoks olulised ning milliseid võib ära visata.
Tihendusalgoritmide omadused ja rakendatavus
Tihendussuhe
Tihendussuhe on tihendusalgoritmi peamine omadus, mis väljendab peamise rakenduse kvaliteeti. See on määratletud kui tihendamata andmete suuruse suhe tihendatud andmetesse, see tähendab:
k = S o/ S c ,Kus k- tihendusaste, S o on tihendamata andmete suurus ja S c - kokkusurutud suurus. Seega, mida kõrgem on tihendusaste, seda parem on algoritm. Tuleb märkida:
- Kui k= 1, siis algoritm ei teosta tihendamist, st saab väljundsõnumi, mille suurus on võrdne sisendsuurusega;
- Kui k < 1, то алгоритм порождает при сжатии сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.
Olukord koos k < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной n Muster:E:bit on täpselt 2 n. Seejärel erinevate sõnumite arv, mille pikkus on väiksem või võrdne n(kui on vähemalt üks lühem sõnum) on väiksem kui 2 n. See tähendab, et kõiki algsõnumeid ei ole võimalik üheselt kokkusurutud sõnumiga vastendada: mõnel algsel sõnumil ei ole tihendatud esitust või mitmel algsel sõnumil on sama tihendatud esitus ja seetõttu ei saa neid eristada.
Tihendussuhe võib olla kas konstantne koefitsient (mõned algoritmid heli, pildi jne tihendamiseks, näiteks A-seadus, μ-seadus, ADPCM) või muutuv. Teisel juhul saab selle määratleda kas konkreetse sõnumi jaoks või hinnata teatud kriteeriumide järgi:
- keskmine (tavaliselt mõne katseandmete kogumi kohta);
- maksimaalne (parima kokkusurumise juhtum);
- minimaalne (halvima kokkusurumise juhtum);
või mõni muu. Kadudeta tihendusaste sõltub sel juhul tugevalt lubatud tihendusveast või sellest kvaliteet, mis tavaliselt toimib algoritmi parameetrina.
Kaotuste taluvus
Peamiseks tihendusalgoritmide eristamise kriteeriumiks on ülalkirjeldatud kadude olemasolu või puudumine. Üldiselt on kadudeta pakkimisalgoritmid universaalsed selles mõttes, et neid saab kasutada igat tüüpi andmete puhul, samas kui kadudeta pakkimise kasutamine peab olema põhjendatud. Teatud tüüpi andmed ei aktsepteeri kadu:
- sümboolsed andmed, mille muutumine toob paratamatult kaasa muutuse nende semantikas: programmid ja nende lähtetekstid, binaarmassiivid jne;
- elulised andmed, mille muutumine võib kaasa tuua kriitilisi vigu: näiteks saadud õhusõidukite, kosmosesõidukite vms meditsiinilistest mõõteseadmetest või juhtimisseadmetest.
- korduvalt tihendatud ja lahti pakitud andmed: töögraafika, heli-, videofailid.
Kadudeta pakkimine võimaldab aga palju suuremat tihendussuhet, jättes kõrvale ebaolulise teabe, mis ei tihenda hästi. Nii näiteks võimaldab kadudeta heli tihendamise algoritm FLAC enamikul juhtudel heli tihendada 1,5–2,5 korda, samas kui kadudeta algoritm Vorbis võib sõltuvalt seatud kvaliteediparameetrist tihendada kuni 15 korda, säilitades samal ajal vastuvõetava helikvaliteedi. .
Algoritmisüsteemi nõuded
Erinevad algoritmid võivad nende täitmiseks vajada erineval hulgal arvutisüsteemi ressursse:
- RAM (vaheandmete jaoks);
- püsimälu (programmikoodi ja konstantide jaoks);
- CPU aeg.
Üldiselt sõltuvad need nõuded algoritmi keerukusest ja intelligentsusest. Üldise tendentsi kohaselt, mida parem ja universaalsem on algoritm, seda suuremaid nõudmisi see masinale esitab. Kuid teatud juhtudel võivad lihtsad ja kompaktsed algoritmid paremini töötada. Süsteeminõuded määravad nende tarbijaomadused: mida vähem nõudlik on algoritm, seda lihtsam ja seega kompaktsem, töökindlam ja odavam süsteem saab töötada.
Kuna tihendus- ja lahtipakkimisalgoritmid töötavad paarikaupa, on oluline ka süsteeminõuete ja nende suhe. Sageli saate ühte algoritmi keerulisemaks muutes teist oluliselt lihtsustada. Seega on meil kolm võimalust:
Tihendusalgoritm on palju ressursinõudlikum kui lahtipakkimisalgoritm. See on kõige levinum suhe ja seda kasutatakse peamiselt juhtudel, kui tihendatud andmeid kasutatakse mitu korda. Näiteks on digitaalsed heli- ja videopleierid. Tihendus- ja lahtipakkimisalgoritmidele on ligikaudu võrdsed nõuded. Sideliini jaoks on kõige vastuvõetavam variant, kui selle kahes otsas toimub tihendamine ja dekompressioon üks kord. Näiteks võib see olla telefoniside. Tihendusalgoritm on oluliselt vähem nõudlik kui dekompressioonialgoritm. Päris eksootiline juhtum. Seda saab kasutada juhtudel, kui saatja on ülimalt kaasaskantav seade, kus saadaolevate ressursside hulk on väga kriitiline, näiteks kosmoseaparaat või suur hajutatud andurite võrk, või need võivad olla andmed, mille lahtipakkimist on vaja väga väike protsent juhtudest, näiteks CCTV kaameratest salvestamine.
Vaata ka
Wikimedia sihtasutus. 2010. aasta.
Vaadake, mis on "teabe tihendamine" teistes sõnaraamatutes:
teabe tihendamine- teabe tihendamine - [L.G. Sumenko. Inglise-vene infotehnoloogia sõnaraamat. M.: Riigiettevõte TsNIIS, 2003.] Teemad infotehnoloogia üldiselt Sünonüümid info tihendamine EN info vähendamine ...
INFO KOMPRESSIOON- (andmete tihendamine) teabe (andmete) esitus originaaliga võrreldes väiksema bittide arvuga. Põhineb koondamise kõrvaldamisel. Seal on S. ja. ilma teabe kadumiseta ja mõne teabe kadumisega, mis pole lahendatavate ülesannete jaoks hädavajalik. TO…… Psühholoogia ja pedagoogika entsüklopeediline sõnastik
kadudeta adaptiivne teabe tihendamine- - [L.G. Sumenko. Inglise-vene infotehnoloogia sõnaraamat. M.: Riigiettevõte TsNIIS, 2003.] Teemad infotehnoloogia üldiselt EN adaptiivne kadudeta andmete tihendamineALDC ... Tehniline tõlkija juhend
teabe tihendamine/tihendamine- - [L.G. Sumenko. Inglise-vene infotehnoloogia sõnaraamat. M.: Riigiettevõte TsNIIS, 2003.] Teemad infotehnoloogia üldiselt EN tihendamine ... Tehniline tõlkija juhend
digitaalne teabe tihendamine- - [L.G. Sumenko. Inglise-vene infotehnoloogia sõnaraamat. M.: Riigiettevõte TsNIIS, 2003.] Teemad infotehnoloogia üldiselt EN tihendus ... Tehniline tõlkija juhend
Heli on lihtne laine ja digitaalne signaal on selle laine esitus. See saavutatakse analoogsignaali amplituudi salvestamisega mitu korda ühe sekundi jooksul. Näiteks tavalisel CD-l jäetakse signaal meelde 44 100 korda... ... Wikipedia
Protsess, mis vähendab andmemahtu, vähendades andmete liiasust. Andmete tihendamine viitab standardsuuruses andmete kompaktsele paigutusele. Seal on tihendused kadudega ja ilma teabe kadumiseta. Inglise keeles: Andmed... ... Finantssõnastik
digitaalse kartograafilise teabe tihendamine- Digitaalse kartograafilise teabe töötlemine selle mahu vähendamiseks, sealhulgas liiasuse kõrvaldamine esitamise nõutava täpsuse piires. [GOST 28441 99] Teemad digitaalne kartograafia Üldmõisted meetodid ja tehnoloogiad... ... Tehniline tõlkija juhend