DMC (kompresní algoritmus)

DMC ( dynamická Markovova komprese ,  dynamická Markovova komprese [1] ) je bezeztrátový algoritmus komprese dat vyvinutý Gordonem Cormackem a Nigelem Horspoolem [2] . Metoda je postavena podobně jako metoda PPM : samotný algoritmus je prediktor (vypočítává pravděpodobnosti symbolů) a přímá komprese je prováděna entropickým kodérem . Na rozdíl od PPM metoda DMC obecně funguje na bitové úrovni, zatímco PPM pracuje na úrovni bajtů. DMC poskytuje srovnatelné úrovně komprese a rychlost zpracování jako PPM, ale vyžaduje více paměti a není tak běžné jako PPM. Některé z moderních implementací jsou: hákový kompresor od Nania Francesco Antonio, kompresor ocamyd od Franka Schwellingera a DMC je použit jako jeden z modelů v kompresoru paq8l Matta Mahoneyho . Všechny uvedené kompresory jsou založeny na původní implementaci C z roku 1993 od Gordona Cormacka.

Algoritmus

DMC předpovídá a zakóduje jeden bit na logický krok operace. Od PPM se liší tím, že funguje na úrovni bitů, nikoli bajtů. Rozdíl od metod míchání kontextu (jako je PAQ ) je v tom, že DMC vytváří a používá jeden jediný zdrojový model. Přímá komprese se provádí pomocí aritmetického kódování .

Model

Zdrojový model předpovídá další bit na základě aktuálního kontextu. Model lze znázornit jako graf, jehož každý uzel obsahuje dva čítače: n 0 a n 1 , kde n 0 je bitový čítač s hodnotou 0 a n 1 je bitový čítač s hodnotou 1. Jeden z uzlů je vždy aktuální. Jeden z čítačů v aktuálním uzlu se zvýší, když je v původních datech nalezen bit s odpovídající hodnotou. Uzel má také dvě hrany, které jej spojují s jinými uzly nebo se sebou samým. Jedna z hran se používá, když se ve zdrojových datech vyskytuje 0, druhá, když se vyskytuje 1. V nejjednodušším případě se model skládá z jediného uzlu, který odkazuje sám na sebe. V této konfiguraci může model číst pouze poměr počtu bitů s hodnotou 0 k počtu bitů s hodnotou 1 v původních datech. Když je v modelu více než jeden uzel, pak při zpracování dalšího bitu může dojít k přechodu do jiného uzlu a také k vytvoření nového uzlu.

Další bit je predikován výpočtem pravděpodobností pro 0 pomocí vzorce p 0 = n 0 / n = n 0 /( n 0 + n 1 ) a podle toho pro 1 pomocí vzorce p 1 = 1 − p 0 = n 1 / n . Každý uzel tedy ztělesňuje samostatný stav modelu, ve kterém provádí různé predikce. Kontext v modelu DMC není explicitně zapamatován, ale je modelem zohledněn v důsledku přechodů mezi uzly stavového grafu.

Simulace se provádí stejným způsobem pro kompresi i dekompresi.

Poznámky

1. ↑ Vatolin D. Metody komprese dat. Zařízení archivátorů, komprese obrazu a videa .. - M . : Dialog-MEPhI, 1993. - S. 9. - ISBN 5-86404-170-x .
2. ↑ Gordon Cormack a Nigel Horspool, „Data Compression using Dynamic Markov Modeling“, Computer Journal 30:6 (prosinec 1987)