Predavanje broj 4. Kompresija informacija

Principi kompresije informacija

Svrha kompresije podataka je osigurati kompaktan prikaz podataka koje generira izvor za ekonomičniju pohranu i prijenos putem komunikacijskih kanala.

Pretpostavimo da imamo datoteku veličine 1 (jedan) megabajt. Moramo iz njega dobiti manju datoteku. Ništa komplicirano – pokrenemo arhiver, na primjer, WinZip, i dobijemo, recimo, datoteku od 600 kilobajta. Gdje su nestala preostala 424 kilobajta?

Sažimanje informacija jedan je od načina za njihovo kodiranje. Općenito, kodovi su podijeljeni u tri velike skupine - kompresijski kodovi (učinkoviti kodovi), kodovi za ispravljanje pogrešaka i kriptografski kodovi. Kodovi dizajnirani za komprimiranje informacija podijeljeni su, pak, na kodove bez gubitaka i kodove s gubicima. Kodiranje bez gubitaka podrazumijeva apsolutno točan oporavak podataka nakon dekodiranja i može se koristiti za komprimiranje bilo koje informacije. Kodiranje s gubitkom obično ima mnogo veći omjer kompresije od kodiranja bez gubitaka, ali dopušta neka odstupanja dekodiranih podataka od izvornika.

Vrste kompresije

Sve metode sažimanja informacija mogu se uvjetno podijeliti u dvije velike klase koje se ne preklapaju: kompresiju s gubitak informacija i kompresije nema gubitka informacija.

Kompresija bez gubitka informacija.

Prije svega nas zanimaju ove metode kompresije, jer se koriste pri prijenosu tekstualnih dokumenata i programa, prilikom izdavanja dovršenog rada kupcu ili kod izrade sigurnosnih kopija podataka pohranjenih na računalu.

Metode kompresije ove klase ne mogu dopustiti gubitak informacija, stoga se temelje samo na eliminaciji njihove suvišnosti, a informacija ima redundanciju gotovo uvijek (iako, ako je netko prije nije komprimirao). Da nema viška, ne bi se imalo što komprimirati.

Evo jednostavnog primjera. U ruskom jeziku ima 33 slova, deset brojeva i desetak interpunkcijskih znakova i drugih posebnih znakova. Za tekst koji je napisan samo velikim ruskim slovima(kao u telegramima i radiogramima) bilo bi dovoljno šezdeset različitih vrijednosti. Međutim, svaki znak obično je kodiran bajtom koji sadrži 8 bitova i može izraziti 256 različitih kodova. To je prvi razlog za višak. Za naš "telegrafski" tekst bilo bi dovoljno šest bitova po znaku.

Evo još jednog primjera. Međunarodno kodiranje znakova ASCII za kodiranje bilo kojeg znaka dodjeljuje se isti broj bitova (8), dok svi odavno dobro znaju da ima smisla najčešće znakove kodirati s manje znakova. Tako, na primjer, u "Morseovom kodu" slova "E" i "T", koja se često nalaze, kodirana su jednim znakom (odnosno, točkom i crticom). I takva rijetka slova kao što su "U" (- -) i "C" (- -) kodirana su s četiri znaka. Neučinkovito kodiranje drugi je razlog redundancije. Programi koji vrše kompresiju informacija mogu unijeti vlastito kodiranje (različito za različite datoteke) i komprimiranoj datoteci dodijeliti tablicu (rječnik) iz koje program za raspakiranje saznaje kako su određeni znakovi ili njihove grupe kodirani u ovoj datoteci. Algoritmi koji se temelje na transkodiranju informacija nazivaju se Huffmanovi algoritmi.

Prisutnost fragmenata koji se ponavljaju treći je razlog redundancije. To je rijetko u tekstovima, ali u tablicama i grafikama, ponavljanje kodova je uobičajeno. Tako, na primjer, ako se broj 0 ponovi dvadeset puta zaredom, onda nema smisla staviti dvadeset nula bajtova. Umjesto toga stavljaju jednu nulu i koeficijent 20. Takvi algoritmi koji se temelje na otkrivanju ponavljanja nazivaju se metodeRLE (Trčanje Duljina Kodiranje).

Grafičke se ilustracije posebno ističu velikim ponavljajućim nizovima istih bajtova, ali ne fotografskih (puno je šuma i susjedne točke se značajno razlikuju po parametrima), već onih koje umjetnici slikaju "glatkim" bojom, kao u animiranim filmovima .

Kompresija s gubitkom.

Kompresija s gubitkom znači da nakon raspakiranja komprimirane arhive dobivamo dokument koji se malo razlikuje od onog koji je bio na samom početku. Podrazumijeva se da što je veći omjer kompresije, veći je gubitak, i obrnuto.

Naravno, takvi algoritmi nisu primjenjivi za tekstualne dokumente, tablice baze podataka, a posebno za programe. Mala izobličenja u jednostavnom neformatiranom tekstu još se mogu nekako preživjeti, ali izobličenje barem jednog bita u programu učinit će ga apsolutno neoperativnim.

Istodobno, postoje materijali u kojima vrijedi žrtvovati nekoliko postotaka informacija kako bi se kompresija udeseterostručila. To uključuje fotografske ilustracije, video zapise i glazbene skladbe. Gubitak informacija tijekom kompresije i naknadnog raspakiranja u takvim materijalima percipira se kao pojava neke dodatne "buke". No, budući da je pri stvaranju ovih materijala još uvijek prisutan neki "šum", njegovo malo povećanje ne izgleda uvijek kritično, a dobitak u veličini datoteka je ogroman (10-15 puta za glazbu, 20-30 puta za foto i video materijale).

Algoritmi kompresije s gubitkom uključuju tako dobro poznate algoritme kao što su JPEG i MPEG. JPEG algoritam se koristi za komprimiranje fotografskih slika. Grafičke datoteke komprimirane ovom metodom imaju JPG ekstenziju. MPEG algoritmi se koriste za komprimiranje videa i glazbe. Ove datoteke mogu imati različite ekstenzije, ovisno o konkretnom programu, ali najpoznatiji su .MPG za video i .MP3 za glazbu.

Algoritmi kompresije s gubitkom koriste se samo za korisničke aplikacije. To znači, na primjer, ako se fotografija šalje na gledanje, a glazba za reprodukciju, onda se mogu koristiti slični algoritmi. Ako se prenose na daljnju obradu, na primjer, za uređivanje, tada gubitak podataka u izvornom materijalu nije prihvatljiv.

Količina dopuštenog gubitka kompresije obično se može kontrolirati. To vam omogućuje eksperimentiranje i postizanje optimalnog omjera veličine i kvalitete. U fotografskim ilustracijama namijenjenim prikazu na ekranu gubitak od 5% informacija obično nije kritičan, au nekim slučajevima može se tolerirati 20-25%.

Algoritmi kompresije bez gubitaka

Shannon-Fano kod

Za daljnje razmišljanje, bit će zgodno zamisliti našu izvornu datoteku s tekstom kao izvor znakova koji se pojavljuju jedan po jedan na njegovom izlazu. Ne znamo unaprijed koji će znak biti sljedeći, ali znamo da će se slovo "a" pojaviti s vjerojatnošću p1, slovo "b" s vjerojatnošću p2 i tako dalje.

U najjednostavnijem slučaju, smatrat ćemo da su svi likovi teksta neovisni jedan o drugom, t.j. vjerojatnost pojavljivanja sljedećeg simbola ne ovisi o vrijednosti prethodnog simbola. Naravno, to nije slučaj za smisleni tekst, ali sada razmatramo vrlo pojednostavljenu situaciju. U ovom slučaju, izjava "simbol nosi što više informacija, to je manja vjerojatnost njegovog pojavljivanja".

Zamislimo tekst čija se abeceda sastoji od samo 16 slova: A, B, C, D, D, E, F, Z, I, K, L, M, N, O, P, R. Svako od njih znakovi se mogu kodirati sa samo 4 bita: od 0000 do 1111. Sada zamislite da su vjerojatnosti pojavljivanja ovih znakova raspoređene na sljedeći način:

Zbroj tih vjerojatnosti je, naravno, jedan. Podijelimo ove simbole u dvije skupine tako da ukupna vjerojatnost simbola svake skupine bude ~ 0,5 (sl.). U našem primjeru, to će biti grupe likovi A-B i gosp. Krugovi na slici, koji označavaju skupine simbola, nazivaju se čvorovi ili čvorovi, a sama konstrukcija tih čvorova naziva se binarno stablo (B-stablo). Dodijelimo svakom čvoru vlastiti kod, označavajući jedan čvor brojem 0, a drugi brojem 1.

Podijelimo opet prvu skupinu (AB) u dvije podskupine tako da njihove ukupne vjerojatnosti budu što bliže jedna drugoj. Dodajmo broj 0 šifri prve podskupine, a broj 1 šifri druge.

Ponavljat ćemo ovu operaciju dok ne ostane po jedan simbol na svakom vrhu našeg "stabla". Kompletno stablo za našu abecedu imat će 31 čvor.

Kodovi znakova (krajnji desni čvorovi stabla) imaju kodove nejednake duljine. Dakle, slovo A, koje ima vjerojatnost p = 0,2 za naš imaginarni tekst, kodirano je sa samo dva bita, a slovo P (nije prikazano na slici), koje ima vjerojatnost p = 0,013, kodirano je sa šest-bitna kombinacija.

Dakle, princip je očigledan - znakovi koji se često pojavljuju su kodirani s manje bitova, rijetki - s više. Kao rezultat, prosječan broj bitova po znaku bit će

gdje je ni broj bitova koji kodiraju i-ti simbol, pi je vjerojatnost i-tog simbola.

Huffmanov kod.

Huffmanov algoritam graciozno implementira opću ideju entropijskog kodiranja koristeći skupove prefiksa i radi na sljedeći način:

1. Napišite redom sve simbole abecede uzlaznim ili silaznim redoslijedom vjerojatnosti njihovog pojavljivanja u tekstu.

2. Uzastopno kombinirajte dva simbola s najmanjom vjerojatnošću pojavljivanja u novom složenom simbolu, čija se vjerojatnost pretpostavlja jednakom zbroju vjerojatnosti njegovih sastavnih simbola. Na kraju ćemo izgraditi stablo čiji svaki čvor ima ukupnu vjerojatnost svih čvorova ispod njega.

3. Pratite put do svakog lista stabla, označavajući smjer do svakog čvora (na primjer, desno - 1, lijevo - 0). Rezultirajući slijed daje kodnu riječ koja odgovara svakom znaku (sl.).

Napravimo stablo koda za poruku sa sljedećom abecedom:

Nedostaci metoda

Najveća poteškoća s kodovima, kao što sugerira prethodna rasprava, je potreba da se imaju tablice vjerojatnosti za svaku vrstu podataka koji se komprimiraju. To nije problem ako se zna da je engleski ili ruski tekst komprimiran; jednostavno dajemo koderu i dekoderu odgovarajuće stablo koda za engleski ili ruski tekst. U općem slučaju, kada je vjerojatnost simbola za ulazne podatke nepoznata, statični Huffmanovi kodovi rade neučinkovito.

Rješenje ovog problema je statistička analiza kodiranih podataka, koja se izvodi tijekom prvog prijelaza preko podataka, te kompilacija kodnog stabla na temelju toga. U ovom slučaju, stvarno kodiranje se izvodi u drugom prolazu.

Još jedan nedostatak kodova je taj što minimalna duljina kodne riječi za njih ne može biti manja od jedan, dok entropija poruke može biti i 0,1 i 0,01 bita po slovu. U tom slučaju kod postaje značajno suvišan. Problem se rješava primjenom algoritma na blokove simbola, no tada se postupak kodiranja/dekodiranja komplicira i kodno stablo se značajno širi, koje se u konačnici mora pohraniti zajedno s kodom.

Ovi kodovi ne uzimaju u obzir odnose između znakova, koji su prisutni u gotovo svakom tekstu. Na primjer, ako je tekst na Engleski jezik naiđemo na slovo q, tada možemo pouzdano reći da će iza njega doći slovo u.

Run Length Encoding (RLE) jedan je od najstarijih i najjednostavnijih algoritama za arhiviranje. Kompresija u RLE-u se događa zamjenom nizova identičnih bajtova parovima protuvrijednosti. (“Crveno, crveno, ..., crveno” je napisano kao “N crveno”).

Jedna od implementacija algoritma je sljedeća: traže najmanji bajt, nazivaju ga prefiksom i zamjenjuju nizove identičnih znakova trojkama "prefiks, brojač, vrijednost". Ako se ovaj bajt pojavljuje u izvornoj datoteci jednom ili dvaput zaredom, tada se zamjenjuje parom "prefiks, 1" ili "prefix, 2". Postoji jedan neiskorišteni par "prefiks, 0" koji se može koristiti kao znak kraja pakiranih podataka.

Kada kodirate exe datoteke, možete pretraživati ​​i pakirati sekvence oblika AxAyAzAwAt ..., koje se često nalaze u resursima (nizovi kodirani u Unicodeu)

Pozitivni aspekti algoritma uključuju činjenicu da ne zahtijeva dodatnu memoriju tijekom rada i da se brzo izvršava. Algoritam se koristi u PCX, TIFF, BMP formatima. Zanimljiva značajka skupnog kodiranja u PCX-u je da se stupanj arhiviranja nekih slika može značajno povećati jednostavnom promjenom redoslijeda boja u paleti slike.

LZW kod (Lempel-Ziv & Welch) daleko je jedan od najčešćih kodova za kompresiju bez gubitaka. Uz pomoć LZW-koda provodi se kompresija u takvim grafičkim formatima kao što su TIFF i GIF; uz pomoć LZW modifikacija, mnogi univerzalni arhivari obavljaju svoje funkcije. Rad algoritma temelji se na traženju u ulaznoj datoteci ponovljenih nizova znakova koji su kodirani kombinacijama duljine od 8 do 12 bita. Stoga je ovaj algoritam najučinkovitiji na tekstualnim datotekama i grafičkim datotekama u kojima postoje velika jednobojna područja ili ponavljajući nizovi piksela.

Odsutnost gubitka informacija tijekom LZW kodiranja dovela je do široke upotrebe TIFF formata koji se temelji na njemu. Ovaj format ne nameće nikakva ograničenja na veličinu i dubinu boje slike i široko se koristi, na primjer, u tiskarskoj industriji. Drugi format koji se temelji na LZW-u - GIF - je primitivniji - omogućuje vam pohranjivanje slika s dubinom boje ne većom od 8 bita / piksel. Na početku GIF datoteke nalazi se paleta - tablica koja uspostavlja korespondenciju između indeksa boja - broja u rasponu od 0 do 255 i prave, 24-bitne vrijednosti boje.

Algoritmi kompresije s gubitkom

JPEG algoritam je razvila grupa tvrtki pod nazivom Joint Photographic Experts Group. Cilj projekta bio je stvoriti visoko učinkovit standard kompresije za crno-bijele i slike u boji, a taj cilj su programeri i postigli. Trenutno se JPEG široko koristi tamo gdje je potreban visoki omjer kompresije - na primjer, na Internetu.

Za razliku od LZW-a, JPEG kodiranje je s gubicima. Sam algoritam kodiranja temelji se na vrlo složenoj matematici, ali općenito se može opisati na sljedeći način: slika se dijeli na kvadrate od 8 * 8 piksela, a zatim se svaki kvadrat pretvara u sekvencijalni lanac od 64 piksela. Nadalje, svaki takav lanac je podvrgnut takozvanoj DCT-transformaciji, koja je jedna od varijanti diskretne Fourierove transformacije. Sastoji se u činjenici da se ulazni slijed piksela može predstaviti kao zbroj sinusoidnih i kosinusnih komponenti s više frekvencija (tzv. harmonici). U ovom slučaju trebamo znati samo amplitude ovih komponenti kako bismo rekonstruirali ulazni niz s dovoljnim stupnjem točnosti. Što više harmonijskih komponenti poznajemo, manja će biti razlika između izvorne i komprimirane slike. Većina JPEG kodera omogućuje podešavanje stupnja kompresije. To se postiže na vrlo jednostavan način: što je veći omjer kompresije postavljen, to će svaki blok od 64 piksela predstavljati manje harmonika.

Naravno, jača strana ove vrste kodiranja je visok omjer kompresije uz zadržavanje izvorne dubine boje. Upravo je to svojstvo dovelo do njegove široke upotrebe na Internetu, gdje je smanjenje veličine datoteka od iznimne važnosti, u multimedijskim enciklopedijama, gdje je potrebno pohraniti najveću moguću količinu grafike u ograničenom iznosu.

Negativno svojstvo ovog formata je da degradira kvalitetu slike, koja se ni na koji način ne može ukloniti. Upravo ta tužna činjenica ne dopušta njegovu primjenu u tiskarskoj industriji, gdje je kvaliteta na prvom mjestu.

Međutim, JPEG format nije granica izvrsnosti u nastojanju da se smanji veličina konačne datoteke. U posljednje vrijeme provode se intenzivna istraživanja u području tzv. wavelet transformacije (ili burst transformacije). Na temelju najsloženijih matematičkih principa, wavelet koderi omogućuju vam da dobijete veću kompresiju od JPEG-a, uz manji gubitak informacija. Unatoč složenosti matematičke wavelet transformacije, u softverskoj je implementaciji jednostavnija od JPEG-a. Iako su algoritmi za kompresiju valova još uvijek u upotrebi početno stanje razvoja, imaju veliku budućnost.

Fraktalna kompresija

Fraktalna kompresija slike je algoritam sažimanja slike s gubicima koji se temelji na primjeni iterativnih funkcijskih sustava (IFS, obično afine transformacije) na slike. Ovaj algoritam poznat je po tome što u nekim slučajevima omogućuje dobivanje vrlo visokih omjera kompresije (najbolji primjeri su do 1000 puta s prihvatljivom vizualnom kvalitetom) za stvarne fotografije prirodnih objekata, što u principu nije dostupno za druge algoritme kompresije slike. . Zbog teške situacije s patentiranjem algoritam nije bio široko korišten.

Fraktalno arhiviranje temelji se na činjenici da se pomoću koeficijenata sustava iteriranih funkcija slika prikazuje u kompaktnijem obliku. Prije nego što pogledamo proces arhiviranja, pogledajmo kako IFS gradi sliku.

Strogo govoreći, IFS je skup trodimenzionalnih afinih transformacija koje pretvaraju jednu sliku u drugu. Točke u trodimenzionalnom prostoru (x koordinata, y koordinata, svjetlina) se transformiraju.

Osnova metode fraktalnog kodiranja je detekcija sebi sličnih područja na slici. Mogućnost primjene teorije sustava iterativnih funkcija (IFS) na problem kompresije slike prvi su istražili Michael Barnsley i Alan Sloan. Svoju ideju patentirali su 1990. i 1991. godine. Jacquin je uveo fraktalnu metodu kodiranja koja koristi sustav blokova podslike domene i raspona, blokova kvadratnog oblika koji pokrivaju cijelu sliku. Ovaj pristup postao je temelj za većinu fraktalnih metoda kodiranja koje se danas koriste. Pročistili su ga Yuval Fisher i brojni drugi istraživači.

Ova metoda dijeli sliku u skup podslika raspona koji se ne preklapa i definira skup podslika domene koji se preklapa. Za svaki blok ranga, algoritam kodiranja pronalazi najprikladniji blok domene i afinu transformaciju koja ovaj blok domene prevodi u zadani blok ranga. Struktura slike je mapirana u sustav rang blokova, blokova domene i transformacija.

Ideja je sljedeća: pretpostavimo da je originalna slika fiksna točka neke karte kontrakcije. Tada, umjesto same slike, možete nekako zapamtiti ovo mapiranje, a da biste ga vratili, dovoljno je više puta primijeniti ovo mapiranje na bilo koju početnu sliku.

Prema Banachovu teoremu, takve iteracije uvijek vode do fiksne točke, odnosno do izvorne slike. U praksi, cijela poteškoća leži u pronalaženju najprikladnijeg mapiranja kompresije iz slike i u njenom kompaktnom pohranjivanju. Tipično, algoritmi za pretraživanje prikaza (tj. algoritmi kompresije) su uglavnom iscrpni i računski intenzivni. Istodobno, algoritmi oporavka su prilično učinkoviti i brzi.

Ukratko, metoda koju je predložio Barnsley može se opisati na sljedeći način. Slika je kodirana s nekoliko jednostavnih transformacija (u našem slučaju afine), odnosno određena je koeficijentima tih transformacija (u našem slučaju A, B, C, D, E, F).

Na primjer, slika Kochove krivulje može se kodirati s četiri afine transformacije, jedinstveno ćemo je definirati koristeći samo 24 koeficijenta.

Kao rezultat toga, točka će nužno otići negdje unutar crnog područja na izvornoj slici. Nakon što smo ovu operaciju izvršili mnogo puta, popunit ćemo sav crni prostor i na taj način vratiti sliku.

Najpoznatije su dvije IFS slike: Sierpinski trokut i Barnsley Fern. Prvi je dan s tri, a drugi s pet afinih transformacija (ili, u našoj terminologiji, lećama). Svaku transformaciju postavljaju doslovno pročitani bajtovi, dok slika izgrađena uz njihovu pomoć može zauzeti nekoliko megabajta.

Postaje jasno kako arhiver radi i zašto je potrebno toliko vremena. Zapravo, fraktalna kompresija je potraga za sebi sličnim područjima na slici i definiranje parametara afine transformacije za njih.

U najgorem slučaju, ako se ne primjenjuje algoritam optimizacije, bit će potrebno nabrajanje i usporedba svih mogućih fragmenata slike različitih veličina. Čak i za male slike, uzimajući u obzir diskretnost, dobivamo astronomski broj opcija koje treba pretraživati. Čak i oštro sužavanje klasa transformacije, na primjer, skaliranjem samo određeni broj puta, neće nam omogućiti postizanje prihvatljivog vremena. Osim toga, gubi se kvaliteta slike. Velika većina istraživanja u području fraktalne kompresije sada je usmjerena na smanjenje vremena arhiviranja potrebnog za dobivanje slike visoke kvalitete.

Za algoritam fraktalne kompresije, kao i za druge algoritme kompresije s gubicima, vrlo su važni mehanizmi pomoću kojih će biti moguće prilagoditi omjer kompresije i omjer gubitaka. Do danas je razvijen prilično velik skup takvih metoda. Prvo, možete ograničiti broj konverzija, svjesno osiguravajući da omjer kompresije nije niži od fiksne vrijednosti. Drugo, moguće je zahtijevati da u situaciji kada je razlika između obrađenog fragmenta i njegove najbolje aproksimacije veća od određene granične vrijednosti, ovaj fragment mora biti zdrobljen (za njega je potrebno instalirati nekoliko leća). Treće, možete zabraniti cijepanje fragmenata manjih od, recimo, četiri točke. Promjenom graničnih vrijednosti i prioriteta ovih uvjeta, možete vrlo fleksibilno kontrolirati omjer kompresije slike: od podudaranja bita do bita do bilo kojeg omjera kompresije.

Usporedba s JPEG-om

Danas je najčešći algoritam za arhiviranje grafike JPEG. Usporedimo to s fraktalnom kompresijom.

Prvo, imajte na umu da oba algoritma rade na 8-bitnim (sivim tonovima) i 24-bitnim slikama u boji. Oba su algoritmi kompresije s gubitkom i pružaju slične omjere arhiviranja. I fraktalni algoritam i JPEG imaju mogućnost povećanja omjera kompresije povećanjem gubitka. Štoviše, oba se algoritma vrlo dobro paraleliziraju.

Razlike počinju kada uzmemo u obzir vrijeme koje je potrebno algoritmima za komprimiranje / raspakivanje. Dakle, fraktalni algoritam komprimira stotine, pa čak i tisuće puta dulje od JPEG-a. S druge strane, raspakiranje slike bit će 5-10 puta brže. Stoga, ako će se slika komprimirati samo jednom, ali se prenositi preko mreže i raspakirati mnogo puta, tada je isplativije koristiti fraktalni algoritam.

JPEG koristi dekompoziciju slike u kosinusne funkcije, pa se gubitak u njoj (čak i uz zadani minimalni gubitak) pojavljuje u valovima i oreolima na granici oštrih prijelaza boja. Upravo zbog tog efekta ne vole ga koristiti prilikom komprimiranja slika koje su pripremljene za visokokvalitetni ispis: tamo taj efekt može postati vrlo uočljiv.

Fraktalni algoritam eliminira ovaj nedostatak. Štoviše, kada ispisujete sliku, svaki put morate izvesti operaciju skaliranja, budući da raster (ili linija) uređaja za ispis ne odgovara rasteru slike. Tijekom pretvorbe može se pojaviti i nekoliko neugodnih učinaka, koji se mogu riješiti programskim skaliranjem slike (kod jeftinih uređaja za ispis kao što su konvencionalni laserski i inkjet pisači) ili opremanjem uređaja za ispis vlastitim procesorom, tvrdim diskom i skup programa za obradu slike (za skupe strojeve za postavljanje fotografija). Kao što možete pretpostaviti, kada koristite fraktalni algoritam, takvih problema praktički nema.

Pomicanje JPEG-a fraktalnim algoritmom u širokoj upotrebi neće se dogoditi uskoro (barem zbog male brzine arhiviranja potonjeg), ali u području multimedijskih aplikacija, u računalne igrice njegova uporaba je potpuno opravdana.

ARHIVATORI

Kompresija informacija Je li proces transformacije informacija pohranjenih u datoteci smanjenjem redundantnosti podataka. Svrha ovog procesa je smanjiti količinu zauzetih podataka.

Arhivska datoteka Je li posebno kreirana datoteka koja sadrži jednu ili više komprimiranih datoteka.

Omjer kompresije: K c = V c / V o * 100%

K c- omjer kompresije, V c- veličina komprimirane datoteke, V o- izvorna veličina datoteke.

Omjer kompresije ovisi o:

1) korišteni program - arhivar,

2) metoda kompresije,

3) vrstu izvorne datoteke: tekst, grafika, video, zvuk itd.

Programi koji pakiraju i raspakiraju datoteke nazivaju se arhivisti. Najčešći su: ARJ, ZIP, RAR. Ekstenzija arhivskih datoteka podudara se s imenom arhivera koji je korišten za njihovu izradu.

Arhiveri vam omogućuju stvaranje samoraspakujućih arhivskih datoteka, t.j. da biste ih raspakirali, ne morate pokretati program za arhiviranje, jer oni sami sadrže program za raspakiranje. Te se arhive nazivaju SFX arhive
(Samoizvlačenje). Ekstenzija takvih datoteka je * .EXE.

Principi kompresije informacija

U bilo kojem tekstu postoje znakovi koji se ponavljaju. Moguće je odrediti jedan znak i broj ponavljanja. Učinkovitost ovog algoritma je još veća kada se primjenjuje na grafičke datoteke. Ako pogledate u monitor, možete vidjeti puno ponavljajućih točaka iste boje. Format grafičke datoteke PCX temelji se na ovom principu kompresije informacija. Moderni arhivisti razlikuju ne samo ponavljajuće simbole, već i lance simbola, pojedinačne riječi.

Ako tekst ne koristi sve znakove PC abecede, za njihovo kodiranje možete upotrijebiti umjesto jednog bajta, 8 bita, manje broja. Ovaj princip se koristi u telegrafskom stroju, gdje se koriste samo ruska velika slova, dovoljno je 5 bitova za njihovo predstavljanje, što vam omogućuje pisanje tri znaka u dva bajta.

3. Sljedeći princip koristi pravilnost da se slova u tekstu pojavljuju s različitim frekvencijama. Primjerice, u ovom tekstu razmak je najčešći znak, vrlo često se nalaze simboli "a", "i". Ovi zajednički simboli mogu biti predstavljeni kratkom kombinacijom bitova, ostali simboli se mogu kodirati dužim nizom. Na primjer:

4. Fizički, PC dodjeljuje prostor za postavljanje datoteka na disk u klasterima - u blokovima od 4 KB. Manje je nemoguće istaknuti. Na primjer, ako datoteka ima 8193 bajta (8 KB i 1 bajt), fizički će biti 16 KB ili 16384 bajta. Kombiniranje skupine datoteka u jednu omogućuje vam uštedu na tim ostacima. Kada pakirate male datoteke, to je velika ušteda.

Ukupno, kada se datoteke postavljaju zasebno, 6 KB se ne koristi, što je 100% sadržaja datoteka. U drugom slučaju, 2 KB, 33%, ostaje neiskorišteno.

Zip arhiver

Pakiranje pkzip datoteka [ključevi]<имя архива>[putovi datoteke]

ključevi: -rp arhiviranje s poddirektorijima čuvajući strukturu

S OSI zaštita arhivske lozinke (PWD)

A dodajte datoteke u arhivu

M premjestiti datoteke u arhivu

V pregledati sadržaj arhive

Ako se sve datoteke u direktoriju arhiviraju, svakako navedite masku *.*

Raspakiranje pkunzip datoteka [ključevi]<имя архива>[nazivi datoteka]

Prekidači: -d raspakiranje s poddirektorijima koji zadržavaju strukturu

SPWD lozinka za arhivu (PWD)

Arj arhivar

arj<команда>[ključevi]<имя архива>[nazivi datoteka]

Za arj arhiver, jedna datoteka obavlja i operacije raspakiranja i pakiranja.

naredbe: a arhiviranje

e raspakiranje bez očuvanja strukture imenika

x raspakiranje uz očuvanje strukture

l pregledavam sadržaj arhive

m premjestiti datoteke u arhivu

d izbrisati datoteke iz arhive

Prekidači: -r pakiranje s poddirektorijima koji čuvaju strukturu

V dijeljenje arhive na sveske s volumenom volumena (ako je navedeno)

veličina za standardne diskete (360, 720, 1200, 1440) je naznačena u kilobajtima, veličina nestandardnih disketa u bajtovima

V je naznačeno prilikom raspakiranja višeslojne arhive

G OSI lozinka za arhivu ( OSI)

Zip datoteke

Raspakivanje datoteka

© 2015-2019 stranica
Sva prava pripadaju njihovim autorima. Ova stranica ne tvrdi autorstvo, ali omogućuje besplatno korištenje.
Datum izrade stranice: 2016-08-08

GORKOFF 24. veljače 2015. u 11.41 sati

Metode kompresije podataka

• Algoritmi

Moj znanstveni savjetnik i ja pripremamo malu monografiju o obradi slika. Odlučio sam podnijeti poglavlje o algoritmima kompresije slike na sud HabraSociety. Kako je teško uklopiti cijelo poglavlje u okvir jednog posta, odlučio sam ga podijeliti u tri posta:
1. Metode kompresije podataka;
2. Kompresija slika bez gubitaka;
3. Kompresija slika s gubitkom.
U nastavku možete pročitati prvi post u nizu.

Trenutno postoji veliki broj algoritama kompresije bez gubitaka, koji se uvjetno mogu podijeliti u dvije velike skupine:
1. Stream i algoritmi rječnika. Ova grupa uključuje algoritme RLE (run-length encoding), LZ * i druge obitelji. Posebnost svih algoritama ove grupe je da kodiranje ne koristi informacije o frekvencijama znakova u poruci, već informacije o sekvencama na koje smo se ranije susreli.
2. Algoritmi za statističku (entropijsku) kompresiju. Ova skupina algoritama komprimira informacije koristeći neujednačenost frekvencija s kojima se različiti znakovi pojavljuju u poruci. Algoritmi u ovoj skupini uključuju aritmetičke i prefiksne algoritme kodiranja (koristeći Shannon-Fanno, Huffman, sekantna stabla).
Algoritmi transformacije informacija mogu se izdvojiti u zasebnu skupinu. Algoritmi ove skupine ne komprimiraju izravno informacije, ali njihova primjena uvelike pojednostavljuje daljnju kompresiju pomoću algoritama toka, rječnika i entropije.

Streaming i algoritmi rječnika

Kodiranje duljine izvođenja

Run-Length Encoding (RLE) jedan je od najjednostavnijih i najčešćih algoritama kompresije podataka. U ovom algoritmu niz znakova koji se ponavljaju zamjenjuje se znakom i brojem ponavljanja.
Na primjer, niz "AAAAA", koji zahtijeva 5 bajtova za pohranu (pod pretpostavkom da je bajt dodijeljen za pohranjivanje jednog znaka), može se zamijeniti s "5A", koji se sastoji od dva bajta. Očito, što je duži niz ponavljanja, to je ovaj algoritam učinkovitiji.

Glavni nedostatak ovog algoritma je njegova iznimno niska učinkovitost na nizovima znakova koji se ne ponavljaju. Na primjer, ako uzmemo u obzir slijed "ABABAB" (6 bajtova), tada će se nakon primjene RLE algoritma pretvoriti u "1A1B1A1B1A1B" (12 bajtova). Postoje različite metode za rješavanje problema znakova koji se ne ponavljaju.

Najjednostavnija metoda je sljedeća modifikacija: bajt koji kodira broj ponavljanja mora pohraniti informacije ne samo o broju ponavljanja, već io njihovoj prisutnosti. Ako je prvi bit 1, sljedećih 7 bitova označava broj ponavljanja odgovarajućeg znaka, a ako je prvi bit 0, sljedećih 7 bitova označava broj znakova koji se moraju uzeti bez ponavljanja. Ako kodirate "ABABAB" koristeći ovu modifikaciju, dobivamo "-6ABABAB" (7 bajtova). Očito, predložena tehnika može značajno poboljšati učinkovitost RLE algoritma na nizovima znakova koji se ne ponavljaju. Provedba predloženog pristupa prikazana je u Listingu 1:

1. tip
2. funkcija RLEEncode (InMsg: ShortString): TRLEEncodedString;
3. MatchFl: boolean;
4. MatchCount: shortint;
5. EncodedString: TRLEEncodedString;
6. N, i: bajt;
7. početi
8. N: = 0;
9. SetLength (EncodedString, 2 * duljina (InMsg));
10. dok je duljina (InMsg)> = 1 do
11. početi
12. MatchFl: = (duljina (InMsg)> 1) i (InMsg [1] = InMsg [2]);
13. Broj podudaranja: = 1;
14. dok (broj utakmica<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. Broj podudaranja: = Broj podudaranja + 1;
16. ako MatchFl onda
17. početi
18. N: = N + 2;
19. Kodirani niz [N - 2]: = Broj podudaranja + 128;
20. Kodirani niz [N - 1]: = ord (InMsg [1]);
21. drugo
22. početi
23. ako MatchCount<>duljina (InMsg) tada
24. MatchCount: = MatchCount - 1;
25. N: = N + 1 + Broj podudaranja;
26. EncodedString [N - 1 - MatchCount]: = - MatchCount + 128;
27. za i: = 1 do MatchCount do
28. EncodedString [N - 1 - MatchCount + i]: = ord (InMsg [i]);
29. kraj;
30. izbrisati (InMsg, 1, MatchCount);
31. kraj;
32. SetLength (EncodedString, N);
33. RLEEncode: = EncodedString;
34. kraj;

Dekodiranje komprimirane poruke vrlo je jednostavno i svodi se na jedan prijelaz preko komprimirane poruke, pogledajte Listing 2:

1. tip
2. TRLEEncodedString = niz bajtova;
3. funkcija RLEDecode (InMsg: TRLEEncodedString): ShortString;
4. RepeatCount: shortint;
5. i, j: riječ;
6. OutMsg: ShortString;
7. početi
8. OutMsg: = "";
9. i: = 0;
10. dok ja< length(InMsg) do
11. početi
12. Broj ponavljanja: = InMsg [i] - 128;
13. i: = i + 1;
14. ako RepeatCount< 0 then
15. početi
16. Broj ponavljanja: = trbušnjaci (broj ponavljanja);
17. za j: = i do i + Broj ponavljanja - 1 do
18. OutMsg: = OutMsg + chr (InMsg [j]);
19. i: = i + Broj ponavljanja;
20. drugo
21. početi
22. za j: = 1 do RepeatCount do
23. OutMsg: = OutMsg + chr (InMsg [i]);
24. i: = i + 1;
25. kraj;
26. kraj;
27. RLEDecode: = OutMsg;
28. kraj;

Druga metoda za povećanje učinkovitosti RLE algoritma je korištenje algoritama transformacije informacija koji ne komprimiraju podatke izravno, već ih dovode u oblik koji je pogodniji za kompresiju. Kao primjer takvog algoritma razmotrit ćemo BWT permutaciju nazvanu po izumiteljima Burrows-Wheelerova transformacije. Ova permutacija ne mijenja same znakove, već samo mijenja njihov redoslijed u nizu, dok se ponovljeni podnizovi nakon primjene permutacije skupljaju u guste grupe, koje se puno bolje komprimiraju pomoću RLE algoritma. Izravna BWT pretvorba svodi se na slijed sljedećih koraka:
1. Dodavanje posebnog znaka za kraj reda izvornom nizu, koji se ne nalazi nigdje drugdje;
2. Dobivanje svih cikličkih permutacija izvornog niza;
3. Razvrstavanje primljenih redaka leksikografskim redom;
4. Vraćanje posljednjeg stupca rezultirajuće matrice.
Implementacija ovog algoritma prikazana je u Listingu 3.

1. konst
2. EOMsg = "|" ;
3. funkcija BWTEncode (InMsg: ShortString): ShortString;
4. OutMsg: ShortString;
5. LastChar: ANSIChar;
6. N, i: riječ;
7. početi
8. InMsg: = InMsg + EOMsg;
9. N: = duljina (InMsg);
10. ShiftTable [1]: = InMsg;
11. za i: = 2 do N do
12. početi
13. Zadnji znak: = InMsg [N];
14. InMsg: = LastChar + kopija (InMsg, 1, N - 1);
15. ShiftTable [i]: = InMsg;
16. kraj;
17. Sortiraj (ShiftTable);
18. OutMsg: = "";
19. za i: = 1 do N do
20. OutMsg: = OutMsg + ShiftTable [i] [N];
21. BWTEncode: = OutMsg;
22. kraj;

Ovu transformaciju najlakše je objasniti konkretnim primjerom. Uzmimo niz "ANANAS" i dogovorimo se da će znak na kraju reda biti simbol "|". Sve cikličke permutacije ovog retka i rezultat njihova leksikografskog sortiranja prikazani su u tablici. 1.

Oni. rezultat izravne konverzije bit će niz "| NNAAS". Lako je vidjeti da je ovaj niz mnogo bolji od originalnog; komprimiran je RLE algoritmom, budući da sadrži duge nizove ponovljenih slova.
Sličan učinak može se postići i uz pomoć drugih transformacija, ali prednost BWT transformacije je u tome što je reverzibilna, međutim, inverzna transformacija je teža od izravne. Da biste vratili izvorni niz, morate učiniti sljedeće:
Napravite praznu n * n matricu, gdje je n broj znakova u kodiranoj poruci;
Ispunite krajnji desni prazan stupac kodiranom porukom;
Razvrstaj redove tablice leksikografskim redoslijedom;
Ponavljajte korake 2-3 dok ne bude praznih stupaca;
Vratite redak koji završava znakom za kraj reda.

Na prvi pogled, obrnuta transformacija je jednostavna, a jedna od opcija prikazana je u Listingu 4.

1. konst
2. EOMsg = "|" ;
3. funkcija BWTDecode (InMsg: ShortString): ShortString;
4. OutMsg: ShortString;
5. ShiftTable: niz ShortString;
6. N, i, j: riječ;
7. početi
8. OutMsg: = "";
9. N: = duljina (InMsg);
10. SetLength (ShiftTable, N + 1);
11. za i: = 0 do N do
12. ShiftTable [i]: = "";
13. za i: = 1 do N do
14. početi
15. za j: = 1 do N do
16. ShiftTable [j]: = InMsg [j] + ShiftTable [j];
17. Sortiraj (ShiftTable);
18. kraj;
19. za i: = 1 do N do
20. ako je ShiftTable [i] [N] = EOMsg onda
21. OutMsg: = ShiftTable [i];
22. izbrisati (OutMsg, N, 1);
23. BWTDecode: = OutMsg;
24. kraj;

Ali u praksi, učinkovitost ovisi o odabranom algoritmu sortiranja. Trivijalni algoritmi kvadratne složenosti očito će imati izrazito negativan utjecaj na performanse, stoga se preporučuje korištenje učinkovitih algoritama.

Nakon sortiranja tablice dobivene u sedmom koraku, potrebno je iz tablice odabrati redak koji završava znakom "|". Lako je vidjeti da je ovo jedina linija. Da. ispitali smo BWT transformaciju na konkretnom primjeru.

Sumirajući, možemo reći da je glavna prednost RLE grupe algoritama jednostavnost i brzina rada (uključujući brzinu dekodiranja), a glavni nedostatak je neučinkovitost na skupovima znakova koji se ne ponavljaju. Korištenje posebnih permutacija povećava učinkovitost algoritma, ali također uvelike povećava vrijeme rada (osobito dekodiranje).

Kompresija rječnika (LZ algoritmi)

Skupina algoritama rječnika, za razliku od algoritama grupe RLE, ne kodira broj ponavljanja znakova, već prethodno naiđene nizove znakova. Tijekom rada algoritama koji se razmatraju, dinamički se kreira tablica s popisom prethodno naišlih sekvenci i njihovih odgovarajućih kodova. Ova se tablica često naziva rječnikom, a odgovarajuća skupina algoritama naziva se rječnikom.

Najjednostavnija verzija algoritma rječnika opisana je u nastavku:
Inicijalizirati rječnik sa svim znakovima koji se pojavljuju u ulaznom nizu;
Pronađite u rječniku najduži niz (S) koji odgovara početku kodirane poruke;
Izdajte kod pronađenog niza i uklonite ga s početka kodirane poruke;
Ako ne dođe do kraja poruke, pročitajte sljedeći znak i dodajte Sc u rječnik, prijeđite na korak 2. U suprotnom izađite.

Na primjer, novoinicijalizirani rječnik za izraz "CUCKOOKUCHONKUPILACAPUCHON" prikazan je u tablici. 3:

Tijekom procesa kompresije, rječnik će biti nadopunjen sekvencama koje se nalaze u poruci. Proces nadopunjavanja rječnika prikazan je u tablici. 4.

Pri opisu algoritma namjerno je izostavljen opis situacije kada je rječnik popunjen. Ovisno o varijanti algoritma moguće je različito ponašanje: potpuno ili djelomično pražnjenje rječnika, zaustavljanje punjenja rječnika ili proširenje rječnika s odgovarajućim povećanjem širine koda. Svaki od ovih pristupa ima određene nedostatke. Na primjer, zaustavljanje dovršavanja rječnika može dovesti do situacije kada rječnik pohranjuje sekvence koje se javljaju na početku komprimiranog niza, ali se ne pojavljuju kasnije. Istodobno, brisanjem rječnika možete ukloniti česte sekvence. Većina korištenih implementacija, prilikom popunjavanja rječnika, počinje pratiti omjer kompresije, a kada padne ispod određene razine, rječnik se obnavlja. Zatim ćemo razmotriti najjednostavniju implementaciju koja prestaje nadopunjavati rječnik kada je pun.

Prvo, definirajmo rječnik kao zapis koji ne pohranjuje samo pronađene podnizove, već i broj podnizova pohranjenih u rječniku:

Prethodno susrećene podnizove pohranjuju se u niz Words, a njihovi kodovi su brojevi podnizova u ovom nizu.
Također definiramo funkcije za pretraživanje u rječniku i dodavanje u rječnik:

1. konst
2. MAX_DICT_LENGTH = 256;
3. funkcija FindInDict (D: TDictionary; str: ShortString): cijeli broj;
4. r: cijeli broj;
5. i: cijeli broj;
6. fl: boolean;
7. početi
8. r: = - 1;
9. ako je D. Broj riječi> 0 tada
10. početi
11. i: = D. Broj riječi;
12. fl: = lažno;
13. dok (ne fl) i (i> = 0) rade
14. početi
15. i: = i - 1;
16. fl: = D. Riječi [i] = str;
17. kraj;
18. kraj;
19. ako fl onda
20. r: = i;
21. FindInDict: = r;
22. kraj;
23. procedura AddToDict (var D: TDictionary; str: ShortString);
24. početi
25. ako D. Broj riječi< MAX_DICT_LENGTH then
26. početi
27. D. Broj riječi: = D. Broj riječi + 1;
28. SetLength (D. Words, D. WordCount);
29. D. Riječi [D. Broj riječi - 1]: = str;
30. kraj;
31. kraj;

Koristeći ove funkcije, proces kodiranja prema opisanom algoritmu može se implementirati na sljedeći način:

1. funkcija LZWEncode (InMsg: ShortString): TEncodedString;
2. OutMsg: TEncodedString;
3. tmpstr: kratki niz;
4. D: TDictionary;
5. i, N: bajt;
6. početi
7. SetLength (OutMsg, duljina (InMsg));
8. N: = 0;
9. InitDict (D);
10. dok je duljina (InMsg)> 0 do
11. početi
12. tmpstr: = InMsg [1];
13. dok (FindInDict (D, tmpstr)> = 0) i (dužina (InMsg)> dužina (tmpstr)) rade
14. tmpstr: = tmpstr + InMsg [duljina (tmpstr) + 1];
15. ako FindInDict (D, tmpstr)< 0 then
16. izbrisati (tmpstr, duljina (tmpstr), 1);
17. OutMsg [N]: = FindInDict (D, tmpstr);
18. N: = N + 1;
19. izbrisati (InMsg, 1, duljina (tmpstr));
20. ako je duljina (InMsg)> 0 tada
21. AddToDict (D, tmpstr + InMsg [1]);
22. kraj;
23. SetLength (OutMsg, N);
24. LZWEncode: = OutMsg;
25. kraj;

Rezultat kodiranja bit će brojevi riječi u rječniku.
Proces dekodiranja svodi se na izravno dešifriranje kodova, pri čemu nema potrebe za prijenosom stvorenog rječnika, dovoljno je da se tijekom dekodiranja rječnik inicijalizira na isti način kao i tijekom kodiranja. Tada će rječnik biti potpuno vraćen izravno tijekom procesa dekodiranja spajanjem prethodnog podniza i trenutnog simbola.

Jedini problem je moguć u sljedećoj situaciji: kada je potrebno dekodirati podniz koji još nije u rječniku. Lako je vidjeti da je to moguće samo kada je potrebno izdvojiti podniz koji se dodaje u trenutnom koraku. To znači da podniz odgovara cSc uzorku, tj. počinje i završava istim znakom. Štoviše, cS je podniz dodan u prethodnom koraku. Razmatrana situacija je jedina kada je potrebno dekodirati redak koji još nije dodan. Uzimajući u obzir gore navedeno, možemo predložiti sljedeću opciju za dekodiranje komprimiranog niza:

1. funkcija LZWDecode (InMsg: TEncodedString): ShortString;
2. D: TDictionary;
3. OutMsg, tmpstr: ShortString;
4. i: bajt;
5. početi
6. OutMsg: = "";
7. tmpstr: = "";
8. InitDict (D);
9. za i: = 0 do duljine (InMsg) - 1 do
10. početi
11. ako je InMsg [i]> = D. Broj riječi tada
12. tmpstr: = D. Riječi [InMsg [i - 1]] + D. Riječi [InMsg [i - 1]] [1]
13. drugo
14. tmpstr: = D. Riječi [InMsg [i]];
15. OutMsg: = OutMsg + tmpstr;
16. ako je i> 0 onda
17. AddToDict (D, D. Riječi [InMsg [i - 1]] + tmpstr [1]);
18. kraj;
19. LZWDecode: = OutMsg;
20. kraj;

Prednosti algoritama rječnika uključuju njihovu veću učinkovitost kompresije u usporedbi s RLE-om. Ipak, treba shvatiti da je stvarna uporaba ovih algoritama povezana s određenim poteškoćama u implementaciji.

Entropijsko kodiranje

Kodiranje sa Shannon-Fano stablima

Shannon-Fano algoritam jedan je od prvih razvijenih algoritama kompresije. Algoritam se temelji na ideji predstavljanja češćih znakova korištenjem kraćih kodova. Štoviše, kodovi dobiveni korištenjem Shannon-Fano algoritma imaju svojstvo prefiksa: tj. nijedan kod nije početak bilo kojeg drugog koda. Svojstvo prefiksa osigurava da je kodiranje jedan prema jedan. Algoritam za konstruiranje Shannon-Fano kodova prikazan je u nastavku:
1. Podijelite abecedu na dva dijela, ukupne vjerojatnosti simbola u kojima su što bliže jedan drugome.
2. Dodajte 0 prefiksnom kodu prvog dijela znakova, dodajte 1 kodu prefiksa drugog dijela znakova.
3. Za svaki dio (u kojem postoje najmanje dva znaka), rekurzivno izvedite korake 1-3.
Usprkos svojoj usporednoj jednostavnosti, Shannon-Fano algoritam nije bez nedostataka, od kojih je najznačajniji neoptimalno kodiranje. Iako je particioniranje u svakom koraku optimalno, algoritam ne jamči optimalan rezultat u cjelini. Razmotrimo, na primjer, sljedeći redak: "AAABVGDEZH". Odgovarajuće Shannon-Fano stablo i kodovi izvedeni iz njega prikazani su na Sl. 1:

Bez kodiranja, poruka će zauzeti 40 bita (pod pretpostavkom da je svaki znak kodiran s 4 bita), a korištenjem Shannon-Fano algoritma 4 * 2 + 2 + 4 + 4 + 3 + 3 + 3 = 27 bita. Glasnoća poruka smanjena je za 32,5%, ali će se u nastavku pokazati da se ovaj rezultat može značajno poboljšati.

Kodiranje s Huffman Trees

Algoritam Huffmanovog kodiranja, razvijen nekoliko godina nakon Shannon-Fano algoritma, također posjeduje svojstvo prefiksa, a uz to i dokazanu minimalnu redundanciju, upravo zbog toga je iznimno raširen. Za dobivanje Huffmanovih kodova koristi se sljedeći algoritam:
1. Svi simboli abecede predstavljeni su kao slobodni čvorovi, dok je težina čvora proporcionalna učestalosti simbola u poruci;
2. Iz skupa slobodnih čvorova biraju se dva čvora s minimalnom težinom i stvara se novi (roditeljski) čvor s težinom jednakom zbroju težina odabranih čvorova;
3. Odabrani čvorovi se uklanjaju s popisa slobodnih, a roditeljski čvor kreiran na njihovoj osnovi dodaje se na ovaj popis;
4. Koraci 2-3 se ponavljaju sve dok nema više od jednog čvora na popisu slobodnih;
5. Na temelju izgrađenog stabla svakom znaku abecede dodjeljuje se prefiksni kod;
6. Poruka je kodirana primljenim kodovima.

Razmotrimo isti primjer kao u slučaju Shannon-Fano algoritma. Huffmanovo stablo i dobiveni kodovi za poruku "AAABVGDEZH" prikazani su na Sl. 2:

Lako je izračunati da će veličina kodirane poruke biti 26 bita, što je manje nego u Shannon-Fano algoritmu. Zasebno, treba napomenuti da zbog popularnosti Huffmanovog algoritma na ovaj trenutak Postoji mnogo opcija za Huffmanovo kodiranje, uključujući adaptivno kodiranje, koje ne zahtijeva prijenos frekvencija simbola.
Među nedostacima Huffmanovog algoritma značajan dio su problemi povezani sa složenošću implementacije. Upotreba stvarnih varijabli za pohranjivanje frekvencija simbola povezana je s gubitkom preciznosti, stoga se u praksi često koriste cjelobrojne varijable, ali budući da težina roditeljskih čvorova stalno raste, prije ili kasnije dolazi do prelijevanja. Stoga, unatoč jednostavnosti algoritma, njegova ispravna implementacija još uvijek može uzrokovati određene poteškoće, posebno za velike abecede.

Kodiranje sa stablima sekantne funkcije

Kodiranje korištenjem sekantne funkcije je algoritam koji su razvili autori koji omogućuje dobivanje prefiksnih kodova. Algoritam se temelji na ideji izgradnje stabla, čiji svaki čvor sadrži funkciju sekante. Za detaljniji opis algoritma potrebno je uvesti nekoliko definicija.
Riječ je uređeni niz od m bitova (broj m naziva se duljina riječi).
Sekantni literal je par tipa vrijednosti pražnjenje-pražnjenje. Na primjer, literal (4,1) znači da 4 bita riječi moraju biti 1. Ako je literalni uvjet ispunjen, onda se literal smatra istinitim, inače je netočan.
K-bitni sekant je skup od k literala. Ako su svi literali istiniti, tada je i sama sekantna funkcija istinita, inače je lažna.

Stablo je izgrađeno tako da svaki čvor dijeli abecedu na najbliže moguće dijelove. Na sl. 3 prikazuje primjer sekantnog stabla:

Stablo sekantnih funkcija u općem slučaju ne jamči optimalno kodiranje, ali omogućuje iznimno veliku brzinu rada zbog jednostavnosti operacije u čvorovima.

Aritmetičko kodiranje

Aritmetičko kodiranje je jedno od najčešćih učinkovite načine kompresije informacija. Za razliku od Huffmanovog algoritma, aritmetičko kodiranje omogućuje kodiranje poruka s entropijom manjom od 1 bita po simbolu. Jer većina algoritama aritmetičkog kodiranja zaštićena je patentima, u nastavku će biti opisane samo osnovne ideje.
Pretpostavimo da u korištenoj abecedi postoji N simbola a_1, ..., a_N, s frekvencijama p_1, ..., p_N, redom. Tada će algoritam aritmetičkog kodiranja izgledati ovako:
Uzmite kao radni poluinterval)