Dinamička Markovljeva kompresija

Dinamička Markovljeva kompresija (DMC) je algoritam za kompresiju podataka bez gubitaka koji su razvili Gordon Kormak i Najdžel Horspul. Ovaj algoritam koristi prediktivno aritmetičko kodiranje slično predikciji putem delimičnog poklapanja (PPM), sa razlikom što se unos predviđa jedan po jedan bit (umesto jedan po jedan bajt). DMC ima dobar stepen kompresije i umerenu brzinu, slično PPM, ali zahteva nešto više memorije i primena mu nije rasprostranjena. Neke skorašnje primene uključuju ekperimentalne kompresione programe hook od Nani Frančesko Antonija, ocamyd od Frenka Švelindžera, a koristi se i kao podmodel u paq8l od Meta Mahonija. Svi ovi su zasnovani na primeni u C iz 1993 od Gordona Kormaka.

Algoritam

DMC predviđa i kodira jedan po jedan bit. Razlikuje se od PPM u tome što kodira bitove umesto bajtova, a od algoritama sa mešanjem konteksta poput PAQ u tome što radi sa samo jednim kontekstom po predviđanju. Bit koji je predviđen se potom kodira aritmetičkim kodiranjem.

Aritmetičko kodiranje

Aritmetički koder nad bitovima poput DMC ima dve komponente, prediktor i aritmetički koder. Prediktor prihvata ulazni niz od n-bitova x = x1x2...xn i dodeljuje mu verovatnoću p(x), iskazanu kao proizvod niza predviđanja, p(x1)p(x2|x1)p(x3|x1x2) ... p(xn|x1x2...xn–1). Aritmetički koder utvrđuje dva visoko precizna binarna broja pdonji i pgornji, koji predstavljaju mogući raspon za ukupnu verovatnoću koju će model dodeliti svim nizovima leksikografski manjim od x, uzevši u obzir do sada viđene x bitove. Komprimovani kod za x je px, najkraći niz bitova koji predstavlja broj između pdonji i pgornji. U ovom rasponu je uvek moguće naći broj koji je ne više od jednog bita duži od Šenonovog ograničenja, log2 1/p(x'). Jedan takav broj se može dobiti od pgornji tako što se ispuste svi preostali bitovi nakon prvog bita koji se razlikuje od pdonji.

Kompresija teče na sledeći način. Početni raspon je određen kao pdonji = 0, pgornji = 1. Za svaki bit, prediktor procenjuje p0 = p(xi = 0|x1x2...xi–1) i p1 = 1 − p0, verovatnoću 0 ili 1, tim redom. Aritmetički koder potom deli trenutni raspon (pdonji, pgornji), na dva dela u srazmeri sa p0 i p1. Potom podraspon koji se podudara sa sledećim bitom xi postaje novi raspon.

Za dekompresiju, prediktor obavlja identičan niz predviđanja, uzevši u obzir već dekomprimovane bitove. Aritmetički koder obavlja identičan niz podela raspona, potom odabira raspon koji sadrži px i iznosi bit xi koji se podudara sa tim podrasponom.

U praksi nije potrebno održavati visoku preciznost pdonji i pgornji u memoriji. Kako se raspon sužava vodeći bitovi oba broja će biti isti i mogu se odmah izneti. 

DMC model

DMC prediktor je tabela koja mapira (nad bitovima) kontekste prema paru vrednosti, n0 i n1, koji predstavljaju broj nula i jedinica koje su prethodno posmatrane u ovom kontekstu. Stoga, on predviđa da će sledeći bit biti 0 sa verovatnoćom p0 = n0/n = n0/(n0 + n1) ili 1 sa verovatnoćom p1 = 1 − p0 = n1/n. Pored toga, svaki unos na tabeli ima par pokazatelja ka kontekstima dobijenim dodavanjem bilo 0 ili 1 sa desne strane trenutnog konteksta (sa mogućim ispuštanjem bitova sa leve strane). Zato nikada nije neophodno tražiti trenutni kontekst u tabeli; dovoljno je pratiti pokazatelj ka trenutnom kontekstu i pratiti veze.

U originalnoj DMC primeni, početna tabela je set svih konteksta dužine 8 do 15 bitova koji počinju na granici bajta. Početno stanje je bilo koji od 8-bitnih konteksta. Vrednosti su brojevi sa pokretnim zarezom započeti kao male, veće od nule, konstante poput 0.2. Vrednosti ne počinju od nule da bi se omogućilo kodiranje vrednosti čak i ako prethodno nisu viđene u trenutnom kontekstu.

Modeliranje je isto za kompresiju i dekompresiju. Za svaki bit, izračunava se p0 and p1, bit xi se ili kodira ili dekodira, model se ažurira dodavanjem 1 vrednosti koja se podudara sa xi, i sledeći kontekst se nalazi praćenjem veze koja se podudara sa xi. 

Dodavanje novih konteksta

DMC kako je gore opisan je jednak modelu konteksta prvog reda. Međutim, normalno je dodavati duže kontekste da bi se poboljšala kompresija. Ako je trenutni kontekst A, a sledeći kontekst B bi ispustio bitove sa leve strane, tada DMC može dodati (klonirati) novi kontekst C iz konteksta B. C predstavlja isti kontekst kao što je A nakon dodavanja jednog bita sa desne strane kao što je slučaj sa B, ali bez ispuštanja ijednog bita sa leve strane. Veza od A će stoga biti premeštena sa B da vodi ka C. B i C će oba donositi ista predviđanja, i oba će voditi do istog para sledećih stanja. Totalna vrednost, n = n0 + n1 za C će biti jednaka vrednosti nx za A (za unešeni bit x), i ta vrednosti će biti oduzeta od B.

Na primer, pretpostavimo da stanje A predstavlja kontekst 11111. Pri unosu bita 0, ono prelazi u stanje B koje predstavlja kontekst 110, dobijen ispuštanjem 3 bita sa leve strane. U kontekstu A, bilo je 4 nultih bitova i nekoliko bitova sa jedinicom. U kontekstu B, bilo je 3 nule i 7 jedinica (n = 10), što predviđa p1 = 0.7.

State	n0	n1	next0	next1
A = 11111	4		B
B = 110	3	7	E	F

C je klonirano od B. Ono predstavlja kontekst 111110. I B i C predviđaju p1 = 0.7, i oba prelaze u ista sledeća stanja, E i F. Vrednost za C je n = 4, jednak n0 za A. Ovo ostavlja n = 6 za B.

State	n0	n1	next0	next1
A = 11111	4		C
B = 110	1.8	4.2	E	F
C = 111110	1.2	2.8	E	F

Stanja se kloniraju u trenutku pre prelaska u njih. U originalnom DMC, uslov za kloniranje stanja je kada je prelazak iz A u B najmanje 2, a vrednost za B je najmanje 2 više od toga. (Kada je drugi prag veći od 0, on garantuje da će druga stanja ipak preći u B nakon kloniranja). Neke primene poput hook dozvoljavaju ovim pragovima da budu podešeni kao parametri. U paq8l, ovi se pragovi povećavaju kako se memorija popunjava da bi se usporila stopa rasta novih stanja. U većini primena, kada se memorija istroši model se odbacuje i ponovno inicijalizuje nazad u originalni model nad bajtovima prvog reda.

Spoljašnje veze

• Data Compression Using Dynamic Markov Modelling
• Google Developers YouTube channel: Compressor Head Episode 3 (Markov Chain Compression)