# Reversed Lempel-Ziv Factorization with Suffix Trees +
### Our Contribution  
The aim of this paper is to compute the reversed LZ factorization in less space while retaining the linear time bound. For that, we follow the idea of [PERSON] et al. (2014) ([Section 4]) who built text indexing data structures on \(T\cdot\#\cdot T^{\mathsf{R}}\) to compute \(\mathsf{LPnrF}\) for an artificial character \(\#\). However, they need random access to the suffix array, which makes it hard to achieve linear time for working space bounds within \(o(n\lg n)\) bits. We can omit the need for random access to the suffix array by a different approach based on suffix tree traversals. As a precursor of this line of research we can include the work of [PERSON] (1977) ([APL16]) and [PERSON] et al. (2018). The former studies the non-overlapping Lempel-Ziv-Storer-Szymanski (LZSS) factorization ([PERSON] and [PERSON], 1977; [PERSON], 1977) while the latter the Lempel-Ziv-78 factorization ([PERSON] and [PERSON], 1977). Although their used techniques are similar to ours, they still need \(\mathcal{O}(n\lg n)\) bits of space. To actually improve the space bounds, we follow two approaches: On the one hand, we use the leaf-to-root traversals proposed by [PERSON] et al. (2011) ([Section 3]) for the overlapping LZSS factorization ([PERSON] and [PERSON], 1977) during which they mark visited nodes acting as signposts for candidates for previous occurrences of the factors. On the other hand, we use the root-to-leaf traversals proposed in ([PERSON] and [PERSON], 1977) for the leaves corresponding to the text positions of \(T\) to find the lowest marked nodes whose paths to the root constitute the lengths of the non-overlapping LZSS factors. Although we mimic two approaches for computing factorizations different to the reversed LZ factorization, we can show that these traversals on the suffix tree of \(T\cdot\#\cdot T^{\mathsf{R}}\) help us to detect the factors of the reversed LZ factorization. Our result is as follows:  
**Theorem 1**. : _Given a text \(T\) of length \(n-1\) whose characters are drawn from an integer alphabet with size \(\sigma=n^{\mathcal{O}(1)}\), we can compute its reversed LZ factorization_  
* _in_ \(\mathcal{O}(\epsilon^{-1}n)\) _time using_ \((2+\epsilon)n\lg n+\mathcal{O}(n)\) _bits (excluding the read-only text_ \(T\)_), or_
* _in_ \(\mathcal{O}(\epsilon^{-1}n)\) _time using_ \(\mathcal{O}(\epsilon^{-1}n\lg\sigma)\) _bits,_  
_for a selectable parameter \(\epsilon\in(0,1]\)._  
On the downside, we have to admit that the results are not based on new tools, but rather a combination of already existing data structures with different algorithmic ideas. On the upside, Theorem 1 presents the first linear-time algorithm computing the reversed LZ factorization using a number of bits linear to the input text \(T\), which is \(o(n\lg n)\) bits for \(\lg\sigma=o(\lg n)\). Interestingly, this has not yet been achieved for the seemingly easier non-overlapping LZSS factorization, for which we have \(\mathcal{O}(\epsilon^{-1}n\lg\sigma^{c}_{\sigma}n)\) time within the same space bound ([PERSON] and [PERSON], 1977) ([Theorem 1]). We can also adapt the algorithm of Theorem 1 to compute \(\mathsf{LPnrF}\), but losing the linear time for the \(\mathcal{O}(n\lg\sigma)\)-bits solution:  
**Theorem 2**. : _Given a text \(T\) of length \(n-1\) whose characters are drawn from an integer alphabet with size \(\sigma=n^{\mathcal{O}(1)}\), we can compute a 2n-bits representation of its longest previous non-overlapping reverse factor table \(\mathsf{LPnrF}\)_  
* _in_ \(\mathcal{O}(\epsilon^{-1}n)\) _time using_ \((2+\epsilon)n\lg n+\mathcal{O}(n)\) _bits (excluding the read-only text_ \(T\)_), or_
* _in_ \(\mathcal{O}(\epsilon^{-1}n\log^{c}_{\sigma}n)\) _time using_ \(\mathcal{O}(\epsilon^{-1}n\lg\sigma)\) _bits,_  
_for a selectable parameter \(\epsilon\in(0,1]\).