Content deleted Content added
Sheep8144402 (talk | contribs) →Arithmetic coding: fix linter error (1x missing end tag) Tags: Mobile edit Mobile web edit Advanced mobile edit |
Adding short description: "Lossless data compression algorithm" |
||
| (One intermediate revision by one other user not shown) | |||
Line 1:
{{Short description|Lossless data compression algorithm}}
'''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, [https://web.archive.org/web/20091026235047/http://de.geocities.com/ocamyd/ ocamyd] by Frank Schwellinger, and as a submodel in [[PAQ|paq8l]] by Matt Mahoney. These are based on the [https://web.archive.org/web/20070630111546/http://plg.uwaterloo.ca/~ftp/dmc/dmc.c 1993 implementation] in C by Gordon Cormack.
Line 22 ⟶ 23:
Modeling is the same for compression and decompression. For each bit, ''p''<sub>0</sub> and ''p''<sub>1</sub> are computed, bit ''x''<sub>''i''</sub> is coded or decoded, the model is updated by adding 1 to the count corresponding to ''x''<sub>''i''</sub>, and the next context is found by traversing the link corresponding to ''x''<sub>''i''</sub>.
=== Adding new contexts ===
Line 94:
[[Category:Lossless compression algorithms]]
[[Category:Markov models]]
[[Category:Data compression]]
| |||