## 2 Preliminaries
### Data Structures  
Our text compression algorithm uses a data structure based on suffix trees [29]. The suffix tree of string \(w\), denoted by \(\mathit{STree}(w)\), is defined as follows:  
**Definition 1** (Suffix Trees): \(\mathit{STree}(w)\) _is a tree structure such that: (1) every edge is labeled by a non-empty factor of \(w\), (2) every internal node has at least two child nodes, (3) all out-going edge labels of every node begin with mutually distinct symbols, and (4) every suffix of \(w\) is spelled out in a path starting from the root node._  
Assuming any string \(w\) terminates with the unique symbol \(\$\) not appearing elsewhere in \(w\), there is a one-to-one correspondence between a suffix of \(w\) and a leaf node of \(\mathit{STree}(w)\). It is easy to see that the numbers of the nodes and edges of \(\mathit{STree}(w)\) are linear in \(|w|\). Moreover, by encoding every edge label \(x\) of \(\mathit{STree}(w)\) with an ordered pair \((i,j)\) of integers such that \(x=w[i:j]\), each edge only needs constant space. Therefore, \(\mathit{STree}(w)\) can be implemented with total of \(O(|w|)\) space. Also, it is well known that \(\mathit{STree}(w)\) can be constructed in \(O(|w|)\) time (e.g. see [29]).  
\(\mathit{STree}(w)\) for string \(w=\texttt{ababa}\$\) is shown in Figure 1. For any node \(v\) of \(\mathit{STree}(w)\), \(\mathit{str}(v)\) denotes the string obtained by concatenating the labels of the edges in the path from the root node to node \(v\). The _length_ of node \(v\), denoted \(\mathit{len}(v)\), is defined to be \(|\mathit{str}(v)|\). It is an easy application of the Ukkonen algorithm [29] to compute the lengths of all nodes while constructing \(\mathit{STree}(w)\). The leaf node \(\ell\) such that \(\mathit{str}(\ell)=w[i:]\) is denoted by \(\mathit{leaf}_{i}\), and \(i\) is said to be the _id_ of the leaf. Every node \(v\) of \(\mathit{STree}(w)\) except for the root node has a _suffix link_, denoted by \(\mathit{suf}(v)\), such that \(\mathit{suf}(v)=v^{\prime}\) where \(\mathit{str}(v^{\prime})\) is a suffix of \(\mathit{str}(v)\) and \(\mathit{len}(v^{\prime})+1=\mathit{len}(v)\). Linear-time suffix tree construction algorithms (e.g., [29]) make extensive use of the suffix links. Figure 1: \(\mathit{STree}(w)\) with \(w=\texttt{ababa}\$\). Solid arrows represent edges, and dotted arrows are suffix links. A _sparse suffix tree_[30] of \(w\in\Sigma^{*}\) is a kind of suffix tree which represents only a subset of the suffixes of \(w\). The sparse suffix tree of \(w\in(\Sigma\cup\Pi)^{*}\) represents the subset \(\{w[i\colon]\mid w[i]\in\Sigma\}\) of suffixes of \(w\) which begin with a terminal symbol. Let \(\ell\) be the length of the LRFs of \(w\). A _reference node_ of the sparse suffix tree of \(w\in(\Sigma\cup\Pi)^{*}\) is any node \(v\) such that \(len(v)\geq\ell+1\), and there is no node \(u\) such that \(str(u)\) is a proper prefix of \(str(v)\) and \(len(u)\geq\ell+1\). Our algorithm uses the following data structure. **Definition 2** (Sparse Lazy Suffix Trees): _A sparse lazy suffix tree (\(\mathrm{SLSTree}\)) of string \(w\in(\Sigma\cup\Pi)^{*}\), denoted by \(\mathit{SLSTree}(w)\), is a kind of sparse suffix tree such that: (1) All paths from the root node to the reference nodes coincide with those of the sparse suffix tree of \(w\), and (2) Every reference node \(v\) stores an ordered triple \(\langle\min(v),\max(v),\mathrm{card}(v)\rangle\) such that \(\min(v)=\min\mathit{BP}_{w}(\mathit{str}(v))\), \(\max(v)=\max\mathit{BP}_{w}(\mathit{str}(v))\), and \(\mathrm{card}(v)=\big{|}\mathit{BP}_{w}(\mathit{str}(v))\big{|}\)._  
\(\mathit{SLSTree}(w)\) is called \"lazy\" since its subtrees that are located below the reference nodes may not coincide with those of the corresponding sparse suffix tree of \(w\). Our algorithms of Section 3. run in linear time by \"neglecting\" updating these subtrees below the reference nodes.