## 3 Off-Line Compression by Longest-First Substitution
### How to Update \(\mathit{SLSTree}(w_{k}^{i-1})\) to \(\mathit{SLSTree}(w_{k}^{i})\)
: Assume for contrary that there exists integer \(r\) such that \(r\in\mathit{Dead}_{w_{k}^{i}}(\mathit{str}(v))\) and \(m<r<n\). Since \(r\in\mathit{Dead}_{w_{k}^{i}}(\mathit{str}(v))\), there exist integers \(a,b\) such that \(a\leq r\leq b\), and \(b-a+1=2|\mathit{LRF}(w_{k})|\). For any integer \(j\) such that \(a\leq j\leq b\) and \(j\in\mathit{BP}_{w_{k}^{i-1}}(\mathit{str}(v))\), we have \(j\in\mathit{Dead}_{w_{k}^{i}}(\mathit{str}(v))\). Since \(m,n\
otin\mathit{Dead}_{w_{k}^{i}}(\mathit{str}(v))\), \(m<a<b<n\). As \(\mathit{str}(v)\) is non-repeating, \(n<m+\mathit{len}(v)-1\). Since \(m<a<b<m+\mathit{len}(v)-1\), \(w[a:b]\) is a factor of \(\mathit{str}(v)\). Therefore, there exist two integers \(a^{\prime},b^{\prime}\) such that \(w[a^{\prime}:b^{\prime}]=w[a:b]\). Since \(m<a<b<n<a^{\prime}<b^{\prime}<n+\mathit{len}(v)-1\), \(w[a:b]\) is repeating and \(|w[a:b]|=b-a+1=2|\mathit{LRF}(w_{k})|>|\mathit{LRF}(w_{k})|\). It contradicts that \(\mathit{LRF}(w_{k})\) is an LRF of \(w_{k}\). Recall that \(p\) is the beginning position of the \(i\)-th largest greedily selected occurrence of \(\mathit{LRF}(w_{k})\) in \(w_{k}\). Also, for any \(1\leq t\leq|\mathit{LRF}(w_{k})|\) such that \(w_{k}^{i-1}[r]\in\Sigma\) for every \(p-t\leq r<p\), we have removed \(\mathit{leaf}_{p-t}\) from the subtree rooted at the reference node \(v\) and have reconnected it to node \(s\) such that \(str(s)=w_{k}^{i}[p-t:p-1]\). According to the above lemma, if \(\min(v)<p-t<\max(v)\), \(\mathit{leaf}_{j}\) for every \(p-t\leq j\leq\max(v)\) is removed from the subtree of \(v\). After processing \(\mathit{leaf}_{p-t}\), then \(\max(v)\) is updated to \(p-t-d\) where \(d=(\min(v)+\max(v))/\mathrm{card}(v)\) is the step of the progression, and \(\mathrm{card}(v)\) is updated to \((\max(v)-(p-t))/d+1\). Notice that \(\mathit{leaf}_{p+h}\) for every \(0\leq h\leq|\mathit{LRF}(w_{k})|-1\) has to be removed from the tree, since \(w_{k}^{i}[p+h]\
otin\Sigma\) and therefore this leaf node should not exist in \(\mathit{SLSTree}(w_{k}^{i})\) (see the dark-shaded suffixes of Figure 3). Removing each leaf can be done in constant time. Maintaining the information about the triple for the arithmetic progression of the reference nodes can be done in the same way as mentioned above. The following lemma states how to locate each reference node. **Lemma 10**: _Let \(p\) be the \(i\)-th greedily selected occurrence of \(\mathit{LRF}(w_{k})\) in \(w_{k}\). For any integer \(\ell\) such that \(w_{k}^{i-1}[\ell]\in\Sigma\), let \(v(\ell)\) denote the reference node of \(\mathit{SLSTree}(w_{k}^{i-1})\) in the path from the root spelling out suffix \(w_{k}^{i-1}[\ell:]\). For each \(j\) such that \(p-|\mathit{LRF}(w_{k})|\leq j\leq p+|\mathit{LRF}(w_{k})|-1\), we can locate the reference node \(v(j)\) in amortized constant time._  
Figure 3:1 Illustration of proof for Lemma 9. Proof. : Let \(\ell=|\mathit{LRF}(w_{k})|\). We find \(v(p-\ell)\) by spelling out \(w_{k}^{i-1}[p-\ell\ :]\) from the root in \(O(\ell)\) time, since there can be at most \(\ell+1\) nodes in the path from the root to \(v(p-\ell)\). Suppose we have found \(v(j-1)\). We find \(v(j)\) as follows. Let \(u(j-1)\) be the parent node of \(v(j-1)\). We have \(\mathit{len}(u(j-1))\leq\ell\) and \(\mathit{len}(v(j-1))\leq\ell+1\). We go to \(\mathit{suf}(u(j-1))\). Since \(\mathit{len}(\mathit{suf}(u(j-1)))+1=\mathit{len}(u(j-1))\), we have \(\mathit{len}(\mathit{suf}(u(j-1)))\leq\ell+1\). Thus, we can find \(v(j)\) by going down the path starting from \(\mathit{suf}(u(j-1))\) and spelling out \(w_{k}^{i-1}[j-1+\mathit{len}(u(j-1)):j-1+\mathit{len}(v(j-1))]=w_{k}^{i-1}[j+ \mathit{len}(\mathit{suf}(u(j-1))):j-1+\mathit{len}(v(j-1))]\). (See also the left illustration of Figure 7). A special case happens when there exists a node \(s\) in the path from the root to \(\mathit{leaf}_{j}\), such that \(\mathit{len}(s)=\ell\) and the edge from \(s\) in the path starts with some non-terminal symbol \(A_{h}\) with \(h<k\). Namely, \(w_{k}^{i}[j+\ell]=A_{h}\).