Editing Prediction by partial matching (section)

== Implementation ==

PPM compression implementations vary greatly in other details. The actual symbol selection is usually recorded using [[arithmetic coding]], though it is also possible to use [[Huffman encoding]] or even some type of [[dictionary coder|dictionary coding]] technique. The underlying model used in most PPM algorithms can also be extended to predict multiple symbols. It is also possible to use non-Markov modeling to either replace or supplement Markov modeling. The symbol size is usually static, typically a single byte, which makes generic handling of any file format easy.
<!-- Some PPM algorithms have the useful property of being able to interpret any collection of bytes as valid compressed input. An algorithm with this property is said to be bijective. Bijectiveness has positive implications for compression efficiency and security because there is no way to distinguish random data from valid output. [see talk page [[User:M.e|m.e.]] 10:34, 8 Oct 2004 (UTC)] -->

Published research on this family of algorithms can be found as far back as the mid-1980s. Software implementations were not popular until the early 1990s because PPM algorithms require a significant amount of [[Random Access Memory|RAM]]. Recent PPM implementations are among the best-performing [[lossless compression]] programs for [[natural language]] text.

PPMd is a public domain implementation of PPMII (PPM with information inheritance) by Dmitry Shkarin which has undergone several incompatible revisions.<ref>{{cite web |title=BMF, PPMd Всё о сжатии данных, изображений и видео |url=http://compression.ru/ds/ |website=compression.ru|language=ru}} NOTE: requires manually setting the "Cyrillic (Windows)" encoding in browser.</ref> It is used in the [[RAR (file format)|RAR]] file format by default. It is also available in the [[7z]]<!-- PPMd7 (rev H) & PPMd8 --> and [[zip (file format)|zip]]<!-- PPMd8 (rev I) --> file formats.

Attempts to improve PPM algorithms led to the [[PAQ]] series of data compression algorithms.

A PPM algorithm, rather than being used for compression, is used to increase the efficiency of user input in the alternate input method program [[Dasher (software)|Dasher]].