Tehnike kompresije podataka

Uvod u tehnike kompresije

• Kompresija podataka smanjuje veličinu podataka uz očuvanje ključnih informacija.
• Cilj kompresije je optimizovati pohranu i ubrzati prenos podataka.
• Kompresija se postiže korišćenjem matematičkih algoritama za uklanjanje nepotrebnih podataka.
• Kompresija se koristi u svakodnevnom životu za arhiviranje datoteka (ZIP, RAR, PDF), slika (JPEG, PNG, WebP), zvuka (MP3, AAC, FLAC), videa (MPEG, H.264, AV1), te u streamingu(YouTube, Netflix, Spotify).

Kompresija bez gubitaka

• Kompresija bez gubitaka omogućava originalnim podacima da se u potpunosti rekonstruišu nakon dekompresije.
• Uklanjanje suvišnih podataka smanjuje veličinu datoteka.
• Koristi se u tekstualnim, slikovitim i audio formatima.
• Redundantnost podataka podrazumeva prepoznavanje ponavljajućih uzoraka.
• Metode kodiranja uključuju kodiranje sa fiksnom dužinom(ASCII, binarni kod) i kodiranje sa varijabilnom dužinom(Huffmanovo kodiranje, Lempel-Ziv algoritmi).

Huffmanovo Kodiranje

• Češće korišćeni znakovi dobijaju kraće kodove, a ređi znakovi dulje.
• Smanjuje prosječnu duljinu kodiranog teksta.
• Efikasna je kompresija bez gubitaka.
• Koristi se u ZIP, GZIP, PNG, MP3(entropijska faza kodiranja).

Lempel-Ziv algoritmi

• Lempel-Ziv algoritmi(LZ77, LZ78, LZW) predstavljaju jednu od ključnih grupa algoritama za kompresiju podataka bez gubitaka.
• Algoritmi prepoznaju ponavljajuće uzorke u podacima.
• Razvili su ih Abraham Lempel i Jacob Ziv između 1977. i 1978. godine.
• Ovi algoritmi se primenjuju u ZIP, RAR, PNG, GIF i drugim formatima.

LZ77 Princip Rada

• Algoritam koristi klizni prozor koji sadrži prethodno obrađeni tekst.
• Zapisuje se referenca na raniji dio podataka umjesto ponavljanja istih podataka.
• Podaci se kodiraju u trojkama - (offset, duljina, sljedeći znak).
• Offset predstavlja udaljenost unatrag do podudarnosti.
• Duljina je broj znakova koji se podudaraju.
• Sljedeći znak je prvi novi znak nakon podudaranja.
• Primer ulaznog niza: ABABBCABABBCAB, rezultat kodiranja: (0,0,A), (0,0,B), (2,2,A), (0,0,C), (4,3,B).

LZ78 Princip rada

• LZ78 gradi rečnik ponavljajućih sekvenci tokom obrade podataka, umesto da koristi klizni prozor.
• Podaci se beleže kao(indeks, novi znak).
• Indeks upućuje na već sačuvan niz u rečniku.
• Novi znak je onaj koji dolazi nakon referencirane sekvence.
• Varijanta LZ78 algoritma se koristi u GIF formatu.
• Ulazni niz: ABABBCABABBCAB; Rezultat kodiranja:(0,A), (0,B), (1,B), (3,A), (2,C), (6,B).

LZW Princip rada

• LZW je unapređena verzija LZ78 koja koristi unapred definisani rečnik, koji se nadograđuje tokom obrade.
• Rečnik se sam proširuje, i nema potrebe za beleženjem dodatnih znakova.
• Nalazi primenu u GIF, TIFF, Unix "compress" programima.
• Popularan je zbog jednostavnosti i brzine obrade.
• Ulazni niz: ABABBCABABBCAB, rezultat kodiranja: A, B, 3, 4, C, 7, 5, 6, B..

ZIP i RAR

• ZIP i RAR su formati koji se najčešće koriste za arhiviranje i kompresiju datoteka.
• Omogućuju smanjenje veličine datoteka i grupiranje više datoteka u jednu arhivu.
• ZIP koristi kombinaciju LZ77 i Huffmanovog kodiranja.
• RAR koristi napredniju verziju LZ77 i adaptivno kodiranje za bolju kompresiju.
• Karakteristike ZIP uključuju bržu kompresiju i manji stupanj kompresije dok RAR pruža sporiju kompresiju ali bolju kompresiju.

7-Zip (LZMA)

• 7-Zip je open-source format arhive koji koristi algoritam LZMA(Lempel-Ziv-Markov Chain Algorithm).
• Dizajniran je za postizanje najvećeg stupnja kompresije uz očuvanje brzine dekompresije.
• LZMA koristi LZ77 mehanizam za pronalaženje ponavljajućih uzoraka, Markovljeve modele za predviđanje strukture podataka, i aritmetičko kodiranje za optimizaciju krajnje veličine arhive.

Markovljevi Modeli u Kompresiji

• Markovljevi modeli predviđaju vjerojatnost pojavljivanja sljedećeg simbola na temelju prethodnih podataka.
• Prepoznaju obrasce u podacima i koriste ih za poboljšano kodiranje i prilagodbu modela kompresije ovisno o vrsti podataka.
• Pružaju veću preciznost kodiranja od klasičnih LZ algoritama jer predviđaju sljedeće simbole umjesto ponavljanja niza.

Primer Markovljevih Modela

• Ulazni tekst: "THE CAT SAT ON THE MAT".
• Model procjenjuje koji su simboli vjerojatni, na temelju prethodnih podataka.
• Tablica prijelaznih vjerojatnostima: T-H(80%), T-O(20%), H-E(100%) itd.
• Model kodira skup vjerojatnih prijelaza, a ne svaki simbol zasebno, smanjujući količinu podataka.
• Ukupno bitova bez kompresije iznosi 176, dok je nakon kompresije cca 92, što je redukcija od 48%.

Aritmetičko kodiranje

• Aritmetičko kodiranje vrši kompresiju korišćenjem raspona decimalnih vrednosti umesto fiksnih bitnih kodova.
• Koristi kontinuirani interval između 0 i 1 za predstavljanje podataka.
• Pruža kompaktniju reprezentaciju podataka jer koristi manje bitova od tradicionalnih metoda.
• Bolje iskorištava vjerojatnost pojavljivanja simbola i može kodirati delove bita, a ne samo cele bitove.

PNG Format

• PNG(Portable Network Graphics) je format za slike bez gubitaka(lossless compression).
• Koristi se za slike sa visokom preciznošću i prozirnošću.
• Kompresija se vrši filtriranjem podataka i korišćenjem DEFLATE algoritma(kombinacija LZ77 i Huffmanovog kodiranja).
• Podržava prozirnost(alfa kanal), čuva kvalitet slike, i bolji je od JPEG za slike sa oštrim rubovima i tekstom.
• Ulazna slika 800x600 raw podataka veličine 1,44MB, pretvara se u 320KB(redukcija od 78%).

FLAC Format

• FLAC(Free Lossless Audio Codec) je audio format koji koristi kompresiju bez gubitaka.
• Omogućuje smanjenje veličine audio datoteka bez žrtvovanja kvalitete.
• Koristi predikciju uzoraka(analiza zvučnih valova) i LPC za predviđanje uzoraka zvuka, Golomb-Rice kodiranje za pohranu predviđenih podataka.
• Datoteke su 40-60% manje od WAV formata, uz vrhunsku kvalitetu zvuka i podršku za metadata tagging.

LPC

• Linearno prediktivno kodiranjе(LPC) se koristi za predviđanje budućih uzoraka zvuka na temelju prethodnih vrijednosti.
• Smanjuje redundantnost podataka prije konačne kompresije.
• Analizira prethodne uzorke signala i računa predviđeni uzorak pomoću linearnog modela: 𝑠𝑛 = 𝑎1 𝑆𝑛−1 + 𝑎2 𝑆𝑛−2 + ⋯ + 𝑎𝑘 𝑆𝑛−𝑘.
• LPC smanjuje količinu podataka i uklanja ponavljajuće obrasce u audio signalu.

Golomb-Rice kodiranje

• Golomb-Rice kodiranje je adaptivno kodiranje celih brojeva, optimizirano za male vrednosti.
• Efikasno za kodiranje LPC reziduala(razlika između stvarnog i predviđenog signala).
• Računanje: podela broja na količnik i ostatak pomoću faktora 𝑚: 𝑥 =𝑞×𝑚+𝑟, 𝑞 se zapisuje u Unary kodu, a 𝑟 u binarnoj reprezentaciji.
• Brže i jednostavnije je od standardnih entropijskih kodiranja, i idealno za audio kompresiju.

Efikasno smanjenje veličine podataka

• Osnovni princip je prepoznavanje i uklanjanje redundantnih podataka, uz potpunu rekonstrukciju nakon dekompresije.
• Tehnike optimizacije uključuju: kodiranje ponavljanja(RLE-eliminacija uzastopnih istih znakova), statističko kodiranje(Huffman i aritmetičko), Lempel-Ziv algoritmi, i prediktivno kodiranje(LPC u FLAC-u i filtriranje u PNG-u).
• Primena: Tekst-> ZIP, RAR, 7-Zip, Slike-> PNG, Audio-> FLAC, Video-> Lossless H.264.

Kompresija sa gubicima

• Tehnika uklanja dio podataka radi bolje kompresije, sa ciljem da se smanji veličina, ali da se zadrži prihvatljiva kvaliteta.
• Osnovna ideja je uklanjanje nevažnih podataka, koristeći psihovizualne i psihoakustične modele bazirano na ograničenjima ljudske percepcije.
• Primenjuje se na zvuk(MP3, AAC) uklanjanjem neslušljivih frekvencija, na slike(JPEG, WebP) uklanjanjem nevidljivih detalja i boja, i na video(H.264, HEVC, AV1) smanjenjem detalja u pokretnim scenama.

Psihovizuelni i psihoakustički modeli

• Kod psihovizuelnog modela čovek manje je osetljiv na fine detalje u tamnim ili svetlim područjima.
• Veća je osetljivost na kontraste i rubove, i nismo svi jednako osetljivi na boje – osetljiviji smo na zelenu nego na plavu.
• JPEG koristi psihovizuelne modele uklanjajući detalje u svetlim i tamnim delovima slike i smanjuje rezoluciju boje, ali čuva kontraste.
• Kod psihoakustičnog modela, čovek manje je osetljiv na vrlo visoke i vrlo niske frekvencije.
• Glasni tonovi maskiraju tiše tonove u blizini i ređe primjećujemo tihe zvukove ako su blizu glasnih tonova.
• MP3 ignoriše tihe zvukove koji su prekriveni glasnijima, i uklanja neslušljive frekvencije iz zvučnog spektra.

Perceptualno kodiranje zvuka

• Perceptualno kodiranje zvuka koriste MP3 i AAC, u kombinaciji sa psihoakustičnim modelima.
• Ključni su koraci analiza frekvencijskog spektra, maskiranje zvukova i alokacija bitrate-a, gde važniji tonovi dobijaju više bitova, i primjena Huffmanovog kodiranja.
• AAC je efikasniji od MP3, uz bolju kvalitetu uz isti bitrate, koristi se u Apple Music, Youtube i modernim streamovima.

Primer gubitka kvaliteta zvuka

• Originalni zvuk(WAV, 44.1 kHz, 16-bit) veličine 50MB(3 minuta), pomoću MP3 128kbps postaje 3MB uz gubitak frekvencije > 16 kHz.
• Korišćenjem AAC 128kbps postaje 2.8MB uz bolji upravljanje složenim zvučnim signalima.

Uklanjanje detalja u slikama (DCT)

• JPEG i WebP kompresiraju slike razdvajanjem slike na blokove i pretvaranjem piksela u frekvencije pomoću diskretne kosinusne transformacije(DCT).
• Visoke frekvencije se uklanjaju, a zatim se vrši kvantisacija i Huffmanovo ili aritmetičko kodiranje.
• WebP nudi bolju kompresiju i podršku za prozirnost, dok je JPEG šire podržan, ali gubi više detalja.

Princip rada DCT

• Diskretna kosinusna transformacija transformiše prostornu domenu(piksela) u frekvencijsku.
• Omogućuje razdvajanje bitnih i manje bitnih informacija, gde frekvencije se mogu smanjiti ili eliminirati kvantisacijom.

Primeri kvalitete slike

• Originalna slika(PNG, 1080p) 2MB, uz JPEG 80% postaje 300KB, uz artefakte, a WebP postaje 250KB, uz bolje očuvanje boja i detalja.

Intra-frame i inter-frame

• Intra-frame kompresija koristi JPEG/DCT metodu za svaki kadar, a inter-frame prepoznaje pokrete i pamte se samo razlike između kadrova.
• MPEG-4 ima najmanji stepen kompresije i koristi se za SD video, H.264 ima srednji i koristi se za Full HD, a H.265 koristi najveći i koristi se za 4K i 8K.
• Video 1080p, 10 minuta, RAW formata(30GB), se kodira u 2GB uz H.264 i 1 GB uz H.265, i H.265 pruža više detalja uz manje prostora.

Kompresija bez gubitaka i gubicima

• Kompresija bez gubitaka(lossless) u potpunosti čuva kvalitetu podataka, omogućuje dekompresiju u izvorni oblik, koristi se za zvuk i slike visoke kvalitete, i ima veću veličinu datoteke.
• Kompresija s gubicima(lossy) znatno smanjuje veličinu podataka, optimizovana je za streaming i pohranu, pogodna za web slike, glazbu i video, uz vidljiv gubitak podataka i artefakte pri višoj kompresiji.

Artefakti kompresije

• Javljaju se kod slika (JPEG, WebP): Blokovni efekti, zamućenje i posterizacija.
• Javljaju se kod zvuka (MP3, AAC): Gubitak visokih frekvencija, metalni tonovi i nestanak tihih detalja.
• Javljaju se kod videa (H.264, H.265): Makroblokovi, gubitak detalja i efekt vodene boje.

Fraktalna kompresija

• Fraktalna kompresija je metoda temeljena na samoponavljajućim uzorcima u slikama.
• Koristi matematičke transformacije(IFS) za rekonstrukciju slike umjesto pohrane piksela, i dekodiranje se generira korištenjem rekurzivnih funkcija.
• Fraktalno komprimirana slika (50 KB), gubi detalja pri povećanju.
• Vrlo brz je postupak dekompresije.

Wavelet transformacija

• Wavelet transformacija je napredna metoda za analizu signala u frekvencijskom području, i zamjenjuje DCT u JPEG2000 i H.265.
• Slika se razlaže na pojedine frekvencije te manje bitne informacije u visokim frekvencijama.
• Na taj način se postižu bolji rezultati pri nižem bitrate-u u odnosu u odnosu na DCT.
• H.265 pruža ~50% uštede u kvaliteti podataka.

Autoenkoderi su neuronske mreže

• Autoenkoderi uče kako komprimirati i rekonstruirati podatke,
• Smanjuju dimenzionalnost bez gubitka važnih informacija.
• Kodiranje pretvara ulazne podatke u latentni prostor, dok dekodiranje rekonstruiše podatke iz komprimirane verzije.

AI u kompresiji slika (VQ-VAE)

• VQ-VAE (Vector Quantized Variational Autoencoder) koriti kvantizaciju vektora za bolju kompresiju.
• Uči najbolje reprezentacije podataka, smanjujući redundanciju.
• Uporabom dubokih konvolucijskih mreža automatski se optimizira enkodiranje i dekodiranje podataka
• Duboke konvolucijske mreže prepoznaju važne detalje slike.

Al poboljšava streaming servise

• Optimizira se bitrate prema vrsti sadržaja (brza akcija vs. statične scene),
• Al modeli predviđaju najbolji balans između veličine i kvalitete.
• Netflix koristi Al za dijagnosticiranje kvalitete videa i dinamičko optimiziranje bitrate-a.
• YouTube AI kodeci smanjuju bitrate bez vidljivog gubitka kvalitete.

AI za predviđanje podataka

• Rekonstrukciju izgubljenih podataka pomoću generativnih modela(GANs, autoenkoderi), i popunjavanje praznina.
• Primjena u industriji je restauracija starih filmova, satelitske snimke, kibernetička sigurnost, popravljanje slika koristeći unutarnje uzorke(Deep Image Prior), i povećanje rezolucije slika(Google Al super-resolution).

Kvantna kompresija

• Kvantna kompresija koristi kvantne mehaničke principe za optimiziranje pohrane i prijenosa podataka.
• Bazira se na superpoziciji i spregnutosti kvantnih stanja.
• Količina informacije kvantificira se pomoću Von Neumannove entropije pomoću formula:
  • 𝑆(𝜌) = −𝑇𝑟(𝜌 log 𝜌)
  • 𝜌 = gustoća matrice (density matrix) koja opisuje kvantno stanje.
  • 𝑇𝑟 = trag matrice(matematička operacija koja sumira vlastite vrijednosti matrice).

Kvantna informacija

• Redefinira teoriju entropije i kompresije iskorištavanjem kvantne korelacije.
• Otvara mnoge moguće buduće primjene kvantnog kompresiranja:
  • Kvantno kodirani podaci.
  • Sigurniju i bržu kvantnu enkripciju podataka.
  • Optimizaciju procesorski zahtjevnih zadataka uz pomoć kvantnh računala.

Vrste kompresije

• Bez gubitaka - očuvanje 100% podataka.
• S gubicima - uklanjanje podataka manje važnih za percepciju.

Ključne metode kompresije

• Statisčičke - Huffmanovo i aritmetičko kodiranje.
• Lempel-Ziv algoritmi.
• Transformacijske - DCT i Wavelet.
• Al umjetna inteligencija, poput fraktalne kompresije.
• I nedavno predstavljena - kvantna kompresija.