Word-Based Grammars for PPM

The Prediction by Partial Matching (PPM) compression algorithm is considered one of the most efficient methods for compressing natural language text. Despite the advances of the PPM method for the English language to predict upcoming symbols or words, more research is required to devise better compression methods for other languages, such as Arabic due, for example, to the rich morphological nature of the Arabic text, where a word can take many different forms. In this paper, we propose a new method that achieves the best compression rates not only for Arabic text but also for other languages that use Arabic script in their writing system such as Persian. Our word-based method constructs a context-free grammar (CFG) for the text and this grammar is then encoded using PPM to achieve excellent compression rates.

@article{Aljehane2017,
  title     = {Word-Based Grammars for PPM},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {8},
  number    = {10},
  year      = {2017},
  publisher = {The Science and Information Organization},
  author    = {Nojood O. Aljehane and William J. Teahan},
  doi       = {10.14569/IJACSA.2017.081037},
  url       = {https://doi.org/10.14569/IJACSA.2017.081037}
}