## 3 Non-Overlapping LZSS
### Complexity Bounds
Here, we consider answering substring compression queries with the LZ78 factorization (which is actually also an SLP ([42] [Section VI.A.1])), i.e., the goal is to compress the substring \(T[\mathcal{I}]\) with LZ78. Let \(z_{78[\mathcal{I}]}\) denote the number of LZ78 factors of the string \(T[\mathcal{I}]\). When the text is given as an SLP of size \(g\), we can first transform this SLP into an SLP of \(T[\mathcal{I}]\) in \(\mathcal{O}(g)\) time, and then apply the algorithm of [PERSON] et al. [43] on this SLP to compute the LZ78 factorization in \(\mathcal{O}(g+z_{78[\mathcal{I}]}\lg z_{78[\mathcal{I}]})\) time. Let us consider from now on that \(T\) is given in its plain form as a string with \(n\lg\sigma\) bits. A possible way is to apply first a solution for computing an LZ77 substring compression query, and then transform the LZ77-compressed substring into an SLP of size \(\mathcal{O}(z_{58[\mathcal{I}]}\lg|\mathcal{I}|)\) in \(\mathcal{O}(z_{58[\mathcal{I}]}\lg|\mathcal{I}|)\) time by a transformation due to [PERSON] [44], to finally apply the aforementioned algorithm of [PERSON] et al. [43]. The fastest LZ78 factorization algorithms [4; 45] can answer a LZ78 substring compression query in \(\mathcal{O}(|\mathcal{I}|)\) time alphabet independently. For small alphabet sizes, the running time \(\mathcal{O}(|\mathcal{I}|(\lg\lg|\mathcal{I}|)^{2}/(\log_{\sigma}|\mathcal{I} |\lg\lg|\mathcal{I}|))\) of the LZ78 factorization algorithm of [PERSON] et al. [46] becomes even sub-linear in \(|\mathcal{I}|\). However, for large \(\mathcal{I}\) and a compressible text \(T\), these approaches are rather slow compared to the solutions for LZSS mentioned above, whose running times are bounded by the number of computed factors and a logarithmic multiplicative factor on the text length. To obtain similar bounds for LZ78, we could adapt the approach of [PERSON] et al. [36] to preprocess the LZ78 factorization of all suffixes of \(T\), but that would give us a data structure with super-linear preprocessing time (and possibly super-linear space). Here, we borrow the idea from [PERSON] et al. [45] to superimpose the suffix tree with the LZ78 trie, and use a data structure for answering nearest marked ancestor queries to find the lowest marked suffix tree node on the path from the root to a leaf. This data structure [47] takes \(\mathcal{O}(n\lg n)\) bits of space, and can answer a nearest marked ancestor query in \(\mathcal{O}(1)\) amortized time. We are unaware whether there are improvements for this type of query, even under the light that they only need to answer fringe marked ancestor queries, a notion coined by [PERSON] and [PERSON] [48], which is a special case of nearest marked ancestor queries:

Figure 6: Exponential search on a root-to-leaf path for the first node that does not meet a specific condition. In the setting of the non-overlapping LZSS factorization of Section 4 as well as in the LZ78 factorization of Section 4.5, the path from the root to a leaf \(\lambda\) contains a sub-path \(\pi\) including the root whose contained nodes all share a common property (for LZSS they meet the condition on Line 10 of Algorithm 1, while for LZ78 they are edge witnesses marked in the bit vector \(B_{E}\)). We symbolize the path from the root to \(\lambda\) as an array, where each node is represented by its depth. The sub-path \(\pi\) is visualized by the shaded entries. Here, the leaf \(\lambda\) has depth 18, and we want to find the first unshaded node on depth 15. The exponential search and the subsequent binary search in the range \([8\dots 16]\) is conducted by following the edges below and above the path array, respectively. ### Linear-Time Computation

Now, we can give our first result of Theorem 2 on the LZ78 substring compression query problem by a simple modification of the LZ78 factorization algorithm presented by [PERSON] et al. [45]. This algorithm uses a pointer-based suffix tree, which is augmented by a nearest marked ancestor data structure [47], using altogether \(\mathcal{O}(n\lg n)\) bits of space.