What is it about?

We build a grammar compressor, capable of compressing highly-repetitive texts using the factorization approach of inducing suffix order. The grammar is also capable of extracting substring without decompressing the entire text. Practical experiments show that the proposed grammar have interesting trade-offs regarding time and space when compared with other modern compressors designed for repetitive texts.

Featured Image

Why is it important?

This is a novel grammar compression scheme, which has interesting properties and good practical results.


This work can contribute with self-indices based on grammar compression and thus be capable of answering complex pattern matching queries in the compressed information using little space.

Daniel Saad

Read the Original

This page is a summary of: Grammar Compression by Induced Suffix Sorting, ACM Journal of Experimental Algorithmics, December 2022, ACM (Association for Computing Machinery),
DOI: 10.1145/3549992.
You can read the full text:



The following have contributed to this page