# Reversed Lempel-Ziv Factorization with Suffix Trees +
## 2 Preliminaries  
With \(\lg\) we denote the logarithm \(\log_{2}\) to base two. Our computational model is the word RAM model with machine word size \(\Omega(\lg n)\) for a given input size \(n\). Accessing a word costs \(\mathcal{O}(1)\) time. Let \(T\) be a text of length \(n-1\) whose characters are drawn from an integer alphabet \(\Sigma=[1\ldots\sigma]\) with \(\sigma=n^{\mathcal{O}(1)}\). Given \(X,Y,Z\in\Sigma^{*}\) with \(T=XYZ\), then \(X\), \(Y\) and \(Z\) are called a prefix, substring and suffix of \(T\), respectively. We call \(T[i\ldots]\) the \(i\)-th suffix of \(T\), and denote a substring \(T[i]T[i+1]\cdots T[j]\) with \(T[i\ldots j]\). For \(i>j\), \([i\ldots j]\) and \(T[i\ldots j]\) denote the empty set and the empty string, respectively. The reverse \(T^{\mathsf{R}}\) of \(T\) is the concatenation \(T^{\mathsf{R}}:=T[n-1]T[n-2]\cdots T[1]\). We further write \(T[i\ldots j]^{\mathsf{R}}:=T[j]T[j-1]\cdots T[j]\). \begin{table}
\begin{tabular}{l l l} \hline \hline \multicolumn{3}{l}{\((1+\epsilon)n\lg n+\mathcal{O}(n)\)**Bits of Working Space (Excluding the Read-Only Text \(T\))**} \\
**Reference** & **Type** & **Time** \\ \hline \hline
[21] ([Corollary 3.7]) & overlapping LZSS & \(\mathcal{O}(\epsilon^{-1}n)\) \\
[34] ([Lemma 6]) & LPF & \(\mathcal{O}(\epsilon^{-1}n)\) \\
[22] ([Theorem 1]) & non-overlapping LZSS & \(\mathcal{O}(\epsilon^{-1}n)\) \\
[22] ([Theorem 3]) & LPnF & \(\mathcal{O}(\epsilon^{-1}n)\) \\ \hline \hline \multicolumn{3}{l}{\(\mathcal{O}(\epsilon^{-1}n\lg\sigma)\)**Bits of Working Space**} \\
**Reference** & **Type** & **Time** \\ \hline \hline
[21] ([Corollary 3.4]) & overlapping LZSS & \(\mathcal{O}(\epsilon^{-1}n)\) \\
[34] ([Lemma 6]) & LPF & \(\mathcal{O}(\epsilon^{-1}n\log_{\sigma}^{\epsilon}n)\) \\
[22] ([Theorem 1]) & non-overlapping LZSS & \(\mathcal{O}(\epsilon^{-1}n\log_{\sigma}^{\epsilon}n)\) \\
[22] ([Theorem 3]) & LPnF & \(\mathcal{O}(\epsilon^{-1}n\log_{\sigma}^{\epsilon}n)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Complexity bounds of related approaches described in Section 1.2 for a selectable parameter \(\epsilon\in(0,1]\). Given a character \(c\in\Sigma\), and an integer \(j\), the rank query \(T\). \(\operatorname{rank_{c}}(j)\) counts the occurrences of \(c\) in \(T[1\dots j]\), and the select query \(T\). \(\operatorname{select_{c}}(j)\) gives the position of the \(j\)-th \(c\) in \(T\), if it exists. We stipulate that \(\operatorname{rank_{c}}(0)=\operatorname{select_{c}}(0)=0\). If the alphabet is binary, i.e., when \(T\) is a bit vector, there are data structures (35; 36) that use \(o(|T|)\) extra bits of space, and can compute rank and select in constant time, respectively. There are representations (37) with the same constant-time bounds that can be constructed in time linear in \(|T|\). We say that a bit vector has a rank-support and a select-support if it is endowed by data structures providing constant time access to rank and select, respectively. From now on, we assume that there exist two special characters \(\#\) and \(\$\) that do not appear in \(T\), with \(\$<\#<c\) for every character \(c\in\Sigma\). Under this assumption, none of the suffixes of \(T\cdot\#\) and \(T^{\mathsf{R}}\cdot\$\) has another suffix as a prefix. Let \(R:=T\cdot\#\cdot T^{\mathsf{R}}\cdot\$\). \(R\) has length \(|R|=2|T|+2=2n\). The suffix tree \(\mathsf{ST}\) of \(R\) is the tree obtained by compacting the suffix trie, which is the trie of all suffixes of \(R\). \(\mathsf{ST}\) has \(2n\) leaves and at most \(2n-1\) internal nodes. The string stored in a suffix tree edge \(e\) is called the label of \(e\). The children of a node \(v\) are sorted lexicographically with respect to the labels of the edges connecting the children with \(v\). We identify each node of the suffix tree by its pre-order number. We do so implicitly such that we can say, for instance, that a node \(v\) is marked in a bit vector \(B\), i.e., \(B[v]=1\), but actually have \(B[i]=1\), where \(i\) is the pre-order number of \(v\).