## 3 Off-Line Compression by Longest-First Substitution
### How to Update \(\mathit{SLSTree}(w_{k}^{i-1})\) to \(\mathit{SLSTree}(w_{k}^{i})\)  
Let \(L\) be the set of the greedily selected occurrences of \(\mathit{LRF}(w_{k})\) in \(w_{k}\). For any \(0\leq i\leq|L|\), let \(w_{k}^{i}\) denote the string obtained after replacing the first \(i\) occurrences of \(\mathit{LRF}(w_{k})\) with non-terminal symbol \(A_{k+1}\). Namely, \(w_{k}^{0}=w_{k}\) and \(w_{k}^{|L|}=w_{k+1}\). In this section we show how to update \(\mathit{SLSTree}(w_{k}^{i-1})\) to \(\mathit{SLSTree}(w_{k}^{i})\). Let \(p\) be the beginning position of the \(i\)-th occurrence in \(L\). Assume that we have \(\mathit{SLSTree}(w_{k}^{i-1})\), and that we have replaced \(w_{k}^{i-1}[p:p+|\mathit{LRF}(w_{k})|-1]\) with non-terminal symbol \(A_{k+1}\) such that \(|A_{k+1}|=|\mathit{LRF}(w_{k})|\). We now have \(w_{k}^{i}\), and we have to update \(\mathit{SLSTree}(w_{k}^{i-1})\) to \(\mathit{SLSTree}(w_{k}^{i})\). A naive way to obtain \(\mathit{SLSTree}(w_{k}^{i})\) is to remove all the suffixes of \(w_{k}^{i-1}\) from \(\mathit{SLSTree}(w_{k}^{i-1})\) and insert all the suffixes of \(w_{k}^{i}\) into it. However, since only the nodes not longer than \(\mathit{LRF}(w_{k})\) are important for our longest-first strategy, only the suffixes \(w_{k}^{i-1}[p-t:]\) such that \(1\leq t\leq|\mathit{LRF}(w_{k})|\) and \(w_{k}^{i-1}[r]\in\Sigma\) for any \(p-t\leq r<p\) have to be removed from \(\mathit{SLSTree}(w_{k}^{i-1})\), and only the suffixes \(w_{k}^{i}[p-t:]\) have to be inserted into the tree (see the light-shaded suffixes of Figure 3). **Lemma 7**: _For any \(t\), let \(r\) be the shortest node of \(\mathit{SLSTree}(w_{k}^{i-1})\) such that \(w_{k}^{i}[p-t:p-1]\) is a prefix of \(\mathit{str}(r)\). Assume \(p-t=\min\mathit{BP}_{w_{k}^{i-1}}(\mathit{str}(r))\)._  
1. _If_ \(\mathit{len}(r)>|\mathit{LRF}(w_{k})|+t-1\)_, then there exists an edge in_ \(\mathit{SLSTree}(w_{k}^{i})\) _from the root node to_ \(\mathit{leaf}_{p-t}\) _labeled with_ \(w_{k}^{i}[p-t:]\)_._
2. _If_ \(\mathit{len}(r)\leq|\mathit{LRF}(w_{k})|+t-1\)_, then there exists a node_ \(s\) _in_ \(\mathit{SLSTree}(w_{k}^{i})\) _such that_ \(\mathit{str}(s)=w_{k}^{i}[p-t:p-1]\) _and_ \(s\) _has an edge labeled with_ \(w_{k}^{i}[p:]=A_{k}w_{k}^{i}[p+|A_{k}|:]\) _and leading to_ \(\mathit{leaf}_{p-t}\)_._  
Proof. : Consider Case 1 (see also Figure 4). Since \(t\geq 1\), \(\mathit{len}(r)>|\mathit{LRF}(w_{k})|\). Hence \(\mathit{str}(r)\) is a non-repeating factor of \(w_{k}^{i}\). By Lemma 5, \(\mathit{BP}_{w_{k}^{i-1}}(\mathit{str}(r))\) forms a single arithmetic progression. Also, since \(\mathit{len}(r)>|\mathit{LRF}(w_{k})|\), \(\max\mathit{BP}_{w_{k}^{i-1}}(\mathit{str}(r))-\min\mathit{BP}_{w_{k}^{i-1}}( \mathit{str}(r))\leq|\mathit{LRF}(w_{k})|\). Therefore, if \(p-t=\min\mathit{BP}_{w_{k}^{i-1}}(\mathit{str}(r))\), then \(\mathit{BP}_{w_{k}^{i}}(w_{k}^{i}[p-t:])=\{p-t\}\). Hence there exists an edge from the root node to \(\mathit{leaf}_{p-t}\) labeled with \(w_{k}^{i}[p-t:]\) in \(\mathit{SLSTree}(w_{k}^{i})\). Consider Case 2 (see also Figure 5). Let \(u=w_{k}^{i-1}[p-t:p-1]=w_{k}^{i}[p-t:p-1]\). Then \(|u|=t-1\). Since \(\mathit{len}(r)\leq|\mathit{LRF}(w_{k})|+t-1\), and since \(r\) is not longer than the reference node in the path spelling out \(u\mathit{LRF}(w_{k})\) from the root node of \(\mathit{SLSTree}(w_{k}^{i})\), there exists at least one integer \(m\) such that \(m\in\mathit{BP}_{w_{k}^{i}}(\mathit{str}(r))\) and \(m\
otin\mathit{BP}_{w_{k}^{i}}(uA_{k})\). Hence there exists a node \(s\) in \(\mathit{SLSTree}(w_{k}^{i})\) such that \(\mathit{str}(s)=u\) and has an out-going edge labeled with \(w_{k}^{i}[p:]=A_{k}w_{k}^{i}[p+|A_{k}|:]\) and leading to \(\mathit{leaf}_{p-t}\). It is not difficult to see that the edge in each case of Lemma 7 does not exist in \(\mathit{SLSTree}(w_{k}^{i-1})\). Hence we create the edge when we update \(\mathit{SLSTree}(w_{k}^{i-1})\) to \(\mathit{SLSTree}(w_{k}^{i})\). The next lemma states how to locate node \(s\) of Case 2 of Lemma 7.