## 1 Introduction  
Data compression is a task of reducing data description length. Not only does it enable us to save space for data storage, but also it reduces time for data communication. This paper focuses on text compression where the data to be compressed are texts (strings). Recent research developments show that text compression has a wide range of applications, e.g., pattern matching [1; 2; 3], string similarity computation [4; 5], detecting palindromic/repetitive structures [4; 6], inferring hierarchal structure of natural language texts [7; 8], and analyses of biological sequences [9].  
Grammar-based compression [10] is a kind of text compression scheme in which a context-free grammar (CFG) that generates only an input text \(w\) is output as a compressed form of \(w\). Since the problem of computing the smallest CFG which generates \(w\) is NP-hard [11], many attempts have been made to develop practical algorithms that compute a small CFG which generates \(w\). Examples of grammar-based compression algorithms are LZ78 [12], LZW [13], Sequitur [7], and Bisection [14]. Approximation algorithms for optimal grammar-based compression have also been proposed [15; 16; 17]. The first compression algorithm based on a subclass of context-sensitive grammars was introduced in [18].  
Grammar-based compression based on _greedy_ substitutions has been extensively studied. [PERSON] [19] introduced a concept of _most-frequent-first substitution_ (_MFFS_) such that a digram (a factor of length 2) which occurs most frequently in the text is recursively replaced by a new non-terminal symbol. He also presented an \(O(n^{2})\)-time algorithm for it, where \(n\) is the input text length. A linear-time algorithm for most-frequent-first substitution, called Re-pair, was later proposed by [PERSON] and [PERSON] [20]. [PERSON] and [PERSON] [21] proposed a concept of _largest-area-first substitution_ such that a factor of the largest \"area\" is recursively replaced by a new non-terminal symbol. Here the area of a factor refers to the product of the length of the factor by the number of its non-overlapping occurrences in the input text. It was reported in [22] that compression by largest-area-first substitution outperforms gzip (based on LZ77 [23]) and bzip2 (based on the Burrows-Wheeler Transform [24]) on DNA sequences. However, to the best of our knowledge, no linear-time algorithm for this compression scheme is known.  
This paper focuses on another greedy text compression scheme called _longest-first substitution_ (_LFS_), in which a longest repeating factor of an input text is recursively replaced by a new non-terminal symbol. For example, for input text \(w=\texttt{abaaabbabbabb}\$\), the following grammar  
\[S \rightarrow B\texttt{aa}ABA\$;\] \[A \rightarrow \texttt{abb};\] \[B \rightarrow \texttt{ab},\]  
which generates only \(w\) is the output of LFS.  
In this paper, we propose the _first linear-time algorithm_ for text compression by LFS substitution. A key idea is the use of a new data structure called _sparse lazy suffix trees_. Moreover, this paper deals with a more sophisticated version of longest-first text compression (named _LFS2_), where we also consider repeating factors of the right-hand of the existing production rules. For the same input text \(w=\texttt{abaaabbabbabb}\$\) as above, we obtain the following grammar:  
\[S \rightarrow B\texttt{aa}ABA\$;\] \[A \rightarrow B\texttt{b};\] \[B \rightarrow \texttt{ab}.\]  
This method allows better compression since the total grammar size becomes smaller. In this paper, we present the first linear-time algorithm for text compression based on LFS2. Preliminary versions of our paper appeared in [25] and [26].