Пређи на садржај

Kompresija podataka

С Википедије, слободне енциклопедије

U obradi signala, kompresija podataka, kodiranje izvora,[1] ili redukcija bitne stope obuhvata kodiranje informacija koristeći manji broj bitova nego u originalnoj reprezentaciji.[2] Kompresija može da bude bilo sa gubicima ili bez gubitaka. Kompresija bez gubitka redukuje bitove putem identifikacije i eliminacije statističke izlišnosti. Informacije se ne gube pri tom vidu kopresije. Kompresija sa gubicima redukuje bitove uklanjanjem nepotrebnih ili manje važnih informacija.[3]

Proces redukovanja veličine datoteke sa podacima se obično naziva kompresijom podataka. U kontekstu prenosa podataka, toj proces se naziva kodiranjem izvora; kodiranje se tipično vrši na izvoru podataka pre njihovog skladištenja ili prenosa.[4] Kodiranje izvora ne treba mešati sa kodiranjem kanala radi detekcije i korekcije grešaka, ili kodiranjem linije sredstva za mapiranje podataka na signal.

Kompresija je korisna jer se njom redukuju resursi neophodni za skladištenje i prenos podataka. Računarski resursi se konzumiraju pri procesu kompresije i isto tako pri suprotnom procesu (dekompresiji). Kompresija podataka je zavisna od kompromisa prostorno–vremenske kompleksnosti. Na primer, kompresiona shema za video može da zahteva skup hardver da bi se video dovolno brzo dekompresovao tako da se može gledati kao da je već bio dekomprimovao. Opcija da se video u potpunosti dekompresuje pre gledanja može da pude nepodesna ili da zahteva znatan dodatni prostor. Dizajn shema za kompresiju podataka obuhvata kompromise među mnoštvom različitih faktora, uključujući stepen kompresije, količinu unešene distorzije (pri korištenju kompresije sa gubitkom), i računarske resurse neophodne za komprimovanje i dekomprimovanje podataka.[5][6]

Kompresija bez gubitka

[уреди | уреди извор]

Algoritmi kompresije bez gubitka obično iskorišćavaju statističku redundanciju za prikazivanje podatka bez gubitaka informacija, tako da je proces reverzibilan. Kompresija bez gubitaka je moguća zato što većina podataka iz realnog sveta pokazuje statističku izlišnost. Na primer, jedna slika može imati područja boje koja se ne menjaju tokom nekoliko piksela; umesto kodiranja „crveni piksel, crveni piksel, ...” podaci mogu da budu kodirani kao „279 crvenih piksela”. Ovo je bazni primer kodiranja dužine trajanja; postoje mnoge sheme za smanjenje veličine datoteke uklanjanjem redundancije.

Lempel–Zivovi (LZ) kompresioni metodi su među najpopularnijim algoritmima za skladištenje bez gubitaka.[7] DEFLATE je varijacija LZ pristupa optimizovana za dekompresiju govora i poboljšanje kompresionog odnosa, ali kompresija može da bude spora. Tokom sredine 1980-ih, nakon rada Terija Velča, Lempel-Ziv-Velčov (LZW) algoritam brzo je postao preferentni metod za većinu kompresionih sistema opšte namene. LZW se koristi u GIF imidžima, programima kao što je PKZIP, i hardverskim uređajima kao što su modemi.[8] LZ metodi koriste kompresioni model koji je baziran na tabelama, pri čemu se tabelarnim unosima zamenjuju ponavljajući nizovi podataka. Za većinu LZ metoda, ova tabela se dinamički generiše iz ranijih podataka na ulazu. Sama tabela je obično kodirana pomoću Hafmanovih kodova. Gramatički zasnovini kodovi poput ovih mogu da mogu da kompresuju visoko repetitivne podatke sa ekstremnom efikasnošću, na primer, kolekcija biologiških podataka o istoj ili blisko srodnim vrstama, ogromna kolekcija dokumenata sa višestrukim verzijama, internetsko arhiviranje, etc. Osnovni zadatak na gramatici zasnovanih kodova je konstruisanje bezkontekstne gramatike izvedene iz pojedinačnih nizova. Drugi praktični gramatički kompresioni algoritmi su Sekvitur i Re-Pair.

Najsnažniji moderni kompresori bez gubitaka koriste probabilističke modele, kao što je predviđanje parcijalnog podudaranja. Barous-Vilerova transformacija se isto tako može smatrati indirektnom formom statističkog modelovanja.[9] U daljem poboljšanju direktne upotrebe probabilističkog modelovanja, statističke procene se mogu povezati sa algoritmom zvanim aritmetičko kodiranje. Aritmetičko kodiranje je moderna tehnika kodiranja koja koristi matematičke proračune mašine konačnog stanja za proizvođenje niza kodiranih bitova iz serije simbola inputnih podataka. Ovim pristupom se može ostvariti superiorna kompresija u odnosu na druge tehnike, kao što je dobro poznati Hafmanov algoritam. Pri aritmetičkom kodiranju se koriste unutrašnja memorijska stanja da bi se izbegla potreba za mapiranjem jedan-na-jedan individualnih ulaznih simbola na distinktne reprezentacije koje koriste celobrojni broj bitova. Do čišćenja unutrašnje memorije dolazi samo nakon što se iskodira celokupni niz simbola podataka. Aritmetičko kodiranje je veoma podesno za zadatke prilagodljive kompresije podataka gde statistika varira i zavisi od konteksta, jer se ono lako može povezati sa adaptivnim modelom distribucije verovatnoće ulaznih podataka. Jedan rani primer upotrebe aritmetičkog kodiranja je bio u opcionom (mada ne široko korištenom) svojstvu JPEG standarda kodiranja slka.[10] Od tog vremena je ono bilo primenjeno na razne druge dezajne, uključujući H.263, H.264/MPEG-4 AVC i HEVC za video kodiranje.[11]

Kompresija sa gubicima

[уреди | уреди извор]

U kasnim 1980-im, digitalne slike su postale uobičajene, i standardi za kompresiju slika bez gubitaka su se pojavili. U ranim 1990-im, metode kompresije sa gubicima su ušle u široku upotrebu.[8] U tim shemama, izvestan gubitak informacije je prihvatljiv, jer odbacivanje nebitnih detalja može da uštedi skladišni prostor. Postoji korespondirajući kompromis između očuvanja informacija i smanjenja veličine podataka. Šeme kompresije podataka sa gubitkom su dizajnirane istraživanjem načina na koji ljudi spoznaju date podatke. Na primer, ljudsko oko je senzitivnije za suptilne varijacije u osvetljenju, nego za varijacije boje. Kompresija JPEG imidža se delimično ostvaruje zaokruživanjem nebitnih bitova informacija.[12] Brojni popularni kompresioni formati iskorištavaju ove perceptivne razlike, uključujući psihoakustiku za zvuk, i psihovizualne efekte za imidže i video.

Kompresija sa gubicima se može koristiti u digitalnim kamerama, za povećanje kapaciteta skladištenja uz minimalnu degradaciju kvaliteta slike. Slično tome, DVD tehnologija koristi MPEG-2 video kodirajući format sa gubicima za video kompresiju.

U audio kompresiji sa gubicima, metodi psihoakustike se koriste za uklanjanje nečujnih (ili manje čujnih) komponenti audio signala. Kompresija ljudskog govora se često izvodi još više specijalizovanim tehnikama; kodiranje govora, ili kodiranje glasa, ponekad se izdvaja kao zasebna disciplina od audio kompresije. Različiti standardi audio i govorne kompresije su prisutni u formatima audio kodiranja. Kompresija glasa se koristi u internetskoj telefoniji, dok se audio kompresija koristi za CD skladištenje, i audio plejeri dekodiraju te zapise.[9]

Teorija

[уреди | уреди извор]

Teoretsku zaleđinu kompresije pruža teorija informacije (koja je blisko srodna sa algoritamsko informacionom teorijom) za kompresiju bez gubitaka i teorijom stopne distorzije za kompresiju sa gubicima. Ove oblasti izučavanja je esencijalno stvorio Klod Šenon, koji je objavio fundamentalne publikacije u ovom polju tokom kasnih 1940-ih i ranih 1950-ih. Teorija kodiranja je isto tako srodna oblast. Ideja kompresije podataka je duboko povezana sa statističkim zaključivanjem.[13]

Mašinsko učenje

[уреди | уреди извор]
Takođe pogledajte: Mašinsko učenje

Postoji bliska veza između mašinskog učenja i kompresije: sistem koji predviđa posteriorne verovatnoće sekvence polazeći od njene celokupne istorije može se koristiti za optimalnu kompresiju podataka (koristeći aritmetičko kodiranje na izlaznoj distribuciji) dok se optimalni kompresor može koristiti za predviđanje (pronalaženjem simbola koji se najbolje komprimuju, s obzirom na prethodnu istoriju). Ova je ekvivalentnost korištena kao opravdanje za upotrebu kompresije podataka kao merila za „generalnu inteligenciju”.[14][15][16]

Reference

[уреди | уреди извор]
  1. ^ Wade, Graham (1994). Signal coding and processing (2 изд.). Cambridge University Press. стр. 34. ISBN 978-0-521-42336-6. Приступљено 22. 12. 2011. „The broad objective of source coding is to exploit or remove 'inefficient' redundancy in the PCM source and thereby achieve a reduction in the overall source rate R.” 
  2. ^ Mahdi, O.A.; Mohammed, M. A.; Mohamed, A. J. (novembar 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. Архивирано из оригинала (PDF) 28. 12. 2018. г. Приступљено 6. 3. 2013. 
  3. ^ Pujar, J.H.; Kadlaskar, L. M. (maj 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. Архивирано из оригинала (PDF) 28. 12. 2018. г. Приступљено 11. 03. 2019. 
  4. ^ Salomon, David (2008). A Concise Introduction to Data Compression. Berlin: Springer. ISBN 9781848000728. 
  5. ^ Mittal, J.; Vetter (2015), „A Survey Of Architectural Approaches for Data Compression in Cache and Main Memory Systems”, IEEE Transactions on Parallel and Distributed Systems, IEEE 
  6. ^ Tank, M.K. (2011). Implementation of Limpel-Ziv algorithm for lossless compression using VHDL. Thinkquest 2010: Proceedings of the First International Conference on Contours of Computing Technology. Berlin: Springer. стр. 275—283. 
  7. ^ Navqi, Saud; Naqvi, R.; Riaz, R. A.; Siddiqui, F. (april 2011). „Optimized RTL design and implementation of LZW algorithm for high bandwidth applications” (PDF). Electrical Review. 2011 (4): 279—285. 
  8. ^ а б Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media, Inc. стр. 1069. ISBN 978-1-57955-008-0. 
  9. ^ а б Mahmud, Salauddin (mart 2012). „An Improved Data Compression Method for General Data” (PDF). International Journal of Scientific & Engineering Research. 3 (3): 2. Архивирано из оригинала (PDF) 28. 12. 2018. г. Приступљено 6. 3. 2013. 
  10. ^ Lane, Tom. „JPEG Image Compression FAQ, Part 1”. Internet FAQ Archives. Independent JPEG Group. Приступљено 6. 3. 2013. 
  11. ^ G. J. Sullivan; J.-R. Ohm; W.-J. Han; T. Wiegand (decembar 2012). „Overview of the High Efficiency Video Coding (HEVC) Standard” (PDF). IEEE Transactions on Circuits and Systems for Video Technology. IEEE. 22 (12). Приступљено 12. 8. 2017. 
  12. ^ Arcangel, Cory. „On Compression” (PDF). Приступљено 6. 3. 2013. 
  13. ^ Marak, Laszlo. „On image compression” (PDF). University of Marne la Vallee. Архивирано из оригинала (PDF) 28. 5. 2015. г. Приступљено 6. 3. 2013. 
  14. ^ Mahoney, Matt. „Rationale for a Large Text Compression Benchmark”. Florida Institute of Technology. Архивирано из оригинала 18. 08. 2006. г. Приступљено 5. 3. 2013. 
  15. ^ Kahiri; Ben-Gal I.; Hauser, S. (2009). „Measuring the Efficiency of the Intraday Forex Market with a Universal Data Compression Algorithm” (PDF). 33 (2). Computational Economics: 131—154.  |first1= захтева |last1= у Authors list (помоћ)
  16. ^ I. Ben-Gal (2008). „On the Use of Data Compression Measures to Analyze Robust Designs” (PDF). 54 (3). IEEE Transactions on Reliability: 381—388. Архивирано из оригинала (PDF) 26. 09. 2020. г. Приступљено 11. 03. 2019. 

Literatura

[уреди | уреди извор]
  • Tank, M.K. (2011). Implementation of Limpel-Ziv algorithm for lossless compression using VHDL. Thinkquest 2010: Proceedings of the First International Conference on Contours of Computing Technology. Berlin: Springer. стр. 275—283. 
  • Salomon, David (2008). A Concise Introduction to Data Compression. Berlin: Springer. ISBN 9781848000728. 
  • Wade, Graham (1994). Signal coding and processing (2 изд.). Cambridge University Press. стр. 34. ISBN 978-0-521-42336-6. Приступљено 22. 12. 2011. „The broad objective of source coding is to exploit or remove 'inefficient' redundancy in the PCM source and thereby achieve a reduction in the overall source rate R.” 
  • Reza, Fazlollah M. (1994) [1961]. An Introduction to Information Theory. New York: Dover [McGraw-Hill]. ISBN 978-0-486-68210-5. 
  • Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, Inc. ISBN 978-0-471-12845-8. 
  • Auffarth, B; Lopez-Sanchez, M.; Cerquides, J. (2010). „Comparison of Redundancy and Relevance Measures for Feature Selection in Tissue Classification of CT images”. Advances in Data Mining. Applications and Theoretical Aspects. Springer. стр. 248—262. CiteSeerX 10.1.1.170.1528 Слободан приступ. 

Spoljašnje veze

[уреди | уреди извор]
Kompresija podataka на Викимедијиној остави.
Преузето из „https://sr.wikipedia.org/w/index.php?title=Kompresija_podataka&oldid=28522060”