## 3 Off-Line Compression by Longest-First Substitution
### How to Find \(Lrf(w_{k})\) Using \(\mathit{SLSTree}(w_{k})\)
Given a node \(s\) in the bin-sorted list, we can determine whether \(\mathit{str}(s)\) is repeating or not by using \(\mathit{SLSTree}(w_{k})\), as follows. **Lemma 3**: _Let \(s\) be any node of \(\mathit{SLSTree}(w_{k})\) with \(\mathit{len}(s)\leq|\mathit{LRF}(w_{k})|\) and let \(s_{1},\ldots,s_{\ell}\) be the children of \(s\). Then \(\mathit{BP}_{w_{k}}(\mathit{str}(s))\) is a disjoint union of \(\mathit{BP}_{w_{k}}(\mathit{str}(s_{1})),\)\(\ldots,\)\(\mathit{BP}_{w_{k}}(\mathit{str}(s_{\ell}))\)._  
_Proof._ Clear from the definition of \(\mathit{SLSTree}(w_{k})\). \(\square\)  
**Lemma 4**: _For any node \(s\) of \(\mathit{SLSTree}(w_{k-1})\) such that \(|\mathit{LRF}(w_{k})|\leq\mathit{len}(s)\leq|\mathit{LRF}(w_{k-1})|\), it takes amortized constant time to check whether or not \(\mathit{str}(s)\) is an LRF of \(w_{k}\)._  
_Proof._ Let \(s_{1},\ldots,s_{\ell}\) be the children of \(s\). Then, \(\mathit{str}(s)\) is repeating if and only if  
\[\max\{\max\mathit{BP}_{w_{k-1}}(s_{i})\mid 1\leq i\leq\ell\}-\min\{\min \mathit{BP}_{w_{k-1}}(s_{j})\mid 1\leq j\leq\ell\}\geq\mathit{len}(s).\]  
Remark that the values of \(\min\mathit{BP}_{w_{k-1}}(s_{i})\) and \(\max\mathit{BP}_{w_{k-1}}(s_{i})\) are stored in node \(s_{i}\) and can be referred to in constant time. Since the above inequality is checked at most once for each node \(s\), it takes amortized constant time. \(\square\)  
Suppose we have found an LRF of \(w_{k}\) as mentioned above. In the sequel, we show our greedy strategy to select occurrences of the LRF in \(w_{k}\) to be replaced with a new non-terminal symbol. The next lemma is essentially the same as Lemma 2 of [PERSON] et al. [1]. **Lemma 5**: _For any non-repeating factor \(x\) of \(w_{k}\), \(\mathit{BP}_{w_{k}}(x)\) forms a single arithmetic progression._  
Therefore, for any non-repeating factor \(x\) of \(w_{k}\), \(\mathit{BP}_{w_{k}}(x)\) can be expressed by an ordered triple consisting of minimum element \(\min\mathit{BP}_{w_{k}}(x)\), maximum element \(\max\mathit{BP}_{w_{k}}(x)\), and cardinality \(\big{|}\mathit{BP}_{w_{k}}(x)\big{|}\), which takes constant space. **Lemma 6**: _Let \(s\) be any node of \(\mathit{SLSTree}(w_{k})\) such that \(\mathit{str}(s)\) is an LRF of \(w_{k}\), and \(s^{\prime}\) be any child of \(s\). Then, \(\mathit{BP}_{w_{k}}(\mathit{str}(s^{\prime}))\) contains at most two positions corresponding to non-overlapping occurrences of \(\mathit{str}(s)\) in \(w_{k}\)._  
Figure 2: Illustration for proof of Lemma 2. Since \(u\) is represented by a node of \(\mathit{SLSTree}(w_{k})\), we know that \(w_{k}[i+|u|]\
eq w_{k}[j+|u|]\). Proof. : Assume for contrary that \(\mathit{BP}_{w_{k}}(\mathit{str}(s^{\prime}))\) contains three non-overlapping occurrences of \(\mathit{str}(s)\), and let them be \(i_{1},i_{2},i_{3}\) in the increasing order. Then we have  
\[i_{3}-(i_{1}+\mathit{len}(s)-1)\geq i_{3}-i_{2}\geq\mathit{len}(s)\geq 1,\]  
which implies that \(w_{k}[i_{1}:i_{1}+\mathit{len}(s)]\) and \(w_{k}[i_{3}:i_{3}+\mathit{len}(s)]\) are non-overlapping. Moreover, since \(\mathit{len}(s^{\prime})>\mathit{len}(s)\), we have \(w_{k}[i_{1}:i_{1}+\mathit{len}(s)]=w_{k}[i_{3}:i_{3}+\mathit{len}(s)]\). However, this contradicts the precondition that \(\mathit{str}(s)\) is an LRF of \(w_{k}\). From Lemma 6, each child \(s^{\prime}\) of node \(s\) such that \(\mathit{str}(s)\) is an LRF, corresponds to at most two non-overlapping occurrences of \(\mathit{str}(s)\). Due to Lemma 3, we can greedily select occurrences of \(\mathit{str}(s)\) to be replaced by a new non-terminal symbol, by checking all children \(s_{1},\ldots,s_{\ell}\) of node \(s\). According to Lemma 5, it takes amortized constant time to select such occurrences for each node \(s\). Note that we have to select occurrences of \(\mathit{str}(s)\) so that no occurrences of \(\mathit{str}(s)\) remain in the text string, and at least two occurrences of \(\mathit{str}(s)\) are selected. We remark that we can greedily choose at least \(\max\{2,\#occ(\mathit{str}(s))/2\}\) occurrences.