Kadudeta pakkimine
Kadudeta pakkimine on klass andmete pakkimise algoritme, mis võimaldab pakitud andmetest algandmeid täpselt taastada. Seevastu kadudega pakkimine võimaldab ainult andmete ligilähedast rekonstrueerimist, kuigi see tavaliselt parandab tihendusastet (ja seega vähendab faili mahtu).
Kadudeta andmete pakkimist kasutatakse paljudes rakendustes. Näiteks kasutavad seda ZIP-faili vorming ja GNU tööriist gzip. Sageli on ka kadudeta pakkimise meetodid kasutuses kadudega andmete pakkimise tehnoloogiatest (nt MP3-helifailivorming ja muud kadudega helifailide vormingud).
Kadudeta pakkimine on kasutusel juhtudel, kui on oluline, et lahti pakitud ja originaalandmed oleks identsed või, kui kõrvalekalded algandmetest on ebasoovitavad. Tüüpilised näited on käivitatavad programmid, dokumendid ja lähtekood. Mõned pildifailivormingud, nagu PNG või GIF, kasutavad ainult kadudeta pakkimist, samas kui teised, nagu TIFF ja MNG, võivad kasutada kas kadudeta või kadudega pakkimise meetodeid. Kadudeta helifailivormingud on kõige sagedamini kasutatavad arhiveerimiseks või tootmise eesmärgil, samas kui väiksemate kadudega helifailid on tavaliselt kasutusel kaasaskantavate mängijate puhul, ning muudel juhtudel, kui ruum on piiratud või täpne edastus pole vajalik.[1]
Kadudeta pakkimise meetodid muuda
Enamus kadudeta pakkimise programme teeb kahte asja järjestikku: esimene samm genereerib statistilise mudeli sisendandmetest ja teine samm kasutab seda mudelit, et seada sisendandmetele vastavusse bitijadad sellisel viisil, et "tõenäolised" (tihedamini esinevad) andmed toodavad lühemad bitijadad kui "ebatõenäolised" andmed.[2]
Peamised algoritmid, mida kasutatakse bitijadade loomiseks, on Huffmani kodeerimine (mida kasutab ka DEFLATE) ja aritmeetiline kodeerimine. Aritmeetiline kodeerimine saavutab tihendusastme, mis on lähedal parimale võimalikule antud statistilise mudeli puhul, mille annab ette informatsiooni entroopia. Huffmani kodeerimine on lihtne ja kiire, kuid annab halbu tulemusi mudelite puhul, mis tegelevad sümbolite tõenäosustega, mis lähenevad ühele.[3]
On kaks peamist võimalust statistilise mudeli koostamiseks: staatilises mudelis andmed analüüsitakse ja nende põhjal ehitatakse mudel, mis salvestatakse koos kokku pakitud andmetega. Selline lähenemine on lihtne ja paindlik, kuid puuduseks on see, et mudel ise võib mälus palju ruumi võtta, ning ainult ühe mudeli kasutamine ei sobi failidele, mis sisaldavad palju erisuguseid andmeid. Adaptiivsed mudelid muudavad end dünaamiliselt vastavalt kokku pakitavatele andmetele. Nii kooder kui ka dekooder alustavad triviaalse mudeliga, mille efektiivsus kasvab andmete pakkimisel. Enamus tänapäeval kasutatavaid pakkimisvahendeid kasutavad adaptiivseid koodreid.
Kadudeta pakkimise meetodeid võib liigitada vastavalt sellele, mis tüüpi andmeid nad on mõeldud pakkima. Kuigi põhimõtteliselt saab kasutada kõiki üldkasutatavaid kadudeta pakkimise algoritme (üldkasutatav tähendab, et nad suudavad vastu võtta mis tahes bitijadasid) mis tahes tüüpi andmete pakkimiseks, paljud ei suuda olulisel määral kokku pakkida seda tüüpi andmeid, mille jaoks nad ei ole loodud.
Multimeedia muuda
Multimeedia pakkimise tehnikad kasutavad ära kujutistele omaseid tunnuseid, näiteks kahemõõtmelistel piltidel asetsevad sama tooni pikslid tihti kõrvuti. Iga piksel peale esimese asendatakse tema ja tema vasaku naabri värvikoodi vahega. Sellisel puhul tekivad palju suurema tõenäoususega väiksemad tooniväärtused kui suuremad. Selline reegel kehtib sageli ka helide puhul ja sellise meetodiga saab kokku ka pakkida helifaile, mis koosnevad peamiselt madalatest sagedustest ja vaiksetest helidest. Piltidega saab seda sammu korrata, kui võtta vahe ülemise piksliga ja videote puhul saab võtta vahe järgmise kaadri vahel.
Hierarhiline versioon sellest tehnikast võtab kõrvuti asetsevad andmepunktid, salvestab nende vahe ning summa ja kõrgemal tasemel jätkab nende summadega madalama eraldusvõimega. Seda nimetatakse diskreetseks lainekese teisenduseks. Lisaks kasutab JPEG2000 andmepunkte teistest paaridest ja korrutamisteguritest, et segada neid andmepunktide vahesse. Need tegurid peavad olema täisarvud, nii et tulemuseks oleks igal juhul täisarv. Nii et väärtused, ja ka faili maht, on suuremad, kuid loodetavasti on väärtuste jaotus kontsentreeritum.[4]
Adaptiivne kodeering kasutab heli kodeerimisel tõenäosusi eelmisest diskreedist (sample), kujutiste puhul ülemise vasakpoolse piksli tõenäosusi ja videote puhul eelmise kaadri tõenäosusi. Diskreetse lainekese teisenduse puhul kasutatakse ka hierarhilist tehnikat.
Krüptograafia muuda
Krüptosüsteemid sageli pakivad andmeid kokku enne krüpteerimist, et suurendada turvalisust. Kui seda õigesti rakendada, suurendab andmete pakkimine arvestatavalt lekkepiiri (minimaalset šifferteksti hulka, mille peal erinevaid võtmeid katsetades on võimalik kood murda), sest pakkimine peidab mustreid, mis võivad hõlbustada krüptoanalüüsi. Siiski, paljud tavalised kadudeta pakkimise algoritmid toodavad päiseid, pakendeid, tabeleid või muid aimatavaid väljundeid, mis võivad hoopis krüptoanalüüsi lihtsustada. Seega, krüptosüsteemid peavad rakendama pakkimisalgoritme, mis ei tekita selliseid mustreid.[5]
Täitmisprogrammid muuda
Iseavanevates arhiivides paiknevad täitmisprogrammid sisaldavad rakendust ja lahtipakkijat. Käivitamisel pakib lahtipakkija rakenduse lahti ja käivitab algse rakenduse. See on sageli kasutusel demode (võimalikult väikse mahuga audio-visuaalne programm) programmeerimisel, kus võistlustel osalevad programmid, mille mahu piiriks võib olla lausa 4 kilobaiti.[6] Seda tüüpi pakendamist ei kasutata vaid täiteprogrammide jaoks, vaid ka skriptide jaoks, nagu näiteks JavaScript.
Viited muuda
- ↑ Eric Roberts. "Data Compression". University of Stanford. Vaadatud 15.01.2018.
- ↑ Mahdi, O.A.; Mohammed, M.A.; Mohamed, A.J. (november 2012). ""Implementing a Novel Approach an Convert Audio Compression to Text Coding via Hybrid Technique"". International Journal of Computer Science Issues 9 (6, No. 3). Lk 53-59.
{{raamatuviide}}: CS1 hooldus: mitu nime: autorite loend (link) - ↑ Matt Mahoney. "Data Compression Explained" (PDF). Vaadatud 15.01.2018.
- ↑ Tom Lane. "JPEG image compression FAQ, part 1". Internet FAQ Archives. Vaadatud 15.01.2018.
- ↑ "Compression and Encryption". Vaadatud 15.01.2018.
- ↑ Janus Kopfstein (05.14.2012). "This 4-kilobyte demo squeezes a universe of fractals into the size of a Word document". The Verge. Vaadatud 09.11.2012.
{{netiviide}}: kontrolli kuupäeva väärtust:|Aeg=(juhend)