# Practical Grammar Compression Based on Maximal Repeats +
Footnote †: This paper is an extended version of our paper published in the Proceedings of the Data Compression Conference (DCC 2019), Snowbird, UT, USA, 26-29 March 2019.  
[PERSON]  
1 Graduate School of IST, Hokkaido University, N14-W9, Kitaku, Sapporo 060-0814, Japan; [EMAIL_ADDRESS] (T.T.); [EMAIL_ADDRESS] (T.K.)  
[PERSON]  
1 Graduate School of IST, Hokkaido University, N14-W9, Kitaku, Sapporo 060-0814, Japan; [EMAIL_ADDRESS] (T.T.); [EMAIL_ADDRESS] (T.K.)  
[PERSON]  
2 Department of Informatics, Kyushu University, 744, Motooka, Nishiku, Fukuoka 819-0395, Japan; [EMAIL_ADDRESS] (Y.N.); [EMAIL_ADDRESS] (S.L.); [EMAIL_ADDRESS] (H.B.)  
[PERSON]  
2 Department of Informatics, Kyushu University, 744, Motooka, Nishiku, Fukuoka 819-0395, Japan; [EMAIL_ADDRESS] (Y.N.); [EMAIL_ADDRESS] (S.L.); [EMAIL_ADDRESS] (H.B.)  
[PERSON]  
2  
[PERSON]  
1 Graduate School of IST, Hokkaido University, N14-W9, Kitaku, Sapporo 060-0814, Japan; [EMAIL_ADDRESS] (T.T.); [EMAIL_ADDRESS] (T.K.)  
[PERSON]  
2 Department of Informatics, Kyushu University, 744, Motooka, Nishiku, Fukuoka 819-0395, Japan; [EMAIL_ADDRESS] (Y.N.); [EMAIL_ADDRESS] (S.L.); [EMAIL_ADDRESS] (H.B.)  
[PERSON]  
2 Department of Informatics, Kyushu University, 744, Motooka, Nishiku, Fukuoka 819-0395, Japan; [EMAIL_ADDRESS] (Y.N.); [EMAIL_ADDRESS] (S.L.); [EMAIL_ADDRESS] (H.B.)  
[PERSON]  
2  
[PERSON]  
2  
[PERSON]  
1 Graduate School of IST, Hokkaido University, N14-W9, Kitaku, Sapporo 060-0814, Japan; [EMAIL_ADDRESS] (T.K.) [EMAIL_ADDRESS] (T.K.)  
[PERSON]  
2 Department of Informatics, Kyushu University, 744, Motooka, Nishiku, Fukuoka 819-0395, Japan; [EMAIL_ADDRESS] (T.K.)  
[PERSON]  
2 Department of Informatics, Kyushu University, 744, Motooka, Nishiku, Fukuoka 819-0395, Japan; [EMAIL_ADDRESS] (Y.N.); [EMAIL_ADDRESS] (S.L.); [EMAIL_ADDRESS] (H.B.)  
Ph  
In the field of text processing, the repetitiveness of a text is considered an important property. Furthermore, it has been suggested that the extent of the repetitiveness of a given text directly relates to the number of maximal repeats in the text. [PERSON] et al. (2013) demonstrated theoretical relations between the number of extensions of maximal repeats and famous other properties of text such as the number of factors in the Lempel-Ziv parsing and the number of runs in the Burrows-Wheeler transform. Also, several text indexing data structures, whose sizes are bounded by the number of extensions of maximal repeats, have been proposed in the literature ([PERSON], 1965; [PERSON], 1966; [PERSON], 1966).  
In this study, we analyzed the properties of RePair, focusing on their relationship to maximal repeats. Although RePair has been extensively studied, to the best of our knowledge, no previous study has associated RePair with maximal repeats. Furthermore, we propose MR-RePair, which is a novel grammar compression algorithm based on the property of maximal repeats. Several off-line grammar compression techniques based on the properties of (non-maximal) repeats have been proposed previously ([PERSON], 1966; [PERSON], 1966; [PERSON], 1966). Recently, [PERSON] and [PERSON] introduced a heuristic method that improves the practical compression ratio of RePair in terms of the grammar size ([PERSON] and [PERSON], 2016). However, none of the previously proposed methods use the properties of maximal repeats. In this study, we aim to demonstrate that there is a theoretical guarantee for the size of constructed grammars; under a specific condition, the size of the grammar constructed by MR-RePair is smaller than or equal to that constructed by RePair. Our experiments show that MR-RePair constructs smaller grammars compared to RePair. We emphasize that generating a grammar of small size is of great importance since most, if not all, existing algorithms/data structures that work on grammar-compressed texts have running time dependent on the grammar sizes (see e.g., ([PERSON], 1966; K