## 3 Off-Line Compression by Longest-First Substitution
### Reducing Grammar Size
```
Input: (w, LRFlen, nonTerm, gso, SLSTree, bins)
1 foreachocpos \(\in\) gso do
2 forpos \(=\) max\(\{1,\textsf{ococpos}-\textsf{LRFlen}\}\)to min\(\{|\textsf{w}|,\textsf{ococpos}+\textsf{LRFlen}-1\}\)do
3\(\textsf{v}:=\) find first node on path to leaf pos such that v.pathlen \(>\) LRFlen;
4 delete leaf pos; maintain v.card, v.min, v.max;
5 ifpos \(<\) occpos && notDead(pos)then
6\(\textsf{s}:=\) find/create node on path to leaf pos such that s.pathlen \(=\) occpos \(-\) pos;
7 ifs was newly createdthenbins(s.pathlen).addNode(s);
8 recreate leaf pos:\(\langle\)min, max, card\(\rangle=\langle\)pos, pos, \(1\rangle\); add edge (s, nonTerm, pos);
9 ifpos \(>\) occpos thenw( pos) \(=\) ; markDead(pos);
10w[occpos] \(:=\) nonTerm; markDead(occpos);
11
12 return
```  
**Algorithm 2**updateSLSTree  
```
Input: (w, LRFlen, nonTerm, gso, SLSTree, bins)
1 foreachocpos \(\in\) gso do
2 forpos \(=\) max\(\{1,\textsf{ococpos}-\textsf{LRFlen}\}\)to min\(\{|\textsf{w}|,\textsf{ococpos}+\textsf{LRFlen}-1\}\)do
3\(\textsf{v}:=\) find first node on path to leaf pos such that v.pathlen \(>\) LRFlen;
4 delete leaf pos; maintain v.card, v.min, v.max;
5 ifpos \(<\) occpos && notDead(pos)then
6\(\textsf{s}:=\) find/create node on path to leaf pos such that s.pathlen \(=\) occpos \(-\) pos;
7 ifs was newly createdthenbins(s.pathlen).addNode(s);
8 recreate leaf pos:\(\langle\)min, max, card\(\rangle=\langle\)pos, pos, \(1\rangle\); add edge (s, nonTerm, pos);
9 ifpos \(>\) occpos thenw( pos) \(=\) ; markDead(pos);
10w[occpos] \(:=\) nonTerm; markDead(occpos);
11
12 return
```  
**Algorithm 3**updateSLSTree  
```
Input: (w, LRFlen, nonTerm, gso, SLSTree, bins)
1 foreachocpos \(\in\) gso do
2 forpos \(=\) max\(\{1,\textsf{ococpos}-\textsf{LRFlen}\}\)to min\(\{|\textsf{w}|,\textsf{ococpos}+\textsf{LRFlen}-1\}\)do
3\(\textsf{v}:=\) find first node on path to leaf pos such that v.pathlen \(>\) LRFlen;
4 delete leaf pos; maintain v.card, v.min, v.max;
5 ifpos \(<\) occpos && notDead(pos)then
6\(\textsf{s}\) \(:=\) find/create node on path to leaf pos such that s.pathlen \(=\) occpos \(-\) pos;
7 ifs was newly createdthenbins(s.pathlen).addNode(s);
8 recreate leaf pos:\(\langle\)min, max, card\(\rangle=\langle\) pos, pos, \(1\rangle\); add edge (s, nonTerm, pos);
9 ifpos \(>\) occpos thenw( pos) \(=\) ; markDead(pos);
11 w[occpos] \(:=\) nonTerm; markDead(occpos);
12
13 return
```  
**Algorithm 4**updateSLSTree  
the total size of the grammar. In so doing, we consider an LRF of string \(z_{k}=w_{k}\$_{0}x_{1}\$_{1}\cdots x_{k}\$_{k}\), where \(z_{0}=w_{0}=w\) and each \(\$_{i}\) appears nowhere else in \(z_{k}\). _Example._ Let \(w=w_{0}=z_{0}=\texttt{abaaabbabb}\$_{0}\). We replace an LRF abb with \(A\), and obtain the following grammar: \(S\rightarrow\texttt{abaa}A\texttt{ab}A\$_{0}\); \(A\rightarrow\texttt{abb}\). Then, \(w_{1}=\texttt{abaa}A\texttt{ab}A\$_{0}\) and \(LRF(z_{0})=\texttt{abb}\). Now, \(z_{1}=\texttt{abaa}A\texttt{ab}A\$_{0}\)abb\$_{1}\). We replace an LRF ab of \(z_{1}\) with a non-terminal \(B\), getting \(S\to B\texttt{aa}ABA\$_{0}\); \(A\to B\texttt{b}\); \(B\rightarrow\texttt{ab}\). Then, \(w_{2}=B\texttt{aa}ABA\$_{0}\) and \(LRF(z_{1})=\texttt{ab}\). Now, \(z_{2}=B\texttt{aa}ABA\$_{0}B\$_{1}\texttt{ab}\$_{2}\). Since there is no LRF of length more than 1 in \(z_{2}\), we are done. We call this method of text compression _LFS2_. **Theorem 2**: _Given a string \(w\), the LFS2 strategy compresses \(w\) in linear time and space._  
Proof. : We modify the algorithm proposed in the previous sections. If we have a generalized SLSTree for set \(\{w_{k},x_{1}\$_{1},\ldots,x_{k}\$_{k}\}\) of strings, we can find an LRF of \(z_{k}=w_{k}x_{1}\$_{1}\cdots x_{k}\$_{k}\). It follows from the property of the longest first substitution strategy that \(|x_{i}|\geq|x_{j}|\) for any \(i<j\). Therefore, any new node inserted into the generalized SLSTree for \(\{w_{k}\), \(x_{1}\$_{0}x_{1}\$0_{k-1}\}\) is shorter than the reference nodes of the tree.