## 3 Non-Overlapping LZSS
### Complexity Bounds
The centroid path decomposition is helpful, because the number of light nodes on a path from the root to a leaf is \(\mathcal{O}(\lg n)\), which means that a path from the root to a leaf in \(\mathsf{cpST}\) contains\(\mathcal{O}(\lg n)\) nodes. This can be seen by the fact that the subtree size of a light node is at most half of the subtree size of its heavy sibling; thus, when visiting a light node during a top-down traversal in ST, we at least half the number of ST nodes we can visit from then on. Consequently, a root-to-leaf path in cpST has \(\mathcal{O}(\lg n)\) nodes. For that to be of use, we need a connection between ST and cpST: observe that the number of leaves and their respective order is the same in both trees, such that we can map leaves by their leaf-ranks in constant time. If we mark the light nodes in the suffix tree in a bit vector \(B_{L}\), then the rank of a light node \(v\) in \(B_{L}\) is the preorder number of the node in cpST representing the heavy path whose highest node is \(v\). To stay within our space budget, we represent the tree topology of cpST with a BP sequence (which we briefly introduced in Section 2). First, we mark all light nodes in \(B_{L}\) by an Euler tour, where we query the ST topology for the subtree size rooted at an arbitrary node in constant time. Next, we perform a depth-first search traversal on the suffix tree while producing the BP sequence of cpST. For that, we use a stack to store the light node ancestors of the currently visited node. Since a node has \(\mathcal{O}(\lg n)\) light nodes as ancestors, the stack uses \(\mathcal{O}(\lg^{2}n)\) bits of space. Finally, we endow \(B_{L}\) with a select-support such that we can map a node of cpST to its corresponding light node in ST.

Our algorithm conducting a pass works as follows: Suppose that we visit the leaf \(\lambda\) with suffix number \(\mathsf{b}(\mathcal{I})+|F_{1}|+\cdots+|F_{x-1}|\). This time, we map \(\lambda\) to the leaf \(\lambda^{\prime}\) of cpST having the same leaf-rank as \(\lambda\) in ST. Next, we apply the exponential search with \(d\mapsto\text{level\_anc}(\lambda^{\prime},d)\) on cpST, to obtain a cpST node representing the heavy path whose highest node is a light node \(v\), i.e., \(v\) is the lowest light node on the ST path from the root to the leaf \(\lambda\) that is an edge witness. Since a root-to-leaf path in ST has \(\mathcal{O}(\lg n)\) light nodes, we spend \(\mathcal{O}(\min(\lg|F_{x}|,\lg\lg n))\) time to find \(v\). Finally, it is left to move from \(v\) to the lowest edge witness on the path from \(v\) to \(\lambda\) in ST. For that, we use a dictionary \(\mathcal{D}\) that associates a light node with the number of edge witnesses in its heavy path. This number is at most \(z_{78|\mathcal{I}|}\leq|\mathcal{I}|\), and thus it can be stored in \(\lg|\mathcal{I}|\) bits, while a light node can be represented with its preorder number in \(\mathcal{O}(\lg n)\) bits. \(\mathcal{D}\) has to be dynamic since we do not know in advance which nodes will become edge witnesses; we can make use of one of the dynamic dictionaries given in Table 2, where \(t_{\mathcal{D}}\) denotes the time for an operation such as a lookup or an insertion and \(s_{\mathcal{D}}\) denotes the dictionary size in bits. Now, suppose that \(\mathcal{D}\) stores that \(d\) nodes in \(v\)'s heavy path are edge witnesses. Let \(w\) be the next light node on the path from \(v\) to \(\lambda\) (i.e., \(w\) is the highest light node on the path from the root to \(\lambda\) whose exploration counter is still zero). * If \(d-1\) is at least the height difference between \(v\) and \(w\), then the parent \(u\) of \(w\) is already an edge witness, and \(u\) is a node on the heavy path of \(v\). If the exploration counter of \(u\) is full, i.e., \(n_{u}=c(\text{parent}(u),u)\), then we increment the exploration counter of \(w\), and hence make \(w\) an edge witness and add \(w\) to \(\mathcal{D}\).