The Lyndon Array (LA) is an important data structure that gives the length of the longest Lyndon word starting at every position of a string S . LMS-based grammar compression consists of building a context-free grammar that generates only the input string, having LMS-substrings as the right side of the rules. In this paper, we show how to compute the LA during the decompression of GCIS (Nunes et al., ACM J. Exp. Algorithmics, 2022), an LMS-based compressor that achieves competitive compression ratios and is faster than popular grammar compressors. For highly repetitive sequences, GCIS grammars require only a small fraction of the input size. Although the algorithms we introduce in this paper are slower than the algorithm by Bille et al. (ICALP, 2020), when constructing the LA from compressed text one of our algorithms uses 20% less memory than first decompressing and then computing the LA. Apart from algorithmic interest, this work add tools for LA construction that enable selecting different tradeoffs between decompression space and time, preserving the advantages on disk storage and network bandwidth usage provided by GCIS, and may be particularly useful on very large datasets.

We introduce GCIS, a grammar compression algorithm based on the induced suffix sorting algorithm SAIS, presented by Nong et al. in 2009. Our solution builds on the factorization performed by SAIS during suffix sorting. We construct a context-free grammar on the input string which can be further reduced into a shorter string by substituting each substring by its corresponding factor. The resulting grammar is encoded by exploring some redundancies, such as common prefixes between suffix rules, which are sorted according to SAIS framework. When compared to well-known compression tools such as Re-Pair and 7-zip under repetitive sequences, our algorithm is faster at compressing and achieves compression ratio close to that of Re-Pair, at the cost of being the slowest at decompressing.