Andmete pakkimine: erinevus redaktsioonide vahel
| 46. rida: | 46. rida: | ||
*BZIP2 |
*BZIP2 |
||
*LZW |
*LZW |
||
*JPEG 2000 (Sisaldab endas |
*JPEG 2000 (Sisaldab endas kadudeta andmete tihendamise võimalust) |
||
Kadudega andmete pakkimisel kasutatavad [[Algoritm|algoritmid]]: |
Kadudega andmete pakkimisel kasutatavad [[Algoritm|algoritmid]] arh: |
||
*MPEG1 |
*MPEG1 |
||
Redaktsioon: 11. detsember 2013, kell 21:54
 | See artikkel vajab toimetamist. (September 2012) |
 | See artikkel ootab keeletoimetamist. |
Arvutiteaduses ja informatsiooniteoorias on andmete pakkimine (ka andmete tihendamine, andmetihendus; bitimäära vähendamine; (Inglise K. "Data compression")) andmete kodeerimine selliselt, et väljundandmed on mälu mahult väiksemad kui sisendandmed. [1] Pakkimist on kahte tüüpi: kadudega ja kadudeta. Kadudeta andmetihendus vähendab bitimäära läbi selle, et leiab ja elimineerib statistilise liiasuse (Inglise K. "Statistic redundancy"). [2] Kadudeta pakkimisel informatsiooni ei lähe kaduma. Kadudega tihendamisel leitakse ebavajalik informatsioon ja eemaldatakse see. Kui andmed on pakitud, saab neid andmeid uuesti kasutada ainult siis, kui need kindlad andmed on uuesti lahti pakitud. [3]
Tihendus on vajalik, sest see aitab vähendada ressursikulu nagu andmete säilitamise ruum või edastusmaht. Kuna andmed peavad olema lahtipakitud, et neid kasutada, on andmete tihendus arvutusvõimsuse suhtes nõudlik. See tähendab seda, et andmete tihendus tähendab muude ressursside eraldamist informatsiooni mahu vähendamise nimel. Seega võib näiteks video vaatamisel vaja minna suhteliselt võimsat riistvara, et arvuti suudaks informatsiooni lahti pakkida piisavalt kiiresti, et seda videot ilma probleemideta (näiteks puhverdamisvajaduseta) vaadata. Veel on võimalus see tihendatud andmehulk täielikult lahti pakkida enne, kui seda kasutama tahetakse hakata, kuid see vajab rohkem ruumi ja aega. Seega, andmete pakkimise süsteemid tähendavad, et andmete mahu vähendamise nimel ohverdatakse muid resursse nagu aeg, arvutuslik võimsus ja andmete enda moonutus (kasutades kadudega pakkimist).
Statistiline liiasus
Statistiline liiasus (Inglise K. "Statistic redundancy") tähendab bittide hulka, mida kasutati, et sõnumit edastada miinus see bittide hulk, mis hulk informatsiooni selles sõnumis tegelikult oli. Võib ka defineerida, et see on raisatud "ruumi" hulk, mida kindla andmehulga edastamisel kasutati. Andmete tihendamine on mittetahetud statistilise liiasuse vähendamine või elimineerimine, samas kui kontrollsummadega on statistilist liiasust võimalik kasvatada. Seda tehakse vahepeal selleks, et leida edastamisvigu, kui näiteks andmeid edastatakse üle suure koormusega võrgu.
Liigid
Andmeid on võimalik pakkida kahel erineval moel:
- Kadudeta andmetihendus (Inglise K. "lossless compression")
- Kadudega andmetihendus (Inglise K. "lossy compression")
Kadudeta andmetihenduse korral saavutatakse lahti pakkimisel esialgsed andmed. Kasutatakse seda varianti tavaliselt siis, kui on oluline, et andmed säiliksid nii nagu nad alguses olid. Näiteks teksti andmete tihendamisel.
Kadudega andmetihenduse korral võib originaaliga võrreldes esineda väikeseid erinevusi. Kasutatakse peamiselt graafiliste failide puhul. Tuntuim failiformaat kus seda kasutatakse on .jpeg. Kui andmed on pakitud kasutades mõnda kadudega andmete pakkimise algoritmi, ei ole võimalik taastada sellest kadudeta versiooni.
Kadudeta andmetihendus
Kadudeta andmete pakkimise algoritmid tavaliselt kasutavad ära statistilist liiasust, et esitada andmeid sisutihedalt ilma informatsiooni kaotamata. Kadudeta andmetihendus on võimalik, sest enamus päris maailma andmetest sisaldab statistilist liiasust. Näiteks, üks pilt võib endas kanda värvide piirkondi kus värv ei muutu üle suure hulga pikslite. Selle asemel, et kodeerida "punane piksel asukohal 2000, punane piksel asukohal 2001, ..." võib andmed kodeerida "279 punast pikslit asukohal 2000, 2001, 2002" või "punased pikslid asukohal 2000-2279". See on algeline näide RLE (Inglise K. "Run-length encoding") kohta.
Grammatikapõhine andmetihendus (Inglise K. "Grammar-based compression") kujutab endas väga efektiivselt väga korduva teksti pakkimist, näiteks bioloogiliste andmete kollektsioon, internetiarhiivid, suure hulga dokumentide kollektsioon jms. Põhiline tööülesanne grammatikapõhisel pakkimisel on leida kontekstivaba korduv osa dokumendis, kustutada see nendest asukohtadest, luua sellest üks koopia ja lisada selle koopia lõppu iga asukoht, kus see lause dokumendis kordus. Näiteks, üks pikk referaat võib endas sisaldada lauset "tiigrite tüüpiline elukoht on" 200 korda. Selle asemel, et seda 208-t baiti iga kord uuesti kirjutada, kustutatakse see igast asukohast, luuakse üks koopia ja selle järgi kirjutatakse selle korduva osa asukoht näiteks nii: ""tiigrite tüüpiline elukoht on" asukohtadel 2000, 2015, 2090, .." ja selle asemel, et iga kord kasutada 208 baiti, kasutab see igal korral peale esimese ainult 36 baiti.
Kadudega andmetihendus
Kadudega andmetihenduse algoritme kasutatakse ainult olukordades kus täielik perfektsus pole nii tähtis. Kaotades mittevajalikkud detailid andmetehulgast saab säästa mäluruumi. Kadudega tihendamise algoritmid on ehitatud üles erinevate uurimiste põhjal, kuidas inimene tajub võib märkab kindlat informatsiooni. Näiteks, inimese silm on rohkem tundlik väikestele heleduse muutustele kui värvi muutustele. Selle põhjal saab teha väikeseid kompromisse informatsiooni säilitamise ja andmehulga vähendamise vahel. Mitmed populaarsed pakkimise formaadid kasutavad ära neid väikseid tajumise erinevusi nagu näiteks JPEG või muud muusika, piltide või video pakkimise algoritmid.
Kadudega piltide pakkimist saab kasutada digitaalkaamerates, et vähendada mälu kasutust piltide poolt, kuid selle nimel ohverdatakse võimalikult minimaalne hulk pildi kvaliteeti. Sarnaselt, DVD-d kasutavad kadudega MPEG-2 Video pakkimise formaati või "koodeksit" nagu seda kutsutakse heli ja videote pakkimisel. Kadudega heli pakkimisel, kasutatakse psühhoakustika (Inglise K. "psychoacoustics") uuringutega kooskõlas leiutatud meetodeid meetodeid, et eemaldada mitte-kuuldavaid (või vaevu kuuldavaid) komponente kogu andmete hulgast. [4] Inimese kõne pakkimimist tehakse tihti veelgi spetsiaalsemate tehnikatega. Kõne kodeerimine või hääle kodeerimine on tihti eristatud tavalisest heli pakkimisest. Hääle pakkimist kasutatakse näiteks internetitelefonide puhul ja heli pakkimist kasutatakse näiteks muusika CD-de puhul, kus muusika kirjutatakse CD plaadile tihendatud vormis ja helimängijad peavad helifailid lahti pakkima.
Arhiveerimine
Kindlasti tuleks eristada andmete pakkimisest teist tüüpi andmesuuruste vähendamist - arhiveerimist. Kuigi enamus tänapäeval rohkem levinuid pakkimisprogramme lubavad ka arhiveerimist (Näiteks WinZip, WinRar, WinAce, arj, jne.), on need siiski kaks erinevat asja.
Pakkimine on ainult kindla andmehulga tihendamine, mis lubab vähendada selle kindla andmehulga mahtu. Arhiveerimine on mitme erineva andmehulga, vahepeal ka erinevat tüüpi andmehulga, tihendus üheks failiks (arhiiviks).
Algoritmid
Kadudeta andmete pakkimisel kasutatavad algoritmid on:
- DEFLATE
- RLE
- GZIP
- BZIP2
- LZW
- JPEG 2000 (Sisaldab endas kadudeta andmete tihendamise võimalust)
Kadudega andmete pakkimisel kasutatavad algoritmid arh:
- MPEG1
- MPEG2
- MPEG3
- MPEG4
- JPEG
- MP3
- DOLBY AC-3
Andmete pakkimise maksimaalsuse saavutamiseks kasutatakse erinevaid algoritme koos.
Kasutusalad
Heli
Heli andmete tihendamist, mida eristatakse dünaamilise raadiuse tihendamisest (Inglise K. "Dynamic range compression"), kasutatakse selleks, et vähendada edastamiseks vajalikku ribalaiust ja ladustamiseks vajalikku mälumahtu. Heli andmete tihendamise algoritme implementeeritakse tarkvarasse ja neid kutsutakse heli koodeksiteks (Inglise K. "Codec"). Kadudega heli andmete pakkimise algoritmid või koodeksid võimaldavad efektiivsemat andmete pakkimist, kuid vähendavad kvaliteeti, ja neid kasutatakse väga paljudes heliga seotud rakendustes. Need algoritmid peaaegu kõik tuginevad psühhoakustika uurimustöödele, mis leida ja vähendada inimesele vähem tajutavad vähem kuuldavad või mittetähenduslikud helid, seega vähendades mäluruumi ja ribalaiuse vajadust ladustamise või edastamise puhul.
Nii kadudega kui kadudeta pakkimisel vähendatakse informatsiooni liiasust, kasutades meetodeid nagu kodeerimine, mustri eristamine ja lineaarne ennustamine, et vähendada andmete hulka, mis esindab tihendamata informatsiooni[5].
Dünaamilise raadiuse tihendamine (Inglise K. "Dynamic range compression") tähendab valjude helide vaigistamist ja vaiksete helide valjemaks tegemist, mis jätab helitugevuse teatud valjuduse ja vaiksuse limiidi vahele. See eemaldab erandlikud olukorrad, kus helitugevus on liiga kõrge või liiga madal, ja seeläbi vähendab helifaili suurust.
Video
Video andmete tihendus kasutab tänapäevaseid kodeerimistehnikaid, et vähendada liiasust video andmetes. Enamus video andmete pakkimise algoritme või koodekseid kombineerivad ruumilise pildi pakkimise (Inglise K. "Spatial image compression") ja ajalise liikumise hüvitamise (Inglise K. "Temporal motion compensation"). Enamus video koodekseid kasutab heli pakkimise tehnikaid paralleelselt video pakkimisele, aga andmed on ühendatud üheks hulgaks[6].
Kodeerimise teooria
Video andmeid saab kujutada kui seeriat paigal olevaid pilte (kaadreid). Piltide (Kaadrite) jada sisaldab endas ajalist ja ruumilist liiasust mida video pakkimise algoritmid üritavad elimineerida või kodeerida väiksemasse suurusesse. Sarnasused saab kodeerida näiteks ainult ladustades ainult erinevused kahe järjestikkuse kaadri vahel, või kasutades erinevaid inimese taju iseärasusi. Näiteks, väikeseid värvi erisusi on raskem inimese jaoks tajuda, kui erinevusi heleduses. Pakkimisalgoritmid saavad seetõttu luua mitme järgneva pildi värvide keskmise ja kasutada seda värvi, et vähendada ruumi.
Üks kõige võimsamaid tehnikaid video pakkimiseks on raamiväline tihendus (Inglise K. "Interframe compression"), kus kasutatakse varasemaid või järgnevaid kaadreid jadas, et pakkida käesolev kaader, kuid sarnane meetod, raamisisene tihendus (Inglise K. "Intraframe compression"), kasutab ainult käesolevat kaadrit, olles rohkem pildi tihendus[7].
Raamivälise pakkimise puhul võrreldakse igat kaadrit jadas eelnevaga, et näha, kas järgneval kaadril on alasid, kus midagi ei ole muutunud. Kui selline ala eksisteerib, siis kopeeritakse see ala lihtsalt eelmiselt pildilt järgnevale. Kui selle ala asukoht on muutunud, siis pööratakse ja liigutatakse eelmisel kaadril olevat ala. See siiski on palju vähem mälumahtu nõudev, kui iga pilt uuesti mälusse jätta ja vajadusel esitada. Raamiväline tihendus töötab ideaalselt programmide puhul, mis lihtsalt mängivad video vaatajale[8].
Probleem raamivälise pakkimisega on aga see, et kuna see algoritm kopeerib andmeid ühelt kaadrilt teisele, võib juhtuda olukordi, kus vajalik kaader on kaduma läinud. Nendes olukordades ei ole võimalik konstrueerida järgmiseid kaadreid õigesti.
Vaata ka
Viited
- ↑ Mahdi, O.A. (2012). "Implementing a Novel Approach an Convert Audio Compression to Text Coding via Hybrid Technique" (PDF). International Journal of Computer Science Issues. 9 (6, No. 3): 53–59. Vaadatud 6. märtsil 2013.
{{cite journal}}: eiran tundmatut parameetrit|coauthors=, kasuta parameetrit (|author=) (juhend); eiran tundmatut parameetrit|month=(juhend) - ↑ Pujar, J.H. (2010). "A New Lossless Method of Image Compression and Decompression Using Huffman Coding Techniques" (PDF). Journal of Theoretical and Applied Information Technology. 15 (1): 18–23.
{{cite journal}}: eiran tundmatut parameetrit|coauthors=, kasuta parameetrit (|author=) (juhend); eiran tundmatut parameetrit|month=(juhend) - ↑ Salomon, David (2008). A Concise Introduction to Data Compression. Berlin: Springer. ISBN 9781848000728.
- ↑ Arcangel, Cory. "On Compression" (PDF). Vaadatud 12. detsembril 2013.
- ↑ Mahdi, O.A. (2012). "Implementing a Novel Approach an Convert Audio Compression to Text Coding via Hybrid Technique" (PDF). International Journal of Computer Science Issues. 9 (6, No. 3): 53–59. Vaadatud 6. märtsil 2013.
{{cite journal}}: eiran tundmatut parameetrit|coauthors=, kasuta parameetrit (|author=) (juhend); eiran tundmatut parameetrit|month=(juhend) - ↑ "Video Coding". Center for Signal and Information Processing Research. Georgia Institute of Technology. Vaadatud 12. detsembril 2013.
- ↑ Faxin Yu, Hao Luo, Zheming Lu (2010). Three-Dimensional Model Analysis and Processing. Berlin: Springer. Lk 47. ISBN 9783642126512.
{{cite book}}: CS1 hooldus: mitu nime: autorite loend (link) - ↑ Bhojani, D.R. "4.1 Video Compression" (PDF). Hypothesis. Vaadatud 12. detsembril 2013.