Kompresija je privatni slučaj kodiranja, čija je glavna karakteristika da je dobiveni kod manji od izvornog. Proces se temelji na traženju ponavljanja u nizu informacija i očuvanju samo jednog uz broj ponavljanja. Tako, na primjer, ako se slijed pojavljuje u datoteci kao što je "AAAAAA", zauzima 6 bajta, ona će biti spremljena kao "6A", koja zauzima 2 bajta u RLE algoritmu kompresije.
Povijest procesa
Tek u sedamdesetim godinama prošlog stoljeća, s pojavom Interneta i online pohrane, implementirani su potpuni algoritmi kompresije. Huffmanovi kodovi se dinamički generiraju na temelju ulaznih informacija. Ključna razlika između Shannon-Fano kodiranja i Huffmanovog kodiranja je u tome što je u prvom stablu vjerojatnosti izgrađena odozdo prema gore, stvarajući suboptimalni rezultat, au drugom, odozgo prema dolje. Godine 1977. Abraham Lempel i Jacob Zev izdali su svoju inovativnu LZ77 metodu koristeći moderniji rječnik. Godine 1978. isti tim autora objavio je poboljšani algoritam kompresije LZ78. Tko koristi novi rječnik, analizira ulazne podatke i generira statički rječnik, a ne dinamički, kao u 77verzija.
Oblici izvođenja kompresije
Kompresija gubitka trajno uklanja bitove podataka koji su suvišni, nevažni ili neprimjetni. Korisna je za grafiku, audio, video i slike, pri čemu uklanjanje nekih bitova praktično nema vidljiv učinak na prezentaciju sadržaja.
Huffmanov algoritam kompresije
,
,
,
), j
, s
, c
, l
, t
,
, a
01110010
11010101
11111011
00010010
11010101
11110111
)
0xd5
0xFB
0x12
0xd5
0xF7
91)
0xB9
0x80
Svih osam bajta i izvorni tekst bio je 23.
Demonstracija knjižnice LZ77
Onda, kada želi pročitati tekst natrag, zamijenit će svaku instancu (h) s "howtogeek", vraćajući se na izvornu frazu. On demonstrira algoritam kompresije podataka bez gubitaka, budući da su ulazni podaci isti kao primljeni podaci.
Ovo je savršen primjer kada je većina teksta komprimirana s nekoliko znakova. Na primjer, riječ "ovo" bit će kratka, čak i ako se pojavljuje u riječima kao što su "ovo", "njihovo" i "ovo". Uz ponavljajuće riječi možete dobiti ogromne omjere kompresije.Na primjer, tekst s riječju "howtogeek", koji se ponavlja 100 puta veću od tri kilobajta, sa kompresijom će trajati samo 158 bajtova, odnosno 95% "smanjenja".
To je, naravno, prilično ekstreman primjer, ali jasno pokazuje svojstva algoritama kompresije. Općenito, to je 30-40% tekstualnog formata ZIP-a. Algoritam LZ77 primjenjuje se na sve binarne podatke, a ne samo na tekst, iako je potonji lakše komprimirati preko ponavljajućih riječi.
Kompresija videa i zvuka radi sasvim drugačije. Za razliku od teksta koji izvodi algoritme kompresije bez gubitaka, a podaci se neće izgubiti, slike se "smanjuju" gubicima, a što je više%, više je gubitaka. To dovodi do užasnih izgleda JPEG datoteka koje su ljudi nekoliko puta preuzimali, razmjenjivali i snimali. Većina slika, fotografija i drugih pohranjuje popis brojeva, od kojih svaki predstavlja jedan piksel. JPEG ih pohranjuje pomoću algoritma kompresije slike koji se naziva diskretna kosinusna transformacija. On predstavlja skup sinusoidnih valova koji se sastoje od različitog intenziteta. Ova metoda koristi 64 različite jednadžbe, zatim Huffmanovo kodiranje, kako bi dodatno smanjila veličinu datoteke. Sličan algoritam kompresije slike daje strahovito visok stupanj kompresije i smanjuje ga od nekoliko megabajta do nekoliko kilobajta, ovisno o kvaliteti koja je potrebna. Većina fotografija se komprimira radi spremanja vremena preuzimanja, posebno za mobilne korisnikeloš prijenos podataka.
Video djeluje malo drugačije od slike. Obično algoritmi za kompresiju grafičkih informacija koriste ono što se naziva "međudržavna kompresija", koja izračunava promjene između svakog okvira i sprema ih. Na primjer, ako postoji relativno mirna slika koja traje nekoliko sekundi videozapisa, bit će "smanjena" na jednu. Interkom kompresija omogućuje digitalni TV i web video. Bez nje, video je težio stotine gigabajta, što je više od prosječnog tvrdog diska 2005. godine. Komprimiranje zvuka jako sliči komprimiranju teksta i slika. Ako JPEG briše detalje slike koja je nevidljiva ljudskom oku, kompresija zvuka čini isto za zvukove. MP3 koristi bitrate, u rasponu od donjih 48 i 96 kbit /s (donja granica) do 128 i 240 kbps (prilično dobra) do 320 kbps (visokokvalitetni audio), a razliku možete čuti samo s vrlo dobrim slušalicama. Postoje audio kodeci bez gubitaka, od kojih je glavni FLAC i koristi LZ77 kodiranje za prijenos zvuka bez gubitaka.
Raspon knjižnica za tekst uglavnom se sastoji od algoritma kompresije podataka bez gubitaka, s iznimkom ekstremnih slučajeva za podatke s pomičnim zarezom. Većina kodeka kompresora uključuje "smanjenje" LZ77 Huffman i Arithmetic kodiranja. Koriste se nakon drugih alata za stiskanje još nekoliko postotaka kompresije.
Pokrenite vrijednosti kodirane kao znak nakon čega slijedi duljina niza. Možete ispravno vratiti izlazpotok. Ako je duljina serije
To je, naravno, prilično ekstreman primjer, ali jasno pokazuje svojstva algoritama kompresije. Općenito, to je 30-40% tekstualnog formata ZIP-a. Algoritam LZ77 primjenjuje se na sve binarne podatke, a ne samo na tekst, iako je potonji lakše komprimirati preko ponavljajućih riječi.
Pretvorba diskretne kosinusne slike
Video djeluje malo drugačije od slike. Obično algoritmi za kompresiju grafičkih informacija koriste ono što se naziva "međudržavna kompresija", koja izračunava promjene između svakog okvira i sprema ih. Na primjer, ako postoji relativno mirna slika koja traje nekoliko sekundi videozapisa, bit će "smanjena" na jednu. Interkom kompresija omogućuje digitalni TV i web video. Bez nje, video je težio stotine gigabajta, što je više od prosječnog tvrdog diska 2005. godine. Komprimiranje zvuka jako sliči komprimiranju teksta i slika. Ako JPEG briše detalje slike koja je nevidljiva ljudskom oku, kompresija zvuka čini isto za zvukove. MP3 koristi bitrate, u rasponu od donjih 48 i 96 kbit /s (donja granica) do 128 i 240 kbps (prilično dobra) do 320 kbps (visokokvalitetni audio), a razliku možete čuti samo s vrlo dobrim slušalicama. Postoje audio kodeci bez gubitaka, od kojih je glavni FLAC i koristi LZ77 kodiranje za prijenos zvuka bez gubitaka.