• tutorial

Davno, dok sam još bio naivan školarac, odjednom sam postao strašno znatiželjan: kako podaci u arhivama na magičan način zauzimaju manje prostora? Vozeći se svojim vjernim dialup-om, počeo sam surfati internetom u potrazi za odgovorom i pronašao mnogo članaka s prilično detaljnim prikazom informacija koje su me zanimale. Ali nijedno od njih tada nije izgledalo lako za razumjeti – popisi kodova su izgledali kao kineska slova, a pokušaji razumijevanja neobične terminologije i raznih formula bili su neuspješni.

Stoga je svrha ovog članka dati ideju o najjednostavnijim algoritmima kompresije onima kojima znanje i iskustvo još ne dopuštaju da odmah razumiju stručnu literaturu ili čiji je profil potpuno daleko od takvih tema. One. Govorit ću o nekim od najjednostavnijih algoritama i navesti primjere njihove implementacije bez kilometarskih lista kodova.

Odmah ću vas upozoriti da neću razmatrati detalje implementacije procesa kodiranja i takve nijanse kao što je efikasna pretraga pojavljivanja niza. Članak će se dotaknuti samo samih algoritama i načina predstavljanja rezultata njihovog rada.

RLE - Kompaktnost uniformnosti

RLE algoritam je vjerovatno najjednostavniji od svih: njegova suština leži u kodiranju ponavljanja. Drugim riječima, uzimamo nizove identičnih elemenata i „slažemo“ ih u parove broj/vrijednost. Na primjer, niz poput "AAAAAAABCCCC" može se konvertirati u unos kao što je "8xA, B, 4xC". Ovo je, općenito, sve što trebate znati o algoritmu.

Primjer implementacije

Pretpostavimo da imamo skup nekih cjelobrojnih koeficijenata koji mogu imati vrijednosti od 0 do 255. Logično, došli smo do zaključka da je razumno pohraniti ovaj skup kao niz bajtova:
unsigned char podaci = ( 0, 0, 0, 0, 0, 0, 4, 2, 0, 4, 4, 4, 4, 4, 4, 4, 80, 80, 80, 80, 0, 2, 2 , 2, 2, 255, 255, 255, 255, 255, 0, 0);

Mnogima će biti mnogo poznatije vidjeti ove podatke kao heksadecimalni dump:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF 00 00

Razmišljajući, odlučili smo da bi bilo dobro nekako komprimirati takve setove kako bismo uštedjeli prostor. Da bismo to učinili, analizirali smo ih i identificirali obrazac: vrlo često postoje podsekvence koje se sastoje od istih elemenata. Naravno, RLE je savršen za ovo!

Kodiramo naše podatke koristeći novostečeno znanje: 6x0, 4, 2, 0, 7x4, 4x80, 0, 4x2, 5x255, 2x0.

Vrijeme je da nekako predstavimo naš rezultat na kompjuterski prilagođen način. Da bismo to učinili, u toku podataka moramo nekako odvojiti pojedinačne bajtove od kodiranih stringova. Budući da naši podaci koriste cijeli raspon vrijednosti bajta, neće biti moguće jednostavno dodijeliti bilo koji raspon vrijednosti ​​​za naše svrhe.

Postoje najmanje dva izlaza iz ove situacije:

1. Kao indikator komprimovanog lanca, izaberite jednu vrednost bajta, a u slučaju kolizije sa stvarnim podacima, pobegnite od njih. Na primjer, ako koristimo vrijednost 255 za “zvanične” svrhe, onda kada se ova vrijednost naiđe u ulaznim podacima, morat ćemo napisati “255, 255” i koristiti maksimalno 254 iza indikatora.
2. Strukturirajte kodirane podatke, ukazujući na broj ne samo ponovljenih, već i narednih pojedinačnih elemenata. Tada ćemo unaprijed znati gdje su koji podaci.

Prva metoda u našem slučaju se ne čini efikasnom, pa ćemo, možda, pribjeći drugom.

Dakle, sada imamo dvije vrste sekvenci: nizove pojedinačnih elemenata (poput "4, 2, 0") i nizove identičnih elemenata (kao "0, 0, 0, 0, 0, 0"). Dodijelimo jedan bit u "servisnim" bajtovima za tip sekvence: 0 - pojedinačni elementi, 1 - identični. Uzmite za ovo, recimo, najznačajniji dio bajta.

U preostalih 7 bitova pohranit ćemo dužine sekvenci, tj. maksimalna dužina kodirane sekvence je 127 bajtova. Mogli bismo dodijeliti, recimo, dva bajta za potrebe servisa, ali u našem slučaju su tako dugi nizovi izuzetno rijetki, pa ih je lakše i ekonomičnije jednostavno razbiti na kraće.

Ispostavilo se da ćemo u izlaznom toku prvo napisati dužinu niza, a zatim ili jednu ponovljena vrijednost, ili lanac neponavljajućih elemenata određene dužine.

Prva stvar koja bi vam trebala upasti u oči je da u ovoj situaciji imamo nekoliko neiskorišćenih vrijednosti. Ne mogu postojati sekvence nulte dužine, tako da možemo povećati maksimalnu dužinu na 128 bajtova oduzimanjem jednog od dužine prilikom kodiranja i dodavanjem prilikom dekodiranja. Dakle, možemo kodirati dužine od 1 do 128 umjesto dužine od 0 do 127.

Druga stvar koju treba napomenuti je da ne postoje nizovi identičnih elemenata jedinične dužine. Stoga ćemo prilikom kodiranja od dužine takvih sekvenci oduzeti još jednu, čime ćemo povećati njihovu maksimalnu dužinu na 129 (maksimalna dužina lanca pojedinačnih elemenata je i dalje 128). One. lanci identičnih elemenata mogu imati dužinu od 2 do 129.

Hajdemo ponovo da kodiramo naše podatke, ali sada u obliku razumljivom računaru. Uslužne bajtove ćemo napisati kao , gdje je T tip sekvence, a L dužina. Odmah ćemo uzeti u obzir da dužine zapisujemo u modifikovanom obliku: pri T=0 oduzimamo jedan od L, pri T=1 - dva.

0, , 4, 2, 0, , 4, , 80, , 0, , 2, , 255, , 0

Pokušajmo dekodirati naš rezultat:

• . T=1, tada će se sljedeći bajt ponoviti L+2 (4+2) puta: 0, 0, 0, 0, 0, 0.
• . T=0, pa samo pročitajte L+1 (2+1) bajtova: 4, 2, 0.
• . T=1, ponovite sljedeći bajt 5+2 puta: 4, 4, 4, 4, 4, 4, 4.
• . T=1, ponovite sljedeći bajt 2+2 puta: 80, 80, 80, 80.
• . T=0, čitanje 0+1 bajtova: 0.
• . T=1, ponoviti bajt 2+2 puta: 2, 2, 2, 2.
• . T=1, ponovi bajt 3+2 puta: 255, 255, 255, 255, 255.
• . T=1, ponoviti bajt 0+2 puta: 0, 0.

I sada posljednji korak: sačuvajte rezultat kao niz bajtova. Na primjer, par upakovan u bajt bi izgledao ovako:

Kao rezultat, dobijamo sljedeće:
0000: 84 00 02 04 02 00 85 04 82 80 00 00 82 02 83 FF
0010: 80 00

Na ovako jednostavan način, na ovom primjeru ulaznih podataka, dobili smo 18 bajtova od 32. Dobar rezultat, pogotovo kada se uzme u obzir da može biti mnogo bolji na dužim lancima.

Moguća poboljšanja

Efikasnost algoritma zavisi ne samo od samog algoritma, već i od načina na koji se implementira. Stoga je za različite podatke moguće razviti različite varijacije kodiranja i prezentacije kodiranih podataka. Na primjer, kada kodirate slike, možete napraviti lance promjenjive dužine: dodijeliti jedan bit za označavanje dugog lanca, a ako je postavljen na jedan, pohraniti dužinu iu sljedeći bajt. Na ovaj način žrtvujemo dužinu kratkih lanaca (65 elemenata umjesto 129), ali s druge strane omogućavamo kodiranje lanaca dužine do 16385 elemenata (2 14 + 2) sa samo tri bajta!

Dodatna efikasnost se može postići upotrebom heurističkih tehnika kodiranja. Na primjer, kodirajmo sljedeći lanac na naš način: "ABBA". Dobijamo " , A, , B, , A" - tj. Pretvorili smo 4 bajta u 6, naduvali originalne podatke za čak jedan i po puta! I što je više takvih kratkih naizmjeničnih heterogenih sekvenci, to je više suvišnih podataka. Ako ovo uzmemo u obzir, onda bismo rezultat mogli kodirati kao ", A, B, B, A" - potrošili bismo samo jedan dodatni bajt.

LZ77 - kratkoća u ponavljanju

LZ77 je jedan od najjednostavnijih i najpoznatijih algoritama u LZ porodici. Ime je dobio po svojim tvorcima: Abraham Lempel (Abraham L empel) i Jacob Ziv (Jacob Z iv). Brojevi 77 u naslovu znače 1977. godinu u kojoj je objavljen članak koji opisuje ovaj algoritam.

Glavna ideja je kodiranje identičnih nizova elemenata. Odnosno, ako se neki lanac elemenata pojavljuje više puta u ulaznim podacima, onda se sva njegova naknadna pojavljivanja mogu zamijeniti „vezama“ na njegovu prvu instancu.

Kao i ostali algoritmi ove porodice porodice, LZ77 koristi rečnik koji pohranjuje prethodno naiđene sekvence. Da bi to učinio, primjenjuje princip tzv. "klizni prozor": područje uvijek ispred trenutne pozicije kodiranja unutar koje možemo adresirati veze. Ovaj prozor je dinamički rečnik za ovaj algoritam - svaki element u njemu odgovara dva atributa: pozicija u prozoru i dužina. Iako u fizičkom smislu, ovo je samo dio sjećanja koji smo već kodirali.

Primjer implementacije

Pokušajmo sada nešto kodirati. Hajde da napravimo neki odgovarajući niz za ovo (unaprijed se izvinjavam zbog njegove apsurdnosti):

“Kompresija i dekompresija ostavljaju utisak. Hahahahaha!"

Evo kako će to izgledati u memoriji (ANSI kodiranje):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 Kompresija
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 i dekompre
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 godišnji odmor i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 Hahah
0040: 61 68 61 68 61 21 ahaha!

Još nismo odlučili za veličinu prozora, ali ćemo se složiti da je veći od veličine kodiranog niza. Pokušajmo pronaći sve nizove znakova koji se ponavljaju. String je niz znakova duži od jednog. Ako je lanac dio dužeg lanca koji se ponavlja, zanemarit ćemo ga.

“Kompresija i t de leave[an] i . Hah!”

Radi veće jasnoće, pogledajmo dijagram, gdje možemo vidjeti korespondenciju ponovljenih sekvenci i njihovih prvih pojavljivanja:

Možda je jedina nejasna točka ovdje sekvenca “Hahahahaha!”, jer niz znakova “ahahaha” odgovara kratkom nizu “ah”. Ali tu nema ničeg neobičnog, koristili smo neki trik koji omogućava algoritmu da ponekad radi kao RLE opisan ranije.

Činjenica je da ćemo prilikom raspakivanja pročitati navedeni broj znakova iz rječnika. A pošto je čitav niz periodičan, tj. podaci u njemu se ponavljaju sa određenim periodom, a simboli prvog perioda će biti neposredno ispred pozicije za raspakivanje, onda možemo ponovo kreirati ceo lanac od njih, jednostavno kopirajući simbole prethodnog perioda u sledeći.

Sredili smo to. Sada zamijenimo pronađena ponavljanja referencama na rječnik. Link ćemo napisati u formatu , gdje je P pozicija prvog pojavljivanja stringa u nizu, L je njegova dužina.

“Kompresija i t de ostavljaju i . Hah!"

Ali ne zaboravite da imamo posla s kliznim prozorom. Radi boljeg razumijevanja, tako da veze ne ovise o veličini prozora, apsolutne pozicije ćemo zamijeniti razlikom između njih i trenutne pozicije kodiranja.

“Kompresija i t de ostavljaju i . Hah!"

Sada samo trebamo oduzeti P od trenutne pozicije kodiranja da bismo dobili apsolutnu poziciju u nizu.

Vrijeme je da odlučite o veličini prozora i maksimalnoj dužini kodirane fraze. Budući da je riječ o tekstu, rijetko će se u njemu nalaziti posebno dugačke sekvence koje se ponavljaju. Dakle, hajde da dodijelimo, recimo, 4 bita za njihovu dužinu - ograničenje od 15 karaktera odjednom nam je sasvim dovoljno.

Ali veličina prozora već ovisi o tome koliko duboko ćemo tražiti iste lance. Budući da se radi o malim tekstovima, bilo bi dobro da broj bitova koje koristimo dopunimo na dva bajta: adresiraćemo veze u rasponu od 4096 bajtova, koristeći 12 bitova za ovo.

Iz iskustva s RLE znamo da se ne mogu koristiti sve vrijednosti. Očigledno, veza može imati minimalnu vrijednost od 1, stoga, da bi se adresa vratila u raspon 1..4096, moramo oduzeti jednu od veze prilikom kodiranja i dodati natrag kada dekodirati. Isto je i sa dužinama sekvenci: umesto 0..15 koristićemo opseg 2..17, pošto ne radimo sa nultim dužinama, a pojedinačni karakteri nisu sekvence.

Dakle, zamislimo naš kodirani tekst, uzimajući u obzir ove izmjene:

“Kompresija i t de ostavljaju i . Hah!"

Sada, opet, moramo nekako odvojiti komprimirane lance od ostatka podataka. Najčešći način je ponovno korištenje strukture i direktno ukazivanje gdje su podaci komprimirani, a gdje ne. Da bismo to učinili, podijelit ćemo kodirane podatke u grupe od osam elemenata (karaktera ili linkova), a prije svake od ovih grupa ubacit ćemo bajt, gdje svaki bit odgovara tipu elementa: 0 za znak i 1 za a veza.

Delimo se u grupe:

• "The Comp"
• "remisija"
• "i t de"
• "ostavi"
• "i. hah"

Sastavljanje grupa:

"(0,0,0,0,0,0,0,0) Rezija komp(0,0,0,0,0,0,0,0) (0,0,0,0,0,1 ,0,0) i t de(1,0,0,0,0,0,1,0) ostavljaju (0,1,0,0,0,0,0,1) i . Hah(0)!"

Dakle, ako naiđemo na bit 0 tokom raspakivanja, onda jednostavno čitamo karakter u izlazni tok, ako je bit 1, čitamo vezu i referencom čitamo sekvencu iz rječnika.

Sada samo moramo grupisati rezultat u niz bajtova. Složimo se da koristimo bitove i bajtove redoslijedom od visokog prema nižem. Pogledajmo kako se veze pakuju u bajtove koristeći primjer:

Kao rezultat, naš komprimirani stream će izgledati ovako:

0000:00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f #The comp#ressio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #and t##de###l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 eave## #i##. Hah
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 ###!

Moguća poboljšanja

U principu, ovdje će biti istina sve što je opisano za RLE. Konkretno, da biste pokazali korisnost heurističkog pristupa u kodiranju, razmotrite sljedeći primjer:

„Dugo goooooong. Looooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooom oje."

Nađimo sekvence samo za riječ "looooooower":

„Dugo goooooong. Vezani."

Da bismo kodirali takav rezultat, potrebna su nam četiri bajta po linku. Međutim, bilo bi ekonomičnije učiniti ovo:

„Dugo goooooong. Bio sam vezan."

Tada bismo potrošili jedan bajt manje.

Umjesto zaključka

Uprkos svojoj jednostavnosti i, čini se, ne prevelikoj efikasnosti, ovi algoritmi se i dalje široko koriste u različitim oblastima IT sfere.

Njihova prednost je jednostavnost i brzina, a složeniji i efikasniji algoritmi se mogu zasnivati ​​na njihovim principima i njihovim kombinacijama.

Nadam se da će suština ovih ovako navedenih algoritama pomoći nekome da shvati osnove i krene u pravcu ozbiljnijih stvari.

Run-length encoding (RLE) ili Repetition encoding je jednostavan algoritam kompresije podataka koji radi na nizovima podataka, odnosno sekvencama u kojima se isti znak pojavljuje nekoliko puta zaredom. Prilikom kodiranja, niz identičnih znakova koji čine niz zamjenjuje se nizom koji sadrži sam karakter koji se ponavlja i broj njegovih ponavljanja.

Karakteristike RLE algoritma:

Omjeri kompresije: Prva opcija: 32, 2, 0.5. Druga opcija: 64, 3, 128/129. (Najbolje, prosječne, najgore kvote). Image class: Algoritam je fokusiran na slike sa malim brojem boja: poslovne i naučne grafike. simetrija: Otprilike jedan.

Karakteristike: Pozitivni aspekti algoritma, možda, mogu se pripisati samo činjenici da ne zahtijeva dodatnu memoriju za arhiviranje i dearhiviranje, a radi i brzo. Zanimljiva karakteristika grupnog kodiranja je da se stepen arhiviranja nekih slika može značajno povećati samo promenom redosleda boja u paleti slika.

Prva verzija algoritma

Ovaj algoritam je izuzetno lak za implementaciju. Grupno kodiranje - od engleskog Run Length Encoding (RLE) - jedan je od najstarijih i najjednostavnijih algoritama za arhiviranje grafike. Slika u njemu (kao u nekoliko algoritama opisanih u nastavku) je ucrtana u lanac bajtova duž linija rastera. Sama kompresija u RLE-u nastaje zbog činjenice da se lanci identičnih bajtova pojavljuju u originalnoj slici. Zamijenite ih parovima<broj ponavljanja, vrijednost> smanjuje redundantnost podataka.

Algoritam je dizajniran za poslovnu grafiku - slike sa velikim površinama boja koje se ponavljaju. Situacija kada datoteka raste nije tako rijetka za ovaj jednostavan algoritam. Može se lako dobiti primjenom serijskog kodiranja na obrađene fotografije u boji. Da bi se slika udvostručila, ona se mora primijeniti na sliku u kojoj su vrijednosti svih piksela veće od binarnih 11000000 i ne ponavljaju se u parovima u nizu.

Druga verzija algoritma

Druga varijanta ovog algoritma ima veći maksimalni omjer arhiviranja i manje povećava veličinu izvorne datoteke.

29. lzw algoritam kompresije

Ime algoritma dato je prvim slovima imena njegovih programera - Lempel, Ziv I Welch.

LZW algoritam se temelji na ideji proširenja abecede, što omogućava korištenje dodatnih znakova za predstavljanje nizova običnih znakova. Koristeći, na primjer, umjesto 8-bitnih ASCII kodova 9-bitnih, dobijate dodatnih 256 znakova. Rad kompresora se svodi na izradu tabele koja se sastoji od linija i njihovih odgovarajućih kodova. Algoritam kompresije se svodi na sljedeće: program čita sljedeći karakter i dodaje ga u niz. Ako je red već u tabeli, čitanje se nastavlja; ako nije, red se dodaje u tabelu redova. Što se više redova ponavlja, više podataka će biti komprimirano. Vraćajući se na telefonski primjer, možemo povući vrlo pojednostavljenu analogiju i reći da ćemo kompresijom zapisa 233 34 44 metodom LZW doći do uvođenja novih linija - 333 i 444 i, izražavajući ih dodatnim znakovima, može smanjiti dužinu zapisa.

Karakteristike LZW algoritma:Omjeri kompresije: Približno 1000, 4, 5/7 (najbolje, prosječne, najgore kvote). Kompresija za 1000 puta se postiže samo na jednobojnim slikama koje su višestruke od oko 7 MB. Image class: LZW se fokusira na 8-bitne slike napravljene na računaru. Kompresije zbog istih podlanaca u toku. Simetrija: Gotovo simetrično, podložno optimalnoj implementaciji operacije pretraživanja redova tablice.

Karakteristike: Situacija kada algoritam uvećava sliku je izuzetno rijetka. LZW je univerzalan - njegove varijante se koriste u konvencionalnim arhivima.

Proces kompresije izgleda prilično jednostavno. Čitamo znakove ulaznog toka sekvencijalno i provjeravamo postoji li takav niz u tablici stringova koju smo kreirali. Ako postoji red, onda čitamo sljedeći znak, a ako nema reda, onda unosimo kod za prethodni pronađeni red u stream, stavljamo red u tablicu i počinjemo ponovo pretraživanje.

Posebnost LZW-a je da za dekompresiju nije potrebno spremiti tablicu stringova u datoteku za raspakivanje. Algoritam je izgrađen na takav način da možemo vratiti tabelu stringova koristeći samo tok koda.

Tipična slika digitalnog fotoaparata ima rezoluciju od oko 3000x2000, tj. oko 6 megapiksela; 24 bita po pikselu se obično koristi za predstavljanje boje. Dakle, količina početnih podataka je oko 17 megabajta. Za profesionalne uređaje za unos slike, veličina rezultujućeg rastera može biti mnogo veća, a dubina boje može biti do 48 bita po pikselu („Modern Bitmap Graphics Hardware“). Shodno tome, veličina jedne slike može biti veća od 200 megabajta. Stoga su algoritmi veoma relevantni. kompresija slike, ili, drugim riječima, algoritmi koji vam omogućavaju da smanjite količinu podataka koji predstavljaju sliku.

Postoje dvije glavne klase algoritama:

1. A se naziva algoritam kompresija bez gubitaka(eng. lossless compression ) ako postoji algoritam A -1 (inverzan prema A ) takav da je za bilo koju sliku I A (I) = I 1 i A -1 (I 1) = I . Slika I je definirana kao skup vrijednosti atributa piksela; nakon primjene algoritma A na I, dobijamo skup podataka I 1 . Kompresija bez gubitaka koristi se u grafičkim formatima kao što su: GIF, PCX, PNG, TGA, TIFF 1 Općenito govoreći, ovaj format također podržava kompresiju s gubicima., mnogi vlasnički formati od proizvođača digitalnih fotoaparata, itd.);
2. A se naziva algoritam kompresija sa gubicima(eng. lossy compression), ako ne pruža mogućnost preciznog vraćanja originalne slike. Algoritam uparen sa A, koji daje približnu restauraciju, biće označen kao A * : za sliku IA(I) = I 1 , A * (I 1) = I 2 i rezultirajuća restaurirana slika I 2 ne mora nužno da se tačno poklapa sa I . Par A, A * je odabran da pruži visoke omjere kompresije i da se i dalje sačuva vizualni kvalitet, tj. da se postigne minimalna razlika u percepciji između Ja i Ja 2 . Kompresija sa gubitkom se primenjuje u sledećim grafičkim formatima: JPEG, JPEG2000, itd.

Ovo predavanje govori o kompresiji bez gubitaka, koja je potrebna u slučajevima kada su informacije dobijene uz visoku cijenu (na primjer, medicinski snimci ili satelitski snimci), ili u drugim slučajevima kada je čak i najmanje izobličenje nepoželjno.

13.2. Nepostojanje idealnog algoritma

Kao što je već pomenuto u prethodnom pasusu, slika I se smatra skupom (sekvencijom) vrednosti atributa piksela. U nastavku ovog predavanja svi algoritmi i iskazi se primjenjuju i na slike i na proizvoljne nizove, čiji elementi mogu poprimiti konačan broj vrijednosti.

Izjava 13.2.1. Ne postoji algoritam koji može komprimirati bilo koji skup podataka bez gubitaka.

Postoje 2 N sekvence veličine N bitova (bit ćemo smatrati minimalnim nosiocem informacija). Neka postoji algoritam A takav da je , gdje je |I| - volumen podataka (dužina sekvence). Neka je M = max M k, a zatim M< N . Существует 2 1 + 2 2 + ... + 2 M последовательностей длины, меньшей или равной M . Но 2 1 +2 2 +...+2 M = 2 M+1 -2< 2 N . Kontradikcija.

Iz tvrdnje proizilazi da ima smisla razvijati algoritme koji bi efektivno komprimirali određenu klasu slika; u isto vrijeme, za ove algoritme uvijek će postojati slike za koje neće obezbijediti kompresiju.

13.3. Algoritmi kodiranja dužine ponavljanja (RLE).

Ova vrsta algoritama (algoritmi kodiranja dužine ponavljanja 2 U literaturi se često nalazi i drugi naziv - grupno kodiranje.(UPP 3 engleski Run Length Encoding)) zasniva se na najjednostavnijem principu: ponavljajuće grupe elemenata originalnog niza zamijenit ćemo parom (količina, element) ili samo kvantitetom.

RLE - bitni nivo

Razmotrićemo originalne podatke na nivou niza bitova; na primjer, predstavljanje crno-bijele slike. Obično ima nekoliko 0 ili 1 u nizu, a možete zapamtiti samo broj identičnih cifara u nizu. One. niz 0000 11111 000 11111111111 odgovara skupu brojeva broja ponavljanja 4 5 3 11 . Pojavljuje se sljedeća nijansa: brojevi koji označavaju broj ponavljanja također moraju biti kodirani u bitovima. Možemo pretpostaviti da svaki broj ponavljanja varira od 0 do 7 (tj. može biti kodiran sa tačno tri bita), tada se sekvence 11111111111 mogu povezati sa brojevima 7 0 4 , tj. 7 jedinica, 0 nula, 4 jedinice. Na primjer, niz koji se sastoji od 21 jedinice, 21 nule, 3 jedinice i 7 nula je kodiran ovako: 111 000 111 000 111 111 000 111 000 111 011 111 , tj. iz originalne sekvence, koja ima dužinu od 51 bita, dobijena je sekvenca od 36 bita.

Ideja ove metode se koristi prilikom slanja faksova.

RLE - nivo bajta

Pretpostavimo da je ulaz slika u sivim tonovima, gdje je 1 bajt dodijeljen vrijednosti intenziteta piksela. Jasno je da je, u poređenju sa crno-bijelim rasterom, očekivanje dugog lanca identičnih bitova značajno smanjeno.

Podijelit ćemo ulazni tok na bajtove (slova) i kodirati ponovljena slova kao par (broj, slovo).

One. AABBBCDAA kodiranje (2A) (3B) (1C) (1D) (2A) . Međutim, mogu postojati dugi nizovi podataka u kojima se ništa ne ponavlja, a svako slovo kodiramo kao par (broj, slovo).

Recimo da imamo fiksni broj (slovo) M (od 0 do 255). Tada se jedno slovo može kodirati samo po sebi, - output = S , a ako postoji nekoliko slova ili , onda output = CS , gdje je C > M , a C - M je broj uzastopnih slova S . Na primjer, dajemo samo algoritam dekodiranja.

// M - fiksna granica // čitanje znakova sekvencijalno iz ulaznog toka // in - ulaz - komprimirana sekvenca // out - izlaz - dekomprimirana sekvenca while(in.Read(c)) ( if(c > M) ( // brojač slučajeva n = c - M;in.Read(c);for(i = 0;i< n; i++) out.Write(c); } else // случай просто символа out.Write(c); } Listing 13.1. RLE algoritam dekodiranja - nivo bajtova

M broj je obično 127. Češće se koristi modifikacija ovog algoritma, gde je znak brojača prisustvo jedinica u 2 najznačajnija bita karaktera koji se čita. Preostalih 6 bitova je vrijednost brojača.

Ova modifikacija ovog algoritma se koristi u PCX formatu. Međutim, modifikacije ovog algoritma se rijetko koriste same, jer podklasa sekvenci na kojima je ovaj algoritam efikasan je relativno uska. Modifikacije algoritma se koriste kao jedna od faza kompresijskog cjevovoda (na primjer, u JPEG,