Dynamic Markov compression

Dynamic Markov compression (DMC) is a lossless data compression algorithm developed by Gordon Cormack and Nigel Horspool. 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 hook by Nania Francesco Antonio, ocamyd by Frank Schwellinger, and as a submodel in paq8l by Matt Mahoney. These are based on the 1993 implementation in C by Gordon Cormack.

DMC predicts and codes one bit at a time. It differs from PPM in that it codes bits rather than bytes, and from context mixing algorithms such as PAQ in that there is only one context per prediction. The predicted bit is then coded using arithmetic coding.

A bitwise arithmetic coder such as DMC has two components, a predictor and an arithmetic coder. The predictor accepts an n-bit input string x = x₁x₂...x_n and assigns it a probability p(x), expressed as a product of a series of predictions, p(x₁)p(x₂|x₁)p(x₃|x₁x₂) ... p(x_n|x₁x₂...x_n–1). The arithmetic coder maintains two high precision binary numbers, p_low and p_high, representing the possible range for the total probability that the model would assign to all strings lexicographically less than x, given the bits of x seen so far. The compressed code for x is p_x, the shortest bit string representing a number between p_low and p_high. It is always possible to find a number in this range no more than one bit longer than the Shannon limit, log₂ 1/p(x'). One such number can be obtained from p_high by dropping all of the trailing bits after the first bit that differs from p_low.

...
Wikipedia