PPM: one step to practicality

PPM is one of the most promising lossless data compression algorithms using Markov source model of order D. Its main essence is the coding of a new (in the given context) symbol in one of inner nodes of the context tree; a sequence of the special escape symbols is used to describe this node. In reality, the majority of symbols is encoded in inner nodes and the Markov model becomes rather conventional. In spite of the fact that the PPM algorithm achieves the best results in comparison with others, it is used rarely in practical applications due to its high computational complexity. This paper is devoted to the PPM algorithm implementation that has a complexity comparable with widespread practical compression schemes based on LZ77, LZ78 and BWT algorithms. This scheme has been proposed by Shkarin (see Problems of Information Transmission, vol.34, no.3, p.44-54, 2001) and named PPM with information inheritance (PPMII).