• Tutorial

Davno, dok sam još bio naivni školarac, odjednom sam postao užasno znatiželjan: kako to da podaci u arhivama magično zauzimaju manje mjesta? Nakon što sam montirao svoj pouzdani dialup, 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 nijedna od njih tada se nije činila lako razumljivom - popisi kodova činili su se poput kineske pismenosti, a pokušaji razumijevanja neobične terminologije i raznih formula nisu bili okrunjeni uspjehom.

Stoga je svrha ovog članka dati predodžbu o najjednostavnijim algoritmima kompresije onima čije znanje i iskustvo još ne dopuštaju odmah razumijevanje stručne literature ili čiji je profil potpuno daleko od takvih tema. Oni. Reći ću vam na prvi pogled o nekim od najjednostavnijih algoritama i dati primjere njihove implementacije bez kilometarskih popisa kodova.

Dopustite mi da vas odmah upozorim da neću razmatrati detalje implementacije procesa kodiranja i takve nijanse kao što su učinkovito pretraživanje pojavljivanja niza. Članak će se baviti samo samim algoritmima i načinima prezentiranja rezultata njihova rada.

RLE - kompaktnost jednolikosti

RLE algoritam je vjerojatno najjednostavniji od svih: njegova bit leži u kodiranju ponavljanja. Drugim riječima, uzimamo sekvence identičnih elemenata i "skupamo" ih u parove "količina/vrijednost". Na primjer, niz poput "AAAAAAAABCCCC" može se pretvoriti u nešto poput "8×A, B, 4×C". Ovo je, općenito, sve što trebate znati o algoritmu.

Primjer implementacije

Recimo da imamo skup određenih cjelobrojnih koeficijenata koji mogu poprimiti vrijednosti od 0 do 255. Logično, došli smo do zaključka da je razumno pohraniti ovaj skup kao niz bajtova:
podaci bez predznaka = (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 češće vidjeti ove podatke u obliku heksadecimalne kopije:
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 FF 00 00

Nakon razmišljanja zaključili smo da bi bilo dobro takve garniture nekako sabiti kako bismo uštedjeli prostor. Da bismo to učinili, analizirali smo ih i identificirali uzorak: vrlo često nailazimo na podnizove koji se sastoje od identičnih elemenata. Naravno, RLE je savršen za to!

Kodirajmo svoje podatke pomoću novostečenog znanja: 6x0, 4, 2, 0, 7x4, 4x80, 0, 4x2, 5x255, 2x0.

Vrijeme je da nekako prezentiramo naš rezultat kompjuterski razumljivo oblik. Da bismo to učinili, u toku podataka moramo nekako odvojiti pojedinačne bajtove od kodiranih nizova. Budući da naši podaci koriste cijeli raspon vrijednosti bajtova, neće biti moguće jednostavno odabrati bilo koji raspon vrijednosti za naše potrebe.

Postoje najmanje dva izlaza iz ove situacije:

1. Kao pokazatelj komprimiranog lanca odaberite jednu bajtnu vrijednost, au slučaju kolizije sa stvarnim podacima, pobjegnite je. Na primjer, ako koristimo vrijednost 255 u "službene" svrhe, tada kada naiđemo na ovu vrijednost u ulaznim podacima bit ćemo prisiljeni napisati "255, 255" i koristiti maksimalno 254 iza indikatora.
2. Strukturirajte kodirane podatke, navodeći količinu ne samo za ponovljene, već i za sljedeće pojedinačne elemente. Tada ćemo unaprijed znati gdje su koji podaci.

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

Sada imamo dvije vrste nizova: lance pojedinačnih elemenata (poput "4, 2, 0") i lance identičnih elemenata (poput "0, 0, 0, 0, 0, 0"). Odaberimo jedan bit u “servisnim” bajtovima za vrstu niza: 0 - pojedinačni elementi, 1 - identični. Za ovo, uzmimo, recimo, najznačajniji bit bajta.

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

Ispada da ćemo prvo upisati duljinu niza u izlazni tok, a zatim ili jednu ponovljivu vrijednost ili lanac neponovljivih elemenata navedene duljine.

Prvo što vam treba zapasti za oko je da u ovoj situaciji imamo par neiskorištenih vrijednosti. Ne mogu postojati nizovi s nultom duljinom, tako da možemo povećati maksimalnu duljinu na 128 bajtova oduzimanjem jedan od duljine prilikom kodiranja i dodavanjem jedan prilikom dekodiranja. Na ovaj način možemo kodirati duljine od 1 do 128 umjesto duljina od 0 do 127.

Druga stvar koju možete primijetiti je da nema nizova identičnih elemenata jedinične duljine. Stoga ćemo prilikom kodiranja oduzeti još jedan od duljine takvih nizova, čime ćemo njihovu maksimalnu duljinu povećati na 129 (maksimalna duljina lanca pojedinačnih elemenata i dalje je 128). Oni. Naši lanci identičnih elemenata mogu imati duljinu od 2 do 129.

Ponovno kodirajmo naše podatke, ali sada u obliku razumljivom računalu. Servisne bajtove ćemo pisati kao , gdje je T vrsta niza, a L je duljina. Uzmimo odmah u obzir da dužine pišemo u modificiranom obliku: za T=0 oduzimamo jedan od L, a za T=1 oduzimamo dva.

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

Pokušajmo dekodirati naš rezultat:

• . T=1, što znači da će se sljedeći bajt ponoviti L+2 (4+2) puta: 0, 0, 0, 0, 0, 0.
• . T=0, što znači da jednostavno čitamo 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, ponovite bajt 2+2 puta: 2, 2, 2, 2.
• . T=1, ponovite bajt 3+2 puta: 255, 255, 255, 255, 255.
• . T=1, ponovite bajt 0+2 puta: 0, 0.

A sada posljednji korak: spremiti rezultat kao niz bajtova. Na primjer, par upakiran u bajt bi izgledao ovako:

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

Na ovaj jednostavan način u ovom primjeru Dobili smo 18 bajta od 32 bajta ulaznih podataka, što nije loš rezultat, pogotovo ako se uzme u obzir da na dužim lancima može ispasti puno bolji.

Moguća poboljšanja

Učinkovitost algoritma ne ovisi samo o samom algoritmu, već i o načinu na koji je implementiran. Stoga se za različite podatke mogu razviti različite varijante kodiranja i predstavljanja kodiranih podataka. Na primjer, kada kodirate slike, možete napraviti lance promjenjive duljine: dodijeli jedan bit za označavanje dugog lanca, a ako je postavljen na jedan, pohrani duljinu iu sljedećem bajtu. Na ovaj način žrtvujemo duljinu kratkih lanaca (65 elemenata umjesto 129), ali omogućujemo kodiranje lanaca do 16385 elemenata dugih (2 14 + 2) sa samo tri bajta!

Dodatna učinkovitost može se postići korištenjem heurističkih metoda kodiranja. Na primjer, kodirajmo sljedeći lanac pomoću naše metode: "ABBA". Dobivamo " , A, , B, , A" - tj. Pretvorili smo 4 bajta u 6, napuhavši izvorne podatke za čak jedan i pol puta! I što je više takvih kratkih izmjeničnih nizova različitih vrsta, to je više suvišnih podataka. Ako ovo uzmemo u obzir, onda bismo mogli kodirati rezultat kao ", A, B, B, A" - uzalud bismo potrošili samo jedan dodatni bajt.

LZ77 - kratkoća u ponavljanju

LZ77 je jedan od najjednostavnijih i najpoznatijih algoritama u LZ obitelji. Nazvan po svojim tvorcima: Abraham Lempel L empel) i Jacob Ziv (Jakov Z iv). Brojevi 77 u naslovu označavaju 1977. godinu u kojoj je objavljen članak koji opisuje ovaj algoritam.

Osnovna ideja je kodirati identične nizove elemenata. To jest, ako se određeni lanac elemenata pojavljuje više od jednom u ulaznim podacima, tada se sva njegova sljedeća pojavljivanja mogu zamijeniti "vezama" na njegovu prvu instancu.

Kao i drugi algoritmi u ovoj obitelji, LZ77 koristi rječnik koji pohranjuje ranije pronađene sekvence. Da bi to učinio, on primjenjuje princip tzv. "klizni prozor": područje uvijek ispred trenutne pozicije kodiranja unutar kojeg možemo adresirati reference. Ovaj prozor je dinamički rječnik za ovaj algoritam - svaki element u njemu odgovara dvama atributima: poziciji u prozoru i dužini. Iako je u fizičkom smislu ovo samo dio sjećanja koji smo već kodirali.

Primjer implementacije

Pokušajmo sada nešto kodirati. Generirajmo neki odgovarajući red za ovo (unaprijed se ispričavam zbog apsurdnosti):

"Kompresija i dekompresija ostaviti dojam. Hahahahaha!"

Ovako će 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 sjednica ostavite
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 mpresija. Hahah
0040: 61 68 61 68 61 21 ahaha!

Još nismo odlučili o veličini prozora, ali složit ćemo se da hoće veće veličine kodirani niz. Pokušajmo pronaći sve nizove znakova koji se ponavljaju. Lanac smatramo nizom znakova duljim od jednog. Ako je lanac dio dužeg lanca koji se ponavlja, zanemarit ćemo ga.

“Kompresija i t de ostavljaju [an] i . haha!

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

Možda će jedina nejasna točka ovdje biti niz "Hahahahaha!", jer lanac znakova "ahahaha" odgovara kratkom nizu "ah". Ali ovdje nema ničeg neobičnog, upotrijebili smo neki trik koji omogućuje algoritmu da ponekad radi kao ranije opisani RLE.

Činjenica je da ćemo prilikom raspakiranja pročitati navedeni broj znakova iz rječnika. A budući da je cijeli niz periodičan, tj. podaci u njemu se ponavljaju s određenom točkom, a simboli prve periode nalazit će se neposredno prije pozicije za raspakiranje, tada iz njih možemo ponovno stvoriti cijeli lanac jednostavnim kopiranjem simbola prethodne periode u sljedeću.

To je sređeno. Sada zamijenimo pronađena ponavljanja poveznicama na rječnik. Link ćemo napisati u formatu, gdje je P pozicija prvog pojavljivanja lanca u retku, L je njegova duljina.

“Kompresija i t de ostavljaju i. haha!

Ali ne treba zaboraviti da imamo posla s klizni prozor. Radi boljeg razumijevanja, kako veze ne bi ovisile o veličini prozora, zamijenimo apsolutne pozicije razlikom između njih i trenutne pozicije kodiranja.

“Kompresija i t de ostavljaju i. haha!

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 maksimalna duljinašifrirana fraza. Budući da se radi o tekstu, rijetko će u njemu biti posebno dugih nizova koji se ponavljaju. Dakle, dodijelimo im, recimo, 4 bita za njihovu duljinu - ograničenje od 15 znakova odjednom sasvim nam je dovoljno.

Ali veličina prozora određuje koliko duboko ćemo tražiti identične lance. Budući da se radi o malim tekstovima, bilo bi sasvim ispravno broj bitova koje koristimo nadopuniti na dva bajta: adresirat ćemo veze u rasponu od 4096 bajtova, koristeći za to 12 bitova.

Iz iskustva s RLE znamo da se ne mogu koristiti sve vrijednosti. Očito, poveznica može imati minimalna vrijednost 1, dakle, da bismo se vratili u rasponu 1..4096, moramo oduzeti jedan od reference prilikom kodiranja i dodati ga natrag prilikom dekodiranja. Ista stvar s duljinama niza: umjesto 0..15 koristit ćemo raspon 2..17, budući da ne radimo s nultim duljinama, već pojedinačni likovi nisu nizovi.

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

“Kompresija i t de ostavljaju i. haha!

Sada, opet, moramo nekako odvojiti komprimirane lance od ostalih podataka. Najčešći način je ponovno koristiti strukturu i eksplicitno naznačiti gdje su podaci komprimirani, a gdje nisu. Da bismo to učinili, podijelit ćemo kodirane podatke u grupe od osam elemenata (simbola ili veza), a prije svake od tih grupa umetnut ćemo bajt, gdje svaki bit odgovara tipu elementa: 0 za simbol i 1 za poveznica.

Dijelimo se u grupe:

• "kompjuter"
• "resija"
• "i t de"
• "napustiti"
• "i. hah"

Kreirajmo grupe:

"(0,0,0,0,0,0,0,0) Comp(0,0,0,0,0,0,0,0) rezija (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 tijekom raspakiranja naiđemo na bit 0, tada jednostavno čitamo znak u izlazni tok, ako je bit 1, čitamo vezu, a iz veze čitamo niz iz rječnika.

Sada sve što trebamo učiniti je grupirati rezultat u niz bajtova. Složimo se da bitove i bajtove koristimo redom od visokog prema niskom. Pogledajmo kako se veze pakiraju u bajtove koristeći primjer:

Kao rezultat toga, naš komprimirani tok ć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 #i t##de###l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 streha## #i##. haha
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 ###!

Moguća poboljšanja

U principu, sve što je opisano za RLE ovdje će biti istina. Konkretno, kako bismo pokazali korisnost heurističkog pristupa kod kodiranja, razmotrite sljedeći primjer:

“Dugo goooooong. Loooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo.

Pronađimo nizove samo za riječ “loooooower”:

“Dugo goooooong. Najbolje uvezano."

Za kodiranje takvog rezultata potrebna su nam četiri bajta po referenci. Međutim, bilo bi ekonomičnije učiniti ovo:

“Dugo goooooong. Bio sam vezan.”

Tada bismo potrošili jedan bajt manje.

Umjesto zaključka

Unatoč svojoj jednostavnosti i naizgled ne baš učinkovitoj, ovi algoritmi još uvijek se široko koriste u raznim područjima IT sektora.

Njihova prednost je jednostavnost i brzina, a na njihovim principima i njihovim kombinacijama mogu se temeljiti složeniji i učinkovitiji algoritmi.

Nadam se da će bit ovih algoritama prikazanih na ovaj način pomoći nekome da shvati osnove i počne gledati prema ozbiljnijim stvarima.

Run-length encoding (RLE) ili Repeat Coding jednostavan je algoritam za kompresiju podataka koji radi na nizovima podataka, to jest 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 znak koji se ponavlja i broj njegovih ponavljanja.

Karakteristike RLE algoritma:

Omjeri kompresije: Prva opcija: 32, 2, 0,5. Druga opcija: 64, 3, 128/129. (Najbolji, prosječni, najgori izgledi). Klasa slike: Algoritam je fokusiran na slike s malim brojem boja: poslovne i znanstvene grafike. Simetrija: Otprilike jedan.

Karakteristike: DO pozitivni aspekti algoritam se možda može pripisati samo činjenici da ne zahtijeva dodatna memorija prilikom arhiviranja i raspakiranja, a također radi brzo. Zanimljiva značajka grupno kodiranje je da se stupanj arhiviranja za neke slike može značajno povećati jednostavnom promjenom redoslijeda boja u paleti slika.

Prva verzija algoritma

Ovaj algoritam je izuzetno jednostavan 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) ucrtana je u lanac bajtova duž rasterskih linija. Do same kompresije u RLE dolazi zbog činjenice da izvorna slika sadrži nizove identičnih bajtova. Zamjenjujući ih parovima<brojač ponavljanja, vrijednost> smanjuje redundantnost podataka.

Algoritam je dizajniran za poslovnu grafiku - slike s velikim površinama ponavljajuće boje. Situacija kada datoteka raste nije tako rijetka za ovaj jednostavan algoritam. Može se lako dobiti primjenom grupnog kodiranja na obrađene fotografije u boji. Kako bi se udvostručila slika, mora se 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 verzija ovog algoritma ima veći maksimalni omjer arhiviranja i manje povećava veličinu izvorne datoteke.

29. lzw algoritam kompresije

Algoritam je dobio ime po prvim slovima prezimena njegovih kreatora - Lempel, Ziv I Welch.

LZW algoritam temelji se na ideji proširenja abecede, što omogućuje korištenje dodatnih znakova za predstavljanje nizova uobičajenih znakova. Korištenjem, primjerice, 9-bitnih ASCII kodova umjesto 8-bitnih, dobivate dodatnih 256 znakova. Rad kompresora svodi se na izgradnju tablice koja se sastoji od redaka i njihovih odgovarajućih kodova. Algoritam kompresije se svodi na sljedeće: program čita sljedeći znak i dodaje ga nizu. Ako je red već u tablici, čitanje se nastavlja, ako nije, dana linija dodaje se u tablicu nizova. Što je više dupliciranih redaka, to će podaci biti više komprimirani. Vraćajući se na primjer s telefonom, možemo vrlo pojednostavljenom analogijom reći da ćemo komprimiranjem unosa 233 34 44 metodom LZW doći do uvođenja novih linija - 333 i 444 i izražavajući ih dodatni znakovi, možemo smanjiti duljinu snimanja.

Karakteristike LZW algoritma:Omjeri kompresije: Približno 1000, 4, 5/7 (najbolji, prosječni, najgori izgledi). Kompresija od 1000 puta postiže se samo na slikama u jednoj boji koje su višekratnike veličine od približno 7 MB. Klasa slike: LZW je fokusiran na 8-bitne slike izrađene na računalu. Sažima se zbog identičnih podlanaca u toku. Simetrija: Gotovo simetrično, pod uvjetom da je operacija pretraživanja za red u tablici optimalno implementirana.

Karakteristike: Situacija kada algoritam povećava sliku je iznimno rijetka. LZW je univerzalan - to su njegove varijante koje se koriste u konvencionalnim arhivarima.

Proces kompresije izgleda prilično jednostavno. Redom čitamo znakove ulaznog toka i provjeravamo postoji li takav niz u tablici nizova koju smo kreirali. Ako postoji linija, onda čitamo sljedeći znak, a ako nema, onda u stream upisujemo šifru prethodno pronađene linije, upisujemo liniju u tablicu i ponovno pokrećemo pretragu.

Osobitost LZW-a je da za dekompresiju ne morate spremati tablicu nizova u datoteku za dekompresiju. Algoritam je dizajniran na takav način da možemo vratiti tablicu nizova koristeći samo tok kodova.

Tipična slika snimljena digitalnim fotoaparatom ima rezoluciju od oko 3000x2000, tj. oko 6 megapiksela; Za prijenos boje obično se koristi 24 bita po pikselu. Dakle, volumen izvornih podataka je oko 17 megabajta. Za profesionalni uređaji Prilikom unosa slika, veličina rezultirajućeg rastera može biti znatno veća, a dubina boje može doseći 48 bita po pikselu ("Suvremeni hardver rasterske grafike"). Prema tome, veličina jedne slike može biti veća od 200 megabajta. Stoga su algoritmi vrlo relevantni kompresija slike ili, drugim riječima, algoritmi koji smanjuju količinu podataka koji predstavljaju sliku.

Postoje dvije glavne klase algoritama:

1. A se naziva algoritam kompresija bez gubitaka(engleska kompresija bez gubitaka), ako postoji algoritam A -1 (obrnut A) takav da 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, dobivamo skup podataka I 1 . U takvim se slučajevima koristi kompresija bez gubitaka grafički formati prikazi slika kao što su: GIF, PCX, PNG, TGA, TIFF 1 Općenito govoreći, ovaj format također podržava kompresiju s gubitkom., gomila vlastite formate od proizvođača digitalne kamere, itd.);
2. A se naziva algoritam kompresija s gubitkom(eng. lossy compression), ako ne pruža mogućnost točne obnove izvorne slike. Algoritam uparen s A koji osigurava približnu obnovu bit će označen kao A *: za sliku I A(I) = I 1, A * (I 1) = I 2 i rezultirajuća obnovljena slika I 2 ne mora se točno podudarati s ja Par A, A * odabran je tako da pruža visoke omjere kompresije i još uvijek održava vizualnu kvalitetu, tj. postići minimalnu razliku u percepciji između Ja i Ja 2. Kompresija s gubitkom koristi se u sljedećim formatima slika: JPEG, JPEG2000 itd.

Ovo predavanje fokusira se na kompresiju bez gubitaka, koja je potrebna u slučajevima kada su informacije primljene uz veliku cijenu(na primjer, medicinske slike ili satelitske slike), ili u drugim slučajevima gdje je čak i najmanje izobličenje nepoželjno.

13.2. Nepostojanje idealnog algoritma

Kao što je već spomenuto u prethodni odlomak, slika I se smatra skupom (slijedom) vrijednosti atributa piksela. U nastavku ovog predavanja svi algoritmi i iskazi vrijede i za slike i za proizvoljne nizove, čiji elementi mogu poprimiti konačan broj vrijednosti.

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

Postoji 2 N nizova veličine N bitova (bit ćemo smatrati minimalnim nositeljem informacije). Neka postoji algoritam A takav da je , gdje je |I| - volumen podataka (duljina niza). Neka je M = max M k, tada je M< N . Существует 2 1 + 2 2 + ... + 2 M последовательностей длины, меньшей или равной M . Но 2 1 +2 2 +...+2 M = 2 M+1 -2< 2 N . Kontradikcija.

Iz tvrdnje proizlazi da ima smisla razvijati algoritme koji bi učinkovito komprimirali određena klasa slike; u isto vrijeme, za ove algoritme uvijek će postojati slike za koje neće osigurati kompresiju.

13.3. Algoritmi ponavljanja kodiranja duljine (RLE).

Ova vrsta algoritama (algoritmi za kodiranje duljine ponavljanja 2 Drugi naziv koji se često nalazi u literaturi je grupno kodiranje.(URL 3 Engleski Run Length Encoding)) temelji se na najjednostavnijem principu: ponavljajuće skupine elemenata izvornog niza zamijenit ćemo parom (količina, element) ili samo količinom.

RLE - bitna razina

Razmotrit ćemo izvorne podatke na razini niza bitova; primjerice predstavljanje crno-bijela slika. Obično postoji nekoliko 0 ili 1 u nizu, a možete zapamtiti samo broj identičnih znamenki u nizu. Oni. niz 0000 11111 000 11111111111 odgovara skupu brojeva 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 se kodirati s točno tri bita), tada se nizovi 11111111111 mogu podudarati s 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 originalnog niza koji je dug 51 bit, dobiven je niz dug 36 bita.

Ideja iza ove metode koristi se u prijenosu faksa.

RLE - razina bajtova

Pretpostavimo da je ulaz polutonska slika, gdje je 1 bajt dodijeljen za vrijednost intenziteta piksela. Jasno je da je u usporedbi s crno-bijelim rasterom očekivanje dugog lanca identičnih bitova značajno smanjeno.

Podijelit ćemo ulazni tok u bajtove (slova) i kodirati ponavljajuća slova s ​​parom (količina, slovo).

Oni. AABBBCDAA kodirano (2A) (3B) (1C) (1D) (2A) . Međutim, mogu postojati dugi dijelovi podataka gdje se ništa ne ponavlja, a mi kodiramo svako slovo kao par (broj, slovo).

Neka nam je fiksni broj (slovo) M (od 0 do 255). Tada se jedno slovo može kodirati samo po sebi, - izlaz = S, a ako ima više slova ili, onda izlaz = CS, gdje je C > M, a C - M je broj uzastopnih slova S. Na primjer, predstavljamo samo algoritam dekodiranja.

// M - fiksna granica // uzastopno čitanje znakova iz ulaznog toka // in - input - komprimirani niz // out - output - dekomprimirani niz 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. Algoritam RLE dekodiranja - razina bajta

Broj M je obično 127. Češće se koristi modifikacija ovog algoritma, gdje je znak brojača prisutnost jedinica u 2 najznačajnija bita očitanog simbola. Preostalih 6 bitova su vrijednost brojača.

Ova modifikacija ovog algoritma koristi se u PCX formatu. Međutim, modifikacije ovog algoritma rijetko se koriste same, jer podklasa nizova na kojima ovaj algoritam učinkovit, relativno uzak. Modifikacije algoritma koriste se kao jedna od faza cjevovoda kompresije (npr. u JPEG formatu,