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
Photo by Brett Jordan on Unsplash
Why is it important?
This is a novel grammar compression scheme, which has interesting properties and good practical results.
Perspectives
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:
Contributors
The following have contributed to this page
