Quantitative Aspects of Grammar-Based Compression

• Applicant: Professor Dr. Markus Lohrey
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 261105198

Grammar-based compression has been studied in the last two decades from a theoretical as well as practical point of view. Except for the family of Lempel-Ziv compressors, only few precisequantitative statements on the performance of grammar-based compressors are known. A good example are the so called global compressors (e.g. RePair) which show an excellent performance in practice, but which also exhibit a big gap between the known upper and lower bounds on the compression ratio. For grammar-based tree compressors the existing research gap is even larger. The main goal of the project is dithe development of new techniques for deriving precise quantitative statements on the compression ratio of grammar-based string and tree compressors. In this second project phase, the focus will be on the approximation ratio of global grammar-based compressors, and the analysis of grammar-based tree compressors. In particular, the average case analysis of the size of minimal DAGs (directed acyclic graphs) for trees with respect to various probability distributions will be studied in more detail. Universal tree compression is our main application of this research direction.

• DFG Programme: Research Grants