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
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]
