DMC (pakkausalgoritmi)

DMC ( dynaaminen Markov-pakkaus ,  dynaaminen Markov-pakkaus [1] ) on Gordon Cormackin ja Nigel Horspoolin [2] kehittämä häviötön tiedonpakkausalgoritmi . Menetelmä on rakennettu samalla tavalla kuin PPM -menetelmä : algoritmi itsessään on ennustaja (laskee symbolien todennäköisyydet) ja suoran pakkauksen suorittaa entropiakooderi . . Toisin kuin PPM, DMC-menetelmä toimii yleensä bittitasolla, kun taas PPM toimii tavutasolla. DMC tarjoaa vertailukelpoiset pakkaustasot ja käsittelynopeudet PPM:ään, mutta vaatii enemmän muistia, eikä se ole yhtä yleinen kuin PPM. Jotkut nykyaikaisista toteutuksista ovat: Nania Francesco Antonion koukkukompressori , Frank Schwellingerin ocamyd- kompressori ja DMC:tä käytetään yhtenä malleista Matt Mahoneyn paq8l-kompressorissa . Kaikki luetellut kompressorit perustuvat Gordon Cormackin alkuperäiseen 1993 C -toteutukseen.

Algoritmi

DMC ennustaa ja koodaa yhden bitin toiminnan loogista vaihetta kohden. Se eroaa PPM :stä siinä, että se toimii bittien, ei tavujen tasolla. Ero kontekstin sekoitusmenetelmiin (kuten PAQ ) on se, että DMC rakentaa ja käyttää yhtä lähdemallia. Suora pakkaus tehdään aritmeettisella koodauksella .

Malli

Lähdemalli ennustaa seuraavan bitin nykyisen kontekstin perusteella. Malli voidaan esittää graafina, jonka jokaisessa solmussa on kaksi laskuria: n 0 ja n 1 , jossa n 0 on bittilaskuri arvolla 0 ja n 1 on bittilaskuri, jonka arvo on 1. Yksi. solmuista on aina nykyinen. Yhtä nykyisen solmun laskureista kasvatetaan, kun alkuperäisessä datassa esiintyy vastaavan arvon omaava bitti. Solmulla on myös kaksi reunaa, jotka yhdistävät sen muihin solmuihin tai itseensä. Toista reunaa käytetään, kun lähdetiedoissa esiintyy 0, toista kun esiintyy 1. Yksinkertaisimmassa tapauksessa malli koostuu yhdestä itseensä viittaavasta solmusta. Tässä konfiguraatiossa malli pystyy lukemaan vain 0-arvoisten bittien määrän suhteessa niiden bittien lukumäärään, joiden arvo on 1, alkuperäisestä tiedosta. Kun mallissa on useampi kuin yksi solmu, niin seuraavaa bittiä prosessoitaessa voi tapahtua siirtyminen toiseen solmuun sekä uuden solmun muodostuminen.

Seuraava bitti ennustetaan laskemalla todennäköisyydet 0:lle kaavalla p 0 = n 0 / n = n 0 /( n 0 + n 1 ) ja vastaavasti 1:lle kaavalla p 1 = 1 − p 0 = n 1 / n . Siten jokainen solmu ilmentää mallin erillisen tilan, jossa se tekee erilaisia ​​ennusteita. DMC-mallin kontekstia ei eksplisiittisesti muisteta, vaan malli ottaa sen huomioon tilagraafin solmujen välisten siirtymien seurauksena.

Simulointi suoritetaan samalla tavalla sekä kompressiolle että dekompressiolle.

Muistiinpanot

1. ↑ Vatolin D. Tietojen pakkausmenetelmät. Arkistointilaite, kuvan ja videon pakkaus .. - M . : Dialog-MEPhI, 1993. - S. 9. - ISBN 5-86404-170-x .
2. ↑ Gordon Cormack ja Nigel Horspool, "Data Compression using Dynamic Markov Modeling", Computer Journal 30:6 (joulukuu 1987)