PPM model cleaning
Milenko Drinić, Darko Kirovski, Miodrag Potkonjak · 2003
The prediction by partial matching (PPM) algorithm uses a cumulative frequency count of input symbols in different contexts to estimate its probability distribution. Compression ratios yielded by the PPM algorithm have not instigated broader use of this scheme mainly because of its high demand for computational resources. An algorithm that improves the memory usage by the PPM model is presented. The algorithm identifies and removes portions of the PPM model, which are not contributing toward better modeling of the input data. As a result, our algorithm improves the average compression ratio up to 7% under the memory limitation constraint at the expense of increased computation. Under the constraint of maintaining the same level of compression ratios, the algorithm reduces the memory usage up to 70%.