## 3 Non-Overlapping LZSS
### The Factorization Algorithm  
All LZSS factorization algorithms of ([PERSON] et al. [4] [Section 3]) are divided into passes. A pass consists of visiting suffix tree leaves in text order (i.e., in order of their suffix numbers). On visiting a leaf, they conduct a leaf-to-root traversal. In what follows, we present our modification, which merely consists of a modification of Pass (a) in all LZSS factorization variants of ([4] [Section 3]): In Pass (a), [PERSON] et al. computed the factor lengths and the witnesses. To maintain the witnesses and lengths in future passes, they marked and stored the preorder numbers of the witnesses and the starting positions of the LZSS factors in two bit vectors \(B_{W}\) and \(B_{T}\), respectively. In succeeding passes, they computed, based on the factor lengths and the witnesses, the referred positions and with that the final coding. Therefore, it suffices to only change Pass (a) according to our definition of witnesses and factors, while keeping the subsequent passes untouched. In this pass, we do the following:  
* Create \(B_{W}\) and \(B_{T}\) to determine the witnesses and the factor lengths, respectively. The main technique of a pass in [4] are leaf-to-root traversals. Here, we do the opposite: We traverse from the root to a specific leaf. We perform a root-to-leaf traversal by level ancestor queries such that visiting a node takes constant time. We perform these traversals only for all _corresponding_ leaves since the other leaves are not useful for determining a factor. Suppose we visit a leaf \(\lambda\) corresponding to a factor \(F\). We already know the starting position of \(F\) (i.e., \(\mathsf{sfnum}(\lambda)\)), but not its length, referred position, or witness \(w\). To detect \(w\), we use the following observation: Given \(j_{u}\) is the smallest suffix number among all leaves in the subtree rooted at a node \(u\), \(w\) is the highest node that maximizes  
\[\ell_{w}\coloneqq\min(\mathsf{str\_depth}(w),\mathsf{sfnum}(\lambda)-j_{w}). \tag{1}\]  
If \(j_{w}=\mathsf{sfnum}(\lambda)\), then \(F\) is a fresh factor. Otherwise, \(w\) determines the length \(|F|=\ell_{w}\) and the referred position \(j_{w}\) of \(F\). However, the two functions \(v\mapsto\mathsf{str\_depth}(v)\) and \(v\mapsto\mathsf{sfnum}(\lambda)-j_{v}\) are strictly increasing and monotonically decreasing, respectively,when applied to each node \(v\) visited when walking downwards the path from the root to \(\lambda\). Thus, our goal is to find the lowest node \(u\), where the value \(\ell_{u}\) of Equation (1) still results from \(\text{str\_depth}(u)\), and not from the second argument \(\text{s\/\/\/num}(\lambda)-j_{u}\). We give a sketch in Figure 3 and study a particular case in Figure 4 for factors of Types 2 and 3. To achieve our goal, let \(\mathcal{I}_{v}\coloneqq[j_{v}\dots j_{v}+\text{str\_depth}(v)-1]\) and \(\mathcal{I}_{\lambda,v}\coloneqq[\text{s\/\/num}(\lambda)\dots\text{s\/\/num}( \lambda)+\text{str\_depth}(v)-1]\) be two intervals. These two intervals have the property that \(T[\mathcal{I}_{v}]=T[\mathcal{I}_{\lambda,v}]\). The idea is that \(T[\mathcal{I}_{\lambda,v}]\) is a candidate for \(F\) with \(T[\mathcal{I}_{v}]\) being its leftmost occurrence in \(T\). We compute the values of \(j_{v}\), \(\mathcal{I}_{v}\) and \(\mathcal{I}_{\lambda,v}\) for every node \(v\) on the path from the root to \(\lambda\) until reaching a node \(v\) such that the intervals \(\mathcal{I}_{v}\) and \(\mathcal{I}_{\lambda,v}\) overlap (cf. Line 9 in Algorithm 1). Let \(u\) be the parent of \(v\). Then, the edge \((u,v)\) determines the factor \(F\): We consider the following two cases that determine whether \(F\) is a fresh or referencing factor, and whether the witness and the referred position of \(F\) are \(u\) and \(j_{u}\), or \(v\) and \(j_{v}\), respectively, in case \(F\) is a referencing factor:  
Figure 4: Special case of the setting considered in Figure 3 for factors of Types 2 and 3.