Dynamic Markov compression: Difference between revisions

Revision as of 01:57, 6 May 2007

Revision as of 14:48, 28 May 2007

Line 1:

Dynamic Markov Compression (DMC) is a lossless [[data compression]] [[algorithm]] developed by [[Gordon Cormack]] and [[Nigel Horspool]] <ref>Gordon Cormack and Nigel Horspool, "Data Compression using Dynamic Markov Modelling", Computer Journal 30:6 (December 1987)</ref>. It uses predictive [[arithmetic coding]] similar to [[prediction by partial matching]] (PPM), except that the input is predicted one bit at a time (rather than one byte at a time). DMC has a good compression ratio and moderate speed, similar to PPM, but requires somewhat more memory and is not widely implemented. Some recent implementations include the experimental compression programs [http://cs.fit.edu/~mmahoney/compression/text.html#1781 hook] by Nania Francesco Antonio, [http://de.geocities.com/ocamyd/ ocamyd] by Frank Schwellinger, and as a submodel in [[PAQ|paq8l]] by Matt Mahoney. These are based on the [http://plg.uwaterloo.ca/~ftp/dmc/dmc.c 1993 implementation] in C by Gordon Cormack.

== Algorithm ==