1 Introduction↩︎

The natural approach to compressing data is to identify its repeating fragments. Then, for every subsequent occurrence of such a fragment, instead of spelling it out explicitly again, we can write down a pointer to the previous occurrence. This is the underlying high-level idea of the well-known Lempel-Ziv compression scheme [1] used in popular compressors such as ZIP, gzip, RAR, PKZIP, and PNG.

While being able to compress the input to obtain its hopefully significantly smaller compressed representation that can be still decompressed to obtain the original input is already interesting, in most applications we would actually prefer to avoid the decompression and instead directly operate on the compressed representation. Ideally, we would like to augment the compressed representation with a data structure of roughly the same size that allows querying the original input. We refer to Navarro’s survey [2] for an overview of such results for different compression methods. While the ultimate goal is designing a compressed index, which is a data structure that allows for efficient pattern matching queries  [3]–[10], the first step (and in fact an important building block in many of the compressed indexes) is a compressed random access structure.

A compressed random access structure for a string \(S[1..n]\) should use space roughly proportional to the size of the compressed representation of the input and allow for extracting any character \(S[i]\) efficiently. Ideally, we would like such a query to take logarithmic time in the length of the string. Whether this is known to be possible depends on the chosen compression method.

A Lempel-Ziv (LZ77) representation of a string \(S[1..n]\) is a factorization of the string into \(z\) blocks called phrases: \(S[1..n] = P_{1} P_{2} \dots P_{z}\). Each phrase \(P_{i}\) is either a single character, that is, \(|P_{i}|=1\), or has an earlier occurrence in \(S\). This allows us to encode each phrase is constant space by either specifying its only character, or the position and the length of the previous occurrence. It is known [11] that greedily choosing each phrase to be as long as possible results in the smallest number of phrases. A related (provably weaker, but easier to operate on) compression method is a straight-line program (SLP) representation, which is simply a context-free grammar with exactly one production for each non-terminal that derives exactly one string \(S\). It can be seen that an SLP consisting of \(g\) productions can be converted into a LZ77 parse of size \(g\). In the other direction, Charikar et al. [12] and Rytter [13] independently established that a LZ77 parse of size \(z\) can be converted into a SLP consisting of \(O(z\log(n/z))\) productions. In fact, the obtained SLP is balanced, meaning that the depth of the derivation tree is \(O(\log n)\). This has the advantage of automatically providing a compressed random access structure with query time \(O(\log n)\) and size \(O(z\log(n/z))\), which simply operates by descending down in the grammar. Verbin and Yu [14] proved that, roughly speaking, this is very close to optimal. Namely, any structure of size \(O(z\mathop{\mathrm{polylog}}n)\) must have \(\Omega(\log n/\log\log n)\) query time, for the case where \(n=z^{1+\epsilon}\). This however does not exclude the possibility of providing a compressed random access structure with size roughly proportional to the size of the compressed representation and, say, logarithmic query time.

This goal has been in fact achieved for grammar compression. Bille et al. [15] showed that, assuming the Word RAM model, given a SLP representation of size \(g\) representing a string \(S[1..n]\), we can build a data structure of size \(O(g)\) that supports random access queries in \(O(\log n)\) time. Later, Ganardi, Jeż, and Lohrey [16] showed a stronger version of this statement: any SLP of size \(g\) representing a string \(S[1..n]\) can be converted into a balanced SLP of size \(O(g)\) representing the same string. This can be seen as the ultimate random access structure for SLPs, although the lower bound of Verbin and Yu [14] still leaves the possibility of designing a structure of size \(O(g)\) and allowing random access in optimal \(O(\log n/\log\log n)\) time. Somewhat surprisingly, the best known bounds for a LZ77 compressed random access structure follow by converting the LZ77 parse to a grammar, and achieve \(O(z\log(n/z))\) space with \(O(\log \frac{n}{z})\) query time (see [17] for an alternative solution achieving the same time-space bounds). The logarithmic space increase is a major drawback of such a solution: after all, the compression ratio might actually be of a similar magnitude (as is the case for a random input), so by building such a structure we are not benefiting at all from using a compressed representation. Fully understanding the complexity of random access for LZ77 compressed strings remains to be a major open problem in the area.

Motivated by the lack of progress on understanding the complexity of random access for LZ77 compressed strings, Kreft and Navarro [6] introduced a restricted variant of LZ77, called LZ-End, in which the previous occurrence of each phrase needs to end at a phrase boundary. With this restriction, the greedy parsing is not necessarily optimal. However, finding the optimal LZ-End parsing of a string was shown to be NP-hard [18], when the greedy parse can be found efficiently [19], and still behaves very well in practice [20]. While already the original paper established that extracting substrings ending at a boundary can be done efficiently with only \(O(z)\) space for LZ-End parse consisting of \(z\) phrases (in fact, this can be seen as the reason for restricting the parsing in such a way), it was not known whether LZ-End admits better compressed random access structures than that of a LZ77 until 10 years later Kempa and Saha [21] showed that, in fact, LZ-End does admit a data structure of size \(O(z)\) that supports random access queries in polylogarithmic time. However, their construction has two major drawbacks.

1. The original proof is purely existential: that is, they only showed that, for any string \(S[1..n]\), there exists a data structure of size \(O(z)\) with polylogarithmic query time. The construction crucially uses probabilistic method, so we can either verify whether the obtained data structure is correct after construction, or we can compromise on a data structure for which the bound on the query time holds with high probability.

2. The guarantee on the query time in the original proof, while polylogarithmic, is actually quite high: \(O(\log^{4}n\cdot \log\log n)\). This should be compared with the only known lower bound, which is \(\Omega(\log n/\log\log n)\) for structures of size \(O(z\mathop{\mathrm{polylog}}n)\). Further, the time-space product of the original structure (a natural measure for data structures) is as high as \(O(z\log^{4}n\cdot\log\log n)\), while for the LZ77 compression it is a much more reasonable \(O(z\log^{2}(n/z))\).

1.0.0.1 Our results.

Our contribution is twofolds. First, we adapt the high-level idea used by Kempa and Saha to obtain, for a string of length \(n\) described by a LZ-End parse consisting of \(z\) phrases, a random access structure of size \(O(z)\) and polylogarithmic query time that can be constructed deterministically in \(\tilde{O}(z)\) time. As explicitly mentioned by Kempa and Saha, their data structure can be either constructed in expected \(O(\mathop{\mathrm{poly}}(n))\) time with worst-case queries or in worst-case \(O(\mathop{\mathrm{poly}}(n))\) time with expected-time queries. Thus, we not only completely remove the randomization, but further bring down the construction time to depend on the size of the compressed representation of the text instead of its length. Second, with further combinatorial insight we are able to significantly improve the query time, which was as high as \(O(\log^{4}n\cdot \log\log n)\) in the original construction. More specifically, our query time is only \(O(\log^{2}(\frac{n}{z}))\).

We note that the time-space tradeoff of our structure is \(O(z\log^{2}(\frac{n}{z}))\), which matches the best known tradeoffs for the LZ77 random access structure.

Our techniques can be applied and enhanced to additionally support the stronger substring extraction query.

2 Preliminaries↩︎

2.0.0.1 Integer intervals.

We use standard notation to denote consecutive sets of integers. For integers \(i,j\), we denote \([i..j] = \{i,i+1,\ldots, j \}\) (if \(j < i\) then \([i..j] = \emptyset\)). We also denote \([i] = [1..i]\), and \((i..j)=(i..j-1]=[i+1..j)=[i+1..j-1]\).

2.0.0.2 Strings.

A string \(S\) with length \(n\) over alphabet \(\Sigma\) is a sequence of symbols \(S[1]S[2] \ldots S[n]\) where \(S[i] \in \Sigma\) for every \(i\in [n]\). For integers \(i,j \in [n]\) we denote \(S[i..j]=S[i]S[i+1]..S[j]\). We call \(S[i..j]\) a substring of \(S\).

2.0.0.3 LZ-End factorization.

An LZ-End factorization of a string \(S[1..n]\) is a partition of \(S\) into substrings \(P_1,P_2,\ldots P_z\) called phrases. For each \(i\), we have \(P_i=S[a_i..b_i]\), with \(a_1 = 1\), \(b_z=n\), and \(a_i = b_{i-1} + 1\) for every \(i \in (1..z]\). Each phrase satisfies one of the following conditions. Either \(P_i\) is a phrase of length one, i.e. \(P_i = S[a_i]\), we call such a phrase a terminal phrase. Or, \(P_i = S[a_i..b_i]\), and there is some reference phrase \(P_j\) with \(j<i\) such that \(S(b_j - |P_i|..b_j] = P_i\). We call such a phrase a reference phrase, and say that \(P_j\) is the source of \(P_i\). When we are given an LZ-End factorization, we assume that every reference phrase \(P_i\) is given alongside the index \(j\) of its source phrase. We stress that, in contrast to prior work [21], we are not requiring that the given parsing is greedy, that is, it is not necessarily the case that every \(P_{i}\) is the longest phrase that occurs earlier ending at a phrase boundary.

In 9, we show that any LZ-End factorization with \(z\) phrases of a string with length \(n\) can be efficiently transformed into a similar size LZ-End factorization of the same string, with all the phrases having size at most \(\frac{n}{z}\).

Throughout the paper, we often partition integer from \([0..\frac{n}{z}]\) into exponential levels. We fix the notation \(\mathbb{K}=\{ 1.5^i \mid i\in [0..\log_{1.5}\frac{n}{z}]\}\) for the set of integer powers of \(1.5\) smaller than \(\frac{n}{z}\).

2.0.0.4 Computational model.

We describe our algorithm in the standard Word RAM model, see e.g. [22]. We assume that \(n\) fits in a single machine word, and basic arithmetical operations on numbers that fit in a constant number of machine words take constant time. In particular, constant-time indirect addressing is available, allowing us to implement arrays with constant lookup time. In this model, we have the following result (called deterministic perfect hashing).

3 Framework and Overview↩︎

Let us start by establishing notation and terminology to be used for the rest of this section. We are given as input an LZ-end factorization \(\mathcal{Z}=P_1,P_2,\ldots, P_z\) of string \(S\) with length \(n\). Each phrase is given with its endpoints \(a_i\) and \(b_i\) such that \(P_i = S[a_i..b_i]\). Additionally, each phrase \(P_i\) with length at least \(2\) is given with the index \(j<i\) such that \(P_j\) is the source of \(P_i\). For every index \(i\in[1..n]\) in the text, we denote as \(r_i\) and \(\ell_i\) the distance to the closest phrase boundary to the right of \(i\) and to the left of \(i\), respectively. Formally, if the phrase containing index \(i\) is \(P=S[a..b]\), then \(r_i = b-i\) and \(\ell_i = i-a\). We call \(r_i\) and \(\ell_i\) the \(r\)-value and the \(\ell\)-value of \(i\), respectively.

3.1 Intuition and High-level Approach↩︎

Let us first describe the approach of Kempa and Saha [21]. We are storing an array \(B\) with \(B[i] = S[b_i]\) for every \(i\in [z]\). For an index \(i\in [n]\) with \(r_i = 0\), we have that \(i = b_j\) for some \(j\in [z]\) and we can output \(S[i] = B[j]\). Our goal is to reduce an arbitrary index \(i\in [n]\) given at query time to an index \(i' \in [n]\) with \(r_{i'} = 0\) and \(S[i] = S[i']\). Kempa and Saha [21] achieve this goal by defining a ‘step’ rule \(N(i)\) for every index \(i\in [n]\). This step rule maps \(i\) with \(r_i > 0\) to another index \(N(i)<i\) such that \(S[i] = S[N(i)]\). The rule defined by Saha and Kempa is both compactly computable and terminates quickly. By compactly computable, we mean that there is a data structure with size \(O(z)\) that allows computing \(N(i)\) in polylogarithmic time. By terminates quickly, we mean that for every \(i\in [n]\), repeatedly applying \(N(i),N^2(i),\ldots\) will result in some index \(i'\) with \(r_{i'}=0\) after a polylogarithmic number of steps. It should be clear that given such a step rule, one can support random access in \(O(z)\) space and polylogarithmic time.

We provide a high level description of the step rule of [21]. The step function \(N\) is a composition of three different functions: \(J\), \(sJ\), and \(M\) ("Jump", "Stable Jump", and "Marked"). The function \(J\) is defined for every index \(i\in [n]\) with \(r_i > 0\), while \(sJ\) and \(M\) are only defined for a strict subset of those indices. For an index \(i\) with \(r_i > 0\), we will prioritize using \(M(i)\) as the step from \(i\), i,e, we have \(N(i)=M(i)\) if \(M(i)\) is defined. Otherwise, we set \(N(i) = sJ(i)\), and only if both \(M(i)\) and \(sJ(i)\) are undefined, we have \(N(i)=J(i)\).

Consider a sequence \(i,N(i),N^2(i),\ldots\) of \(N\) steps. Each of \(J\), \(sJ\), and \(M\) have a particular role in guaranteeing that this sequence quickly converges to an index \(i'\) with \(r_{i'}=0\). This goal is achieved in \(O(\log n)\) step sequences called epochs. An epoch is a subsequence of \(N\) steps such that at the end of the epoch, the \(r\)-value is in a smaller exponential level than the one seen at the start of the epoch. Since initially \(r_i\le n\), after applying \(O(\log n)\) epochs we reach an index with \(r\)-value \(0\) as required. Let us formally define the goal of the epoch. We fix the set \(\mathbb{K}_n = \{1.5^k \mid k \in [0..\log_{1.5}n] \}\) of integer powers of \(1.5\) smaller than \(n\). An epoch starts at an index \(i\) that has \(r_i \in [k..1.5k)\) for some \(k\in \mathbb{K}_n\), and ends upon reaching an index \(j\) with \(S[i] =S[j]\) and \(r_{j}<k\).

Let us describe the role of each function in an epoch. First of all, all the functions share the property of being \(r\)-non increasing. That is, we will have \(r_{F(i)}\le r_i\) for every \(F\in \{J,sJ,M\}\) for which \(F(i)\) is defined.

The function \(J\) will act as a naive ‘searching’ step. It transforms \(i\) into an index to the left of \(i\), without increasing the \(r\)-value and while maintaining \(S[i] = S[J(i)]\). We are not guaranteed to have any progress towards lowering the value of \(r\) when using \(J\), but we ‘hope’ that by repeatedly applying \(J\), we will eventually reach an index for which \(M\) is defined. We call the part of the epoch before \(M\) is activated for the first time the naive jumping part.

The function \(M\) has the role of a trigger function and a progress function, and it has a symbiotic relationship with \(sJ\). By trigger, we mean that after \(M(i)\) applies, the naive jumping part of the epoch ends, and it enters a different state called the stable part. The epoch remains in the stable part until the end of the epoch. During the stable part, all \(N\) steps are guaranteed to be either \(M\) or \(sJ\) until we will eventually reach some index \(i'\) with \(r_{i'} < \frac{2}{3}r_i\), finishing the epoch.

When we say that \(M\) is a progress function, we mean that \(M(i)\) is guaranteed to have a significantly reduced \(\ell\)-value or a significantly reduced \(r\)-value. Namely, it holds that \(\min(r_{M(i)},\ell_{M(i)})\le \min(r_i/2,\ell_i /2)\). Following this notion, we call an index \(i\) for which \(M(i)\) is defined a progress index.

The key property of \(sJ\) is that it is \(\ell\)-non-decreasing, in the following sense. For every index \(i\) for which \(j=sJ(i)\) is defined, either \(\ell_j\le \ell_i\) or \(r_j < \frac{2}{3}r_{i}\). Notice that in the latter case, the epoch is finished. In words, \(sJ\) guarantees that in each step we either do not increase \(\ell\), or we achieve the end of the epoch. We note that the function \(M\) also has this property.

We have that throughout the stable part, both \(r\) and \(\ell\) values are non-increasing. Furthermore, every time we reach a progress index, we have that \(r\) or \(\ell\) are reduced by a constant factor. Since \(\ell_i \le n\), it can only be reduced by a constant factor \(O(\log n)\) times throughout the epoch. It follows that after visiting \(O(\log n)\) progress indices, we will finally reach some \(i'\) with \(r_{i'}<\frac{2}{3}r_i\), finishing the epoch.

The last important property of \(M\) is the property of being common. That is, for every index \(i\), it is guaranteed that withing a polylogarithmic number of \(N\) steps, we reach a progress index.

Therefore, we are guaranteed to reach a progress index after a polylogarithmic number of steps, triggering the start of the stable part. The epoch ends after we visit \(O(\log n)\) progress indices, and we reach a new progress index every polylogarithmic number of steps. It follows that the epoch ends within a polylogarithmic number of steps.

3.1.0.1 Implementing \(J\), \(sJ\), and \(M\).

The implementation of \(M\) follows from a well-known approach from random access on Lempel-Ziv compressed strings. A phrase \(P = S[a..b]\in \mathcal{Z}\) can be processed such that every index \(i\in [a..b]\) is mapped to an index \(j\) with \(S[j]=S[i]\), and either \(\min(r_j,\ell_j) \le \min(r_i/2,\ell_i/2)\) (and in either case, \(r_j \le r_i\)). However, in order to support an \(O(1)\) computation of this mapping, one needs to use \(O(\log n)\) space.

The \(O(\log n)\) in the space complexity for supporting \(M\) arises from a partition of \(P\) into \(\Theta(\log |P|)\) intervals. For each interval, the data structure stores \(O(1)\) space to support computing \(M\) for indices in this interval. Kempa and Saha choose one random interval from each phrase, thus supporting the computation of \(M\) only with probability \(1/\log n\) for an index in \(P\). By making this compromise, they reduce the space consumption per phrase to \(O(1)\). It should be easy to see that if we design \(N\) to always move between phrases (i.e, \(N(i)\) is always in a phrase to the left of the phrase containing \(i\)), the common property of \(M\) is satisfied with high probability (with an appropriate choice of a polylogarithmic function).

\(J\) is the simplest function to implement: for every index \(i\) contained in a phrase \(P=S[a..b]\) with source \(S[a'..b']\), we define \(J(i) = i-b+b'\). Notice that this maps \(i\) to the index aligned with \(i\) in \(S[b'- |P|+1..b'] = P\), so we have both \(S[i] = S[J(i)]\) and \(r_{J(i)}\le r_i\).

In order to define the function \(sJ\), Kempa and Saha introduce the \(\mathsf{pre}\) function. The function \(\mathsf{pre}(b,e)\) receives two parameters \(b,e\) representing an interval of indices within \(S\). The output of the function corresponds to result of the following process: check if \(b\) and \(e\) are contained in the same phrase of \(\mathcal{Z}\). If they are not then return \(b\). Otherwise, replace \((b,e)\) with \((J(b),J(e))\) and repeat. Intuitively, one can think of \(\mathsf{pre}(b,e)\) as a pointer to an occurrence \(S[b'..e']\) of \(S[b..e]\) that is achieved by following the source links of \(\mathcal{Z}\) (potentially many times), and contains a phrase boundary. In order to support efficient computation of \(sJ(i)\), the data structure of Kempa and Saha stores \(\mathsf{pre}(b,e)\) values for \(O(z)\) pairs \((b,e)\).

3.1.0.2 The challenges of constructing [21].

We wish to provide an efficient, deterministic construction based on the ideas of Kempa and Saha. There are two primary obstacles.

Firstly, the construction of Kempa and Saha requires computing \(O(z)\) values of \(\mathsf{pre}(b,e)\). A straightforward computation of \(\mathsf{pre}(b,e)\) can potentially take \(O(z)\) time, for a total of \(O(z^2)\) running time across all required \(\mathsf{pre}(b,e)\) values. We overcome this challenge by providing a batched algorithm for computing multiple queries \((b,e)\) simultaneously, reminiscent of the winding phase of Farach and Thorup’s algorithm for pattern matching in LZ-compressed text [24]. This is achieved by processing a batch \(I=(b_1,e_1),(b_2,e_2),\ldots\) of queries via a single right-to-left scan of \(\mathcal{Z}\). When a phrase \(P=S[a..b]\) is processed, we can ‘shift’ all queries contained within \(P\) to the source of \(P\) as a single block in polylogarithmic time. Then, we can find every \((b_i,e_i)\) such that \(b_i\) and \(e_i\) are separated by \(a\) in polylogarithmic time per such query. This leads to a total running time of \(O((z+|I|)\mathop{\mathrm{polylog}}(\frac{n}{z}))\).

The second challenge is deterministically implement \(M\). We take a different approach than the one of Kempa and Saha for reducing the total space complexity for \(M\). While they partially computed the function \(M\) for every phrase, we pick a subset \(\mathcal{Z}_M\subseteq \mathcal{Z}\) of size \(O(z/\log \frac{n}{z})\), and compute \(M\) fully for every phrase in \(\mathcal{Z}_M\).

Intuitively, one would like to pick a set \(\mathcal{Z}_M\) that acts as a cover in the following sense. Consider for every \(i\in [n]\) the sequence \(P(i)\) of \(\mathop{\mathrm{polylog}}n\) phrases visited by iteratively applying \(J\) exactly \(\mathop{\mathrm{polylog}}n\) times (for some fixed \(\mathop{\mathrm{polylog}}n\)) starting from \(i\). A good choice of \(\mathcal{Z}_M\) corresponds to a set of phrases that is both compact, and covers all \(P(i)\) sequences. Since we aim for a preprocessing time of \(O(z \mathop{\mathrm{polylog}}(\frac{n}{z}))\), we can not even afford to inspect all \(P(i)\) within our preprocessing time.

We sidestep this issue by substituting the demand that \(\mathcal{Z}_M\) covers all such sequences with a relaxed notion of covering that is satisfactory for our purpose. First, let us simplify our analysis by assuming that prior to \(M\), we only make naive steps using \(J\) (and never use \(sJ\)). Now, for every \(i\in [n]\), we say that \(\mathcal{Z}_M\) light-covers \(i\) if there is some \(x\in [0..\log \frac{n}{z}]\) such that \(J^x(i)\) is either contained in some phrase of \(\mathcal{Z}_M\) or \(J^x(i)\) has \(r\)-value less than \(\frac{2}{3}r_i\). In words, we do not require \(\mathcal{Z}_M\) to intersect the first \(\log\frac{n}{z}\) steps following \(i\) in the event when we get ‘lucky’, and the repeated applications of \(J\) happen to incur a significant reduction in \(r\)-value without invoking \(M\).

With this notion of covering, our task is reduced to covering all sequences \(i\),\(J(i)\),\(J^2(i)\),\(\ldots\) ,\(J^{\log(\frac{n}{z})}(i)\) such that the starting and ending \(r\)-values are within the same exponential level. As it turns out, sequences with this property have a very strict structure. Namely, we observe that given \(i\) in a phrase \(P\) with \(r_i \in [k..1.5k)\) for some \(k\in \mathbb{K}_n\), if \(J(i)\) has \(r\)-value that is also in \([k..1.5k)\), there is only one phrase \(P'\) (independent of \(i\)) that may contain \(J(i)\). In other words: all ‘bad steps’ from phrase \(P\) are mapped to the same phrase \(P'\). This induces a tree structure over the phrases, where the parent of each phrase \(P\) is the unique phrase \(P'\) that may be its successor in a sequence of bad steps. Given such a structure, we can apply the standard approach of selecting a sparse tree layer as a compact path-covering set.

3.1.0.3 Improving the query time.

While our implementation is inspired by the construction of Kempa and Saha, our approach is different in the following sense. Kempa and Saha defined a ‘step’ function \(N\), and prove that it has certain properties. Then, the query algorithm iteratively applies the function, and it is guaranteed to converge quickly to a boundary index due to the properties of the function.

We use similar function definitions to the ones of Kempa and Saha, but our query algorithm does not iteratively apply these functions. Instead, our goal is to find the critical value \(x\) such that \(N^x(i)\) has a sufficiently small \(r\)-value, and compute \(N^x(i)\). By further studying the properties of \(N\) (and slightly modifying its definition), we are able to design algorithms that find \(x\) and \(N^x(i)\) without explicitly iterating over \(x=0,1,2,\ldots\).

For instance, the component of our algorithm equivalent to the stable part of Kempa and Saha does not use \(M\). We only use \(M\) to trigger the stable part, but not to make progress within it. Instead, we simply consider a sequence of applications of \(sJ\) throughout the stable part of the epoch. Since we gave up the progress obtained by occasionally reaching \(M\), the sequence of \(sJ\) applications before some progress in \(r\) is achieved may be arbitrarily large. However, by dropping \(M\) we obtain a cleaner structure to the stable part. That structure allows us to find the first \(x\) such that \(sJ^x(i)\) has a significantly reduced \(r\)-value in \(O(\log \frac{n}{z})\) time.

Finally, since we wish to have \(O(\log\frac{n}{z})\) epochs rather than \(O(\log n)\), we introduce a method for reducing any LZ-end partition with \(z\) phrases into a partition with \(O(z)\) phrases such that every phrase has length \(O(\frac{n}{z})\) ([lem:no-big-phrases]). This allows us to assume that the initial \(r\)-value is at most \(\frac{n}{z}\).

Formally, we break the task of previn 1 into the following two lemmas.

2 corresponds to applying \(J\) repeatedly until the \(r\)-value is either reduced significantly, or an index \(i\) for which \(M(i)\) is defined is met. We choose a set \(\mathcal{Z}_M\) for the definition of \(M\) such that this is guaranteed to happen within \(O(\log^2\frac{n}{z})\) applications of \(J\). The \(O(\log \frac{n}{z})\) query time is achieved by introducing shortcuts, which allows us to compute \(J^{\log {\frac{n}{z}}}\) in constant time, under some conditions.

3 corresponds to receiving the first index of the stable part, and efficiently finding the last index of the epoch. As we discussed before, it is achieved by analyzing the structure of the stable part to obtain a clean characterization of the first index with \(r\)-value below the required threshold.

By combining 2 and 3, we obtain our main theorem.

The rest of the paper is dedicated to proving 2 and 3. We prove 2 in 4 and 3 in 5 In 9, we prove [lem:no-big-phrases] , which allows us to assume without loss of generality that there are no long phrases in our input factorization \(\mathcal{Z}\). In [sec:kbad-parent-ds] [sec:shift-merge] [sec:computepre] we separately provide proofs for various auxiliary data structures used throughout the paper. Finally, in 10 we show how to modify and enhance our techniques to provide a compressed data structure for substring extraction.

4 Naive Jumping↩︎

In this section, we prove 2. We start by presenting a high-level description of the algorithm and of the concepts used by the algorithm, and then proceed to present the full version with all the required definitions and proofs.

4.1 High-Level Overview↩︎

The objective of this overview is to equip the reader with a conceptual understanding of the machinery behind 2. The framework developed in this section provides an intuitive abstraction of our method, meaning that the formal definitions and lemmas stated here will not be explicitly invoked in the full description of the data structure. Finally, we express all running times using \(\log n\) instead of \(\log \frac{n}{z}\) to ensure a smoother presentation.

For every phrase \(P=S[a..b]\) with source \(P' = S[a'..b']\), denote \(\delta_P=b-b'\). Clearly, for every index \(i \in [a..b]\), the index \(j=i-\delta_P\) satisfies \(S[i]=S[j]\) and \(r_j \le r_i\). We denote by \(J\) the function that maps any \(i\) in a phrase \(P\) to \(J(i) = i-\delta_P\).

Recall that our goal is to efficiently support the following query. Given some index \(i\) with \(r_i \in [k..1.5k)\), return \(j\) with \(r_j \le r_i\), \(S[j]=S[i]\), and either \(r_j < k\) or \(\ell_j < 1.5k\).

Consider the following simple algorithm for achieving this goal: Given an input index \(i\), let \(P\) be the phrase containing \(i\) in \(\mathcal{Z}\). Notice that \(|P|\neq 1\), as \(|P|=1\) would imply \(r_i = 0\), which contradicts \(r_i \ge k\). Therefore, \(|P|>1\) and \(P\) has a source. Consider \(j=J(i)\). If \(r_j < k\), return \(j\). Otherwise, repeat this process recursively on \(j\).

This algorithm clearly terminates, as every recursive call is for an index \(j\) strictly smaller than \(i\). However, it may be very inefficient. Our key insight is that the pathological case where this simple algorithm fails is highly structured. This structure can be described as follows.

In words, a sequence of applications of \(J\) where the \(r\)-value remains large corresponds to an upwards path in \(T_k\) (see 5).

To take advantage of the tree structure of the bad steps, we use the concept of a good mapping.

Notice that if \(r_i <1.5k\), a good mapping \(M\) maps \(i\) to \(j=M(i)\) with \(\min(r_j,r_i)<k\). Therefore, if \(i\) is in a phrase for which we have a good mapping, we can immediately return a valid output.

We prove that given a set \(M\subseteq \mathcal{Z}\) of phrases, it is possible to construct good mappings for every phrase in \(M\) with the following complexities.

Notice that we cannot afford to apply 5 with \(M=\mathcal{Z}\), as this would result in a data structure with \(O(z\log n )\) space. Instead, we apply 5 with a sparse set that covers all paths of length \(\log^2 n\) in \(T_k\). Such a set can be obtained by partitioning the vertices of \(T_k\) into \(\log^2 n\) sets based on their distance from the root modulo \(\log^2 n\). From the pigeonhole principle, we have that one of these sets has size at most \(z/ \log^2 n\) - we pick \(M_k\) to be this set. Notice that \(M_k\) intersects any upwards path of length \(\log^2 n\) in \(T_k\).

The total size of \(M_k\) sets over all values of \(k\) is \(O(z/\log^2 n \cdot|\mathbb{K}|) = O(z/\log n)\). Therefore, by applying 5 to the union of all \(M_k\)’s, we obtain a good mapping for every phrase within some \(M_k\) in total space \(O(z+ z/\log n \cdot \log n)= O(z)\).

We are almost ready to present an \(O(z)\) space data structure with a slightly slower \(O(\log^2 n)\) running time for 2. To this end, we only require the following two technical subroutines. First, we need a data structure for efficiently finding the phrase \(P\) containing an index \(i\). This can be trivially obtained in \(O(\log n)\) time via binary search. Second, we require a data structure that given a phrase \(P\) and \(k\in \mathbb{K}\), finds the parent of \(P\) in \(T_k\) in \(O(1)\) time. Notice that we cannot afford to store all trees \(T_k\) within our \(O(z)\) space limitation. We show in 31 that such a data structure can be constructed in \(O(z)\) space and \(O(z \log n)\) construction time.

Now, given an index \(i\), we first find the phrase \(P\) containing \(i\) in \(O(\log n)\) time. If \(P\in M_k\), we simply return \(M(i)\). Otherwise, we compute \(j= J(i)\) and \(P'\) the \(k\)-bad parent of \(P\). If \(j\) is not contained in \(P'\), we are guaranteed to have \(r_j<k\). We can therefore return \(j\). If \(j\) is contained in \(P'\), we check if \(r_j<k\) and if it is we return \(j\). If \(r_j \ge k\), we recurse on \(j\). Because \(j\) is guaranteed to be in \(P'\), we additionally send \(P'\) to the recursive call. Thus, successive recursive calls do not need to dedicate \(O(\log n)\) time to compute the phrase containing \(j\).

Every recursive call except for the first one is implemented in \(O(1)\) time. From the path covering property of \(M_k\), we have that if more than \(\log^2 n\) calls are made, it is guaranteed to reach an index \(i\) contained in a phrase of \(M_k\). The running time is therefore \(O(\log^2 n)\).

In order to obtain further speedup, we apply a shortcut strategy. To this end, we analyze a more general notion of ‘lack-of-progress’ in the simple algorithm. In our former analysis, we focused on the case where a single application of \(J\) leads to an index with a large \(r\)-value. Now, we wish to analyze the case where \(x\) consecutive applications of \(J\) still lead to a large \(r\)-value.

We present the notion of an \(x\)-bad index. Consider a phrase \(P\) and the sequence \[P=P^{(0)},P^{(1)},P^{(2)},\ldots, P^{(x)}\] of ancestors of \(P\) in \(T_k\) (with \(P^{(x)}\) denoting the \(x\)-th parent of \(P\) in \(T_k\)). We say that an index \(i\) in \(P\) is \(x\)-bad if for every \(y\in[0..x]\), it holds that \(J^y(i)\) is in \(P^{(y)}\). It can be shown by induction that the set of \(x\)-bad indices within \(P\) forms a consecutive interval in \(P\). We call this the \(x\)-bad interval of \(P\).

Furthermore, we can use the fact that the sequence of visited phrases is shared by all \(x\)-bad indices in \(P\) to efficiently compute \(J^{(x)}(i)\) for an \(x\)-bad index \(i\). Namely, it holds that for an \(x\)-bad index \(i\), we have \(J^x(i)=i-\Delta_P\) where \(\Delta_P=\delta_P+\delta_{P^{(1)}} + \ldots + \delta_{P^{(x-1)}}\).

It follows from the above discussion that given the \(x\)-bad interval of \(P\) and \(\Delta_P\), we can decide for an index \(i\) in \(P\) if it is \(x\)-bad, and if it is, find \(J^x(i)\), all in constant time. Fix \(x\) to be \(\log n\) from now on.

Since the total size of all \(T_k\) is \(O(z\log n)\), we cannot afford to store this information for every node in every \(T_k\). Instead, as in the previous algorithm, we chose a sparse set \(M'_k\) of size \(O(z/\log n)\) for each \(T_k\). We only store this shortcut information for the vertices in \(M'_k\). We also store for each phrase in \(M'_k\) its nearest ancestor in \(T_k\) that is marked (i.e, in \(M_k\)).

We are ready to describe our faster query (see 7). First, apply at most \(\log n\) steps of \(J\). If at any point we reach an index \(j\) with \(r_j<k\) or in \(M_k\), we halt and return as in the previous algorithm.

Otherwise, after \(\log n\) steps the algorithm must reach some phrase in \(M'_k\). At this point, we start using shortcuts instead. In every shortcut step, we check if the current \(i\) is \((\log n)\)-bad using the \((\log n)\)-bad interval. Additionally, we check the distance \(d\) from the phrase \(P\) containing \(i\) to its nearest ancestor in \(T_k\) that is also in \(M_k\).

If \(i\) is not \((\log n)\)-bad, or if \(d < \log n\), apply \(J\) at most \(\log n\) more times instead of using a shortcut – we claim that the algorithm terminates with a valid output within those \(\log n\) steps. If none of these steps reach an index \(j\) with \(r_j<k\), it must hold that \(i\) is \((\log n)\)-bad. Therefore, this case must have been trigger due to \(d<\log n\). It follows that one of the \(\log n\) phrases visited after \(i\) is in \(M_k\), and we can use the good mapping associated with it to return a valid output.

Otherwise, we have that \(i\) is \(x\)-bad, and we use \(\Delta_P\) to obtain \(J^{\log n}(i)\) in constant time. Notice that since \(M'_k\) is selected as a set of all phrases with the same depth modulo \(\log n\) in \(T_k\), it is guaranteed that \(J^{\log n}\) is in a phrase of \(M'_k\).

Let us analyze the running time. We start using shortcuts after applying \(J\) at most \(\log n\) times. Then, every shortcut reduces our distance from a phrase in \(M_k\) by \(\log n\). This distance is initially at most \(\log^2 n\). Therefore, we will use a shortcut at most \(O(\log n)\) times. Once we stop using shortcut for any reason, we are guaranteed to terminate with a valid output within \(O(\log n)\) applications of \(J\). The total running time is therefore \(O(\log n)\), as required.

In order to implement the above in \(O(\log n)\) time, we also require a mechanism for testing in constant time if a phrase \(P\) is in \(M'_k\). This can be obtained by storing a machine word \(M_P\) for every phrase in \(\mathcal{Z}\), where the \(i\)’th bit indicates whether or not \(P\) is in \(M'_k\) for \(k = 1.5^i\).

4.2 Data Structure for Naive Jumping↩︎

To prove 2, we study the process of following the source phrase of the phrase \(P\) containing \(i\), ‘jumping’ to the index aligned with \(i\) within the occurrence of \(P\) ending with the source. To formalize this, we define a jumping rule \(J(i)\). Our ultimate goal is to find an index \(j\) with \(r_j<k\) and \(S[i]=S[j]\). Intuitively, we make progress towards this goal when we jump to an index with a lower \(r\)-value, and lose progress if we jump to an index with a higher \(r\)-value. This motivates us to define jumping rules that do not lose progress, in the following sense.

For a phrase \(P_i=S[a_i..b_i]\) with source \(P_j=S[a_j..b_j]\), we denote \(\delta_{P_i} = b_i-b_j\). We define the jumping rule \(J\) based on \(\delta_{P_i}\).

The following lemma follows directly from the definition of LZ-end.

Since \(J(i)\) is defined based on the phrase containing \(i\), our algorithms are often required to find the phrase containing an index \(i\). This can be supported in \(O(\log n)\) time and \(O(z)\) space by storing \(\{a_i \mid i\in [z] \}\) in a balanced search tree. We would like to support this query slightly faster. To this end, we provide the following data structure.

Given an index \(i\in [n]\), we can use 7 to find the phrase \(P\) containing \(i\) in \(O(\log \frac{n}{z})\) time. Since every phrase \(P_i\) is stored alongside the index \(j\) indicating its source phrase \(P_j\), we can compute \(\delta_{P_i}\) in \(O(1)\) time given \(P_i\), by accessing the array storing the phrases alongside their reference data.

We proceed to define the function \(\mathsf{pre}\), which is used to define the second jumping rule used in the naive jumping part.

In words, \(\mathsf{pre}(b,e)\) is obtained by finding previous occurrences of \(S[b..e]\) by following the source links of \(\mathcal{Z}\), until it is no longer possible. Halting this process can occur either because \(b\) and \(e\) are separated by a phrase boundary, or because the phrase \(P\) containing \([b..e]\) has no source (which can only occur if \(P=S[b]=S[e]\)). The left endpoint of the occurrence on which we stop in this process is \(\mathsf{pre}(b,e)\). Since \(\mathsf{pre}(b,e)\) is obtained by applying \(J\) repeatedly, the following is a consequence of 6.

We will define a jumping rule \(M\) that relies on \(\mathsf{\delta}\text{-}\mathsf{pre}{}\). Unlike \(\delta_P\), that is essentially given alongside \(P\) in \(\mathcal{Z}\), computing \(\mathsf{\delta}\text{-}\mathsf{pre}{}(b,e)\) from \(\mathcal{Z}\) require some non-trivial work. A naive approach would be to check if \([b..e]\) contains a phrase boundary, and if it does not - proceed according to the recursive definition. This may result in \(O(z)\) time for computing a single \(\mathsf{pre}(b,e)\) value. In 6, we present the following algorithm, which will be instrumental for efficiently computing \(\mathsf{\delta}\text{-}\mathsf{pre}{}\)-dependent jumping rules.

In order to define \(M\), we need to introduce the halved canonical partition of an interval. This partition appears under a variety of names in compressed random access data structures (in particular in [21]).

The key property of the canonical partition is that for an index \(i\in [a..b]\), the interval \(I\) that contains \(i\) in the canonical partition has length at most \(m = \min(r_i,\ell_i)+1\). It immediately follows that in the halved canonical partition, the length of the interval containing \(i\) is bounded by \(\max(m/2,1)\). We are now ready to define the jumping rule \(M\).

It follows from [obs:pre-is-legal] that \(M\) is a legal jumping rules.

Notice that \(M(i) = i - \mathsf{\delta}\text{-}\mathsf{pre}{}(b,e)\) transforms \(i\in [b..e]\) into an interval of size \(|[b..e]|\) that contains a phrase boundary. Therefore \(M(i)\) has a phrase boundary that is quite close to it either from the left or from the right, inducing a significant decrease either of \(r\)-value or of \(\ell\)-value compared to \(i\). Formally, we prove the following useful property of \(M\).

[clm:m-reduce-l-or-r] implies that if our sequence of applications of \(J\) reaches upon some index \(j\) in a marked phrase, then \(M(j)\) is a valid output for 2. Our first goal will be to define a ‘good’ set \(M\), such that every sufficiently long sequence of \(J\) applications eventually reaches \(M\) (Roughly, see 10 for the precise definition). In order to exploit this property, our data structure has to support efficient computation of \(M(i)\) for an index \(i\) in a marked phrase. We present the following data structure for efficient \(M\) computation.

4.3 Finding a Good Set of Marked Phrases↩︎

Our first goal is to find a good set \(M\) of marked phrases. Before formally defining a good set (see 10), let us provide some intuition. We wish to find a set \(M\) that is both sparse and covering. We require \(M\) to be small, since we will support a query for \(M(i)\) using 9, which consumes \(O(z+ |M|\log \frac{n}{z})\) space. Since we wish to have \(O(z)\) space complexity, we need to have \(|M| \in O(z/\log \frac{n}{z})\).

As for the covering property, we would like to guarantee that every long enough sequence of steps \(i,J(i),J^2(i),\ldots\) eventually reaches some index contained in a phrase of \(M\). Instead, we will obtain \(M\) that satisfies a weaker, yet sufficient, notion of covering. Namely, we will guarantee that every long enough sequence of steps either reaches a phrase of \(M\), or reaches an index with small enough \(r\)-value.

Formally, we prove the following.

We introduce the concept of a bad jump, that corresponds to a step \(J(i)\) that remains in the same exponential level.

When \(k\) is clear from context or irrelevant, we omit it from the notion of \(k\)-bad jumps and \(k\)-good jumps, using bad jump and good jumps instead.

The existence of bad jumps is the main obstacle in finding a value \(j\) such that \(r_j<k\) via iterative application of \(J\). The pathological case would be where the sequence \(i,J(i),J^2(i),\ldots, J^x(i)\) consists only of bad jumps for high values of \(x\). However, we show that bad jumps are very structured. Namely, we show that the phrase \(P'\) that contains \(J(i)\) for some \(k\)-bad jump \(i\) can be decided only based on the phrase \(P\) containing \(i\) and \(k\). In other words, all \(k\)-bad jumps within a phrase \(P\) share some uniform behavior. We exploit this structure to efficiently cover every long sequence of bad jumps.

We make the following claim regarding bad jumps.

Following 11, we introduce the terminology of a \(k\)-bad parent. For a phrase \(P\) and \(k\in \mathbb{K}\), we call ‘the \(k\)-bad parent’ of \(P\) the unique phrase \(P'\) such that every bad jump \(i\) in \(P\) with \(r_i \in [k..1.5k)\) has \(J(i) \in P'\) (uniqueness follows from 11). If there is no such bad jump in \(P\), then \(P\) does not have a \(k\)-bad parent. Notice that \(P'\neq P\), since \(J(i)\) is necessarily in a phrase strictly to the left of the phrase containing \(i\). As implied by the parent terminology, the \(k\)-bad parent relation induces a forest structure over the phrases of \(\mathcal{Z}\). We denote as \(T_k\) the forest with vertices being the phrases of \(\mathcal{Z}\), and the parent of every \(P\) is the \(k\)-bad parent of \(P\).

In 7, we prove the following.

We are now ready to prove 10.

4.3.0.3 Reaching a marked phrase fast.

So far, we have guaranteed that if we repeatedly apply \(J\) starting from some index \(i\), we will either reach a marked phrase or reduce the \(r\)-value to the next exponential level within \(O(\log^2 \frac{n}{z})\) jumps.

Now, we introduce ‘shortcuts’, allowing us to find \(J^{\log \frac{n}{z}}(i)\) of an index \(i\) in constant time rather than by computing \(J\) iteratively step-by-step. The shortcut mechanism can only be applied if the next \(\log \frac{n}{z}\) steps are all ‘bad’. This will allow us to retrieve a valid output for the naive jumping part in \(O(\log \frac{n}{z})\) time, as if one of the next \(\log \frac{n}{z}\) steps are not bad - we can afford to make these steps one-by-one as we reach a good enough index after reaching a good step.

For a phrase \(P\), \(k\in \mathbb{K}\) and a non-negative integer \(x\), we denote as \(\mathsf{\pi}^{(x)}_{k}(P)\) the \(x\)’th ancestor of \(P\) in \(T_k\). In particular, \(\mathsf{\pi}^{(0)}_{k}(P) =P\) for every phrase \(P\) and \(k\in \mathbb{K}\). We also call \(\mathsf{\pi}^{(x)}_{k}(P)\) the \((x,k)\)-bad parent of \(P\).

We introduce the notion of \((x,k)\)-bad jumps.

Notice that every index \(i\) contained in a phrase \(P\) is \((0,k)\)-bad. For a node \(P\), \(k\in \mathbb{K}\) and non-negative integer \(x\) we denote \(\delta_x(P)=\sum_{y=0}^{x} \delta_{ \mathsf{\pi}^{(y)}_{k}(P) }\). In words, \(\delta_x(P)\) is the sum of \(\delta\) values taken over the first \(x+1\) ancestors of \(P\) in \(T_k\) (starting from \(P\) itself).

We make the following simple observation.

The following follows directly from [obs:same-jumps-same-shift] and from the definition of an \((x,k)\)-bad jump.

We show that the \((x,k)\)-bad jumps of \(P\) form a consecutive interval within \(P\).

We call the interval containing exactly the \((x,k)\)-bad jumps of \(P\) (implied by 13) the \((x,k)\)-bad interval of \(P\). We proceed to show that the \((x,k)\)-bad interval can be computed efficiently.

We are now ready to prove 2.

5 The Stable Part↩︎

In this section, we prove 3.

5.0.0.1 The jumping rule \(sJ\).

We define the jumping rule \(sJ\). For every \(P=S[a..b]\in \mathcal{Z}\), we denote \(L(P) = S[a..a+\left\lfloor \frac{2}{3}|P| \right\rfloor-1]\) the prefix of size \(\left\lfloor \frac{2}{3}|P| \right\rfloor\) of \(P\). Let us denote the set \(\mathbb{L}=\{ L(P) \mid P \in \mathcal{Z}\}\).

We define \(sJ(i)\) only for indices \(i\) that are contained in some \(L\in \mathbb{L}\).

Although not explicitly stated as a jumping rule, the logic expressed by \(sJ\) is used in [21] as well. It follows from [obs:pre-is-legal] that \(sJ\) is a legal jumping rule.

On several occasions throughout the section, we are required to prove that \(sJ(i)\) is defined for some index \(i\). The following provides a clean characterization of the event in which \(sJ(i)\) is defined for an index \(i\).

As we did for \(M\) in 4, we use 8 to construct the following data structure for computing \(sJ\).

We assume that for every phrase \(P\) with \(L(P) = S[b..e]\), we have access to \(\mathsf{\delta}\text{-}\mathsf{pre}{}(b,e)\). This is achieved as a consequence of applying 8 with the query set \(\mathbb{L}\).

5.0.0.2 High-level idea for proving 3

Let us fix some index \(i_0\) as the input for the stable part, and denote as \(k\in \mathbb{K}\) the unique integer power of \(1.5\) such that \(r_{i_0} \in [k..1.5k)\). We are interested in finding the first integer \(x^*\) such that \(sJ^{x^*}(i_0)\) has \(r\)-value less than \(k\). As in 4, we will show that there is a tree structure capturing the bad sequences of applications of \(sJ\). Unlike in 4, where we had a separate tree \(T_k\) for every possible \(k\in \mathbb{K}\) capturing the bad sequences with \(r\)-values roughly \(k\), here we will have a single tree \(T_{\mathsf{bad}}\) capturing all bad sequences.

This allows us to store \(T_{\mathsf{bad}}\) and preprocess it for level-ancestor queries. We provide a characterization of the sought value \(x^*\) such that \(sJ^{x^*}(i_0)\) has \(r\)-values less than \(k\). The characterization allows us to assign a numerical values \(\delta_\ell(P)\) and \(\delta_r(P)\) to every phrase \(P\). Then, when given \(i_0\) contained in some phrase \(P_0\), we can identify \(x^*\) as a level in \(T_{\mathsf{bad}}\) where the aggregated sums of \(\delta_{\ell}(P)\) and \(\delta_r(P)\) on the path from \(P_0\) to its ancestor in this level reach some threshold. We compute this sum in logarithmic time using level-ancestor queries. Given \(x^*\), and auxiliary information stored in \(T_{\mathsf{bad}}\), we can obtain \(sJ^{x^*}(i_0)\) in constant time.

5.0.0.3 Existence of \(x^*\)

Recall that \(sJ(i)\) is not defined for every index in \(i\in [n]\). Therefore, it is not immediate that \(x^*\) exists, as it may be the case that when repeatedly applying \(sJ\), we reach an index \(i'=sJ^{x'}(i_0)\) for which \(sJ(i')\) is undefined. In the following lemma, we prove that if this process reaches such an index, we have \(r_{i'}<k\), which means that \(x' =x^*\). In [21], the following properties are proven, but they are hidden within the proof of another claim (See Lemma 4.4 in [21]). We repeat their proof for the sake of self-containment.

The following is an immediate corollary of 16.

With 3, we have shown that \(x^*\) exists. For the rest of the section, we show how to efficiently find \(x^*\) and \(sJ^{x^*}(i_0)\).

5.0.0.4 Tree structure.

We override the definition of bad jumps from 4 to match our current context. First, we define the bad phrase and the bad suffix of \(L\in \mathbb{L}\) as follows.

Notice that unlike in the previous section, where we associated each phrase \(P\) with possibly \(|\mathbb{K}| \in O(\log \frac{n}{z})\) ‘bad’ phrases, here we only define one bad phrase for \(P\).

In the following, we establish the importance of bad phrases and bad suffixes, linking them to the terminal step that finally leads to an index with sufficiently small \(r\)-value.

We define a tree structure over the phrases. Let \(T_{\mathsf{bad}}\) be a tree with vertices being the phrases of \(\mathcal{Z}\). For every phrase \(P\), the parent of \(P\) in \(T_{\mathsf{bad}}\) is the bad phrase of \(P\). We denote the \(x\)’th ancestor of \(P\) in \(T_{\mathsf{bad}}\) as \(\mathsf{\pi}^{(x)}_{\mathsf{bad}}(P)\).

Similarly to 4, we have that if applying \(sJ(i)\) does not result in an \(r\)-value below \(k\), the index \(i\) is in the bad suffix of \(P\). Therefore, we focus on analyzing the structure of a sequence of \(sJ(i)\) applications in which every step falls within the bad suffix of the phrase containing it. We make the following simple observation, showing that the difference in \(\ell\) and \(r\) values as a result of applying \(sJ(i)\) is identical across all \(i\) in the bad suffix of a phrase \(P\).

Following 18, we introduce additional notation to capture the common change in \(\ell\)-values and in \(r\)-values among indices in the bad suffix. For a phrase \(P=S[a..b]\), with \(L(P)= L=[a..b']\), we define \(\delta_{\ell}(P) = \ell_{b'}-\ell_{sJ(b')}\) and \(\delta_r(P)=r_{b'}-r_{sJ(b')}\). Notice that \(b'\), as the last index of \(L\), is in the bad suffix of \(L\).

The following is directly implied by 18.

We notice that for every \(P\) we have that \(\delta_{\ell}(P)\) and \(\delta_r(P)\) are always non-negative.

Let us define the set of \((x)\)-bad indices of a phrase.

We also define, for every phrase \(P\) with \(L(P)=S[a'..b']\) the value \(\delta_{\mathsf{bad}}(P) = \mathsf{\delta}\text{-}\mathsf{pre}{}(a',b')\). Recall that for an index \(i\) in \(L(P)\), it holds that \(sJ(i) = i - \mathsf{\delta}\text{-}\mathsf{pre}{}(a',b')\). The following follows directly from the definition of an \((x)\)-bad jump.

We exploit [obs:same-jumps-same-shift] to show that we can quickly find \(sJ^{x+1}(i)\), provided that \(i\) is \((x)\)-bad.

5.0.0.5 Characterizing \(x^*\).

We will use the \(\delta_r\) and \(\delta_\ell\) values of the phrases to provide a characterization of the first integer \(x^*\) such that \(j = sJ^{x^*}(i_0)\) has \(r_j < k\). Before formally providing the characterization (see 21), let us provide some intuition.

Consider the process of iteratively applying \(sJ\), starting from \(i_0\) until \(j\) is reached. Before \(j\) is reached, it should be clear that all visited indices are bad, and it follows from 17 that every visited index is in the bad suffix of the phrase containing it. Therefore, the phrases visited correspond to an upwards path in \(T_{\mathsf{bad}}\). From 4, it follows that the decrease in \(\ell\) and \(r\) values when we jump from \(i\) to \(j\) is exactly the \(\delta_{\ell}\) and \(\delta_r\) values of the phrase containing \(i\), respectively.

In particular, if \(i_D = sJ^{D+1}(i_0)\) for some integer \(D\), it holds that \(\ell_{i_D} = \ell_{i_0} -\sum_{y = 0}^D\delta_{\ell}(P^{(y)})\) and similarly, \(r_{i_D} = r_{i_0} -\sum_{y = 0}^D\delta_{r}(P^{(y)})\). The two sums representing the total decrease in \(\ell\) and \(r\) correspond to the sum \(\delta_\ell\) values and \(\delta_r\) values of an upwards path from \(P\) in \(T_{\mathsf{bad}}\), respectively. We can use level ancestor queries to quickly identify the lowest ancestor of \(P\) in which the sum crosses a given threshold.

A natural threshold to consider for the sum of \(\delta_r\) is \(k-r_{i_0}\), as once this threshold is surpassed, the \(r\)-value drops below \(k\), which means that we have reached an index with sufficiently small \(r\)-value. However, this bound alone is not sufficiently precise. It may be the case that at some point, before the \(\delta_r\) values accumulate to \(k-r_{i_0}\), we visit some index \(j\) that is not in the bad suffix of the phrase containing it. If that is the case, our claim that the \(r\) value decreases according to the \(\delta_r\) values no longer holds (as its jumps no longer correspond to an upward path). Fortunately, according to 17, if such \(j'\) is reached, either \(j'\) or its successor \(sJ(j')\) have \(r\)-value below \(k\). Furthermore, it turns out that the first such \(j\) can be characterized using the accumulated \(\delta_\ell\) values.

To see this relationship between the \(\delta_\ell\) values in the first \(j\) that is not in a bad suffix, consider first \(\delta_\ell(P)\) (See 9). Let \(L=S[a' ..b']\) be the bad suffix of \(P=S[a..b]\). It should be relatively easy to see that \(\delta_{\ell}(P)=a'-a\). Now, it is clear that \(i\) is in the bad suffix of \(P\) if and only if \(\ell_i =i-a \ge a'-a=\delta_{\ell_P}\). Assume that \(i\) is indeed in the bad suffix of \(P\) and consider the bad phrase \(P'\) of \(P\) that contains \(j=sJ(i)\). We can apply the same reasoning and show that \(j\) is in the bad suffix of \(P'\) if and only if \(\ell_j \ge \delta_{\ell}(P')\). But when we reached \(P'\), we already decreased the \(\ell\) value of \(i\) by \(\delta_{\ell}(P)\). So, the condition \(\ell_j \ge \delta_{\ell}(P')\) translates to \(\ell_i \ge \delta_{\ell}(P)+\delta_{\ell}(P')\).

This pattern persists inductively, and we have that \(sJ^x(i)\) is in the bad suffix of the phrase containing it ‘if and only if’ the sum of \(\delta_{\ell}\) values does not exceed \(\ell_i\). Again, ‘if and only if’ is not completely precise here, because it may be the case that the \(r\)-value drops below \(k\) while visiting a bad suffix. Recall that we are only guaranteed to have the value of \(sJ\) well defined for the indices we meet in this process as long as their \(r\)-value exceeds \(k\) (3).

In conclusion, there are two events that may lead to the \(r\)-value dropping below \(k\) for the first time. One event corresponds to passing a certain threshold of accumulated \(\delta_r\) values and the other event corresponds to passing a certain threshold of accumulated \(\delta_{\ell}\) values. We need to specifically find the earlier of the two events, as the characterization of the \(r\)-values and the \(\ell\)-values on which we rely persists only as long as none of these two events occur.

We formalize the above intuition as follows. For any phrase \(P\in \mathcal{Z}\) and integer \(B\), we define \(\Delta_L(P,B) = \sum_{x=0}^{B} \delta_{\ell}( \mathsf{\pi}^{(x)}_{\mathsf{bad}}(P) )\). Similarly, we define \(\Delta_R(P,B) = \sum_{x=0}^{B} \delta_{r}( \mathsf{\pi}^{(x)}_{\mathsf{bad}}(P) )\).

We prove the following fact.

We proceed to use 21 to characterize \(x^*\). Recall that \(i_0\) is the input index with \(r_{i_0}=R \in [k..1.5k)\) for \(k\in \mathbb{K}\) We also denote \(L=\ell_{i_0}\). Let \(P\) be the phrase containing \(i_0\). For an integer \(D\), we denote \(\Delta_R(D)=\sum_{x=0}^{D}\delta_r( \mathsf{\pi}^{(x)}_{\mathsf{bad}}(P) )\) and \(\Delta_L(D)=\sum_{x=0}^{D}\delta_r( \mathsf{\pi}^{(x)}_{\mathsf{bad}}(P) )\). In words, \(\Delta_R(D)\) (resp. \(\delta_L(D)\)) is the sum of \(\delta_r\) values (resp. \(\delta_\ell\) values) on the path of length \(D\) from \(P\) towards the root of \(T_{\mathsf{bad}}\).

We denote as \(D_R\) the maximal integer such that \(\Delta_R(D_R) \le R-k\). Similarly, we denote \(D_L\) as the maximal integer satisfying \(\Delta_L(D_L) \le L\). Notice that \(\Delta_L(-1) = \Delta_R(-1) = 0\), and that \(L \ge 0\) and \(R \ge k\), so \(D_L\) and \(D_R\) are well defined.

We prove the following fact.

Having established the connection between \(D_L\),\(D_R\), and the sought value \(x^*\), we are now interested in constructing a data structure for efficiently computing \(D_L\) and \(D_R\). We prove the following.

We are finally ready to prove 3

6 Batched pre Computation↩︎

In this section, we prove 8.

We use the following data structure that has been designed (in a slightly more restricted variant) by Farach and Thorup [24]. For completeness, we provide a complete proof in 8.

We first present an algorithm with \(O(z\log^2n)\) running time. We will later show how to replace the \(\log n\) factors with \(\log \frac{n}{z}\). Denote \(I = (b_1,e_1),(b_2,e_2),\ldots , (b_{|I|},e_{|I|})\). Denote \(B = \{ b_i \mid i \in [|I|] \}\). Let \(Z = \{ a_i \mid i\in [z] \}\) be the starting indices of the phrases of the Lempel-Ziv End partition \(\mathcal{Z}\) of \(S\). We define a node for every query in \(I\) as follows. For every \((b_i,e_i)\in I\), we define a node \(v_i\) with initial value \(\mathsf{val}(v_i) =b_i\). The node \(v_i\) contains as auxiliary information \(E(v_i)= e_i\) and \(I(v_i)=i\). We initialize a tree data of [lem:split-merge-shift] and add to \(X\) a balanced tree \(T\) containing all the vertices \(\{v_i \mid i\in [|I|]\}\). The tree is sorted in increasing order of \(\mathsf{val}(v)\).

For every node \(v\in T\), we store as auxiliary information the value \(M(v)\) which is the maximal \(E(v)\) value of a node in the subtree rooted at \(v\).

We maintain the auxiliary information as the tree is manipulated by the operations of the data structure. Throughout the algorithm, when a node \(v\) is in a tree \(T'\) that is applied a \(\mathsf{Shift}(T,\delta)\) operation, we consider \(E(v)\) to be shifted by the same amount. However, \(I(v)\) does not change throughout the running time of the algorithm.

6.0.0.1 The algorithm (See [fig:pre-batch])

The algorithm initializes an array \(A\) of size \(|I|\) intended to store the answers to each query. Initially, \(A[i] = \mathsf{nil}\) for every \(i\in [|I|]\). We will show that when the algorithm terminates, \(A[i]=\mathsf{pre}(b_i,e_i)\). Throughout the algorithm, we will remove nodes from \(T\). When we remove a node \(v\) from \(T\), we assign \(A[I(v)] = \mathsf{val}(v)\).

The algorithm consists of \(z\) iterations indexed in decreasing order from \(z\) to \(1\). We maintain the invariant that at the start of every iteration, \(X\) contains a single balanced search tree. Initially, \(T= T_z\) is the tree described above. For every \(t\in [1..z]\), in decreasing order, the algorithm applies the following.

1. Let \(T\) be the single tree in \(X\) at the start of iteration \(t\). Let \(P_t = S[a_t..b_t]\) be the \(t\)-th phrase in \(\mathcal{Z}\) with source \(S[a'_t..b'_t]\), and let \(\delta_t = b_t - b'_t\). If \(P_t\) does not have a source, let \(\delta_t = 0\).

2. If \(\delta_t \neq 0\):

   1. Split: split \(T\) into two trees \(T^1= T \cap [1..a_t-1]\) and \(T^2= T \cap [a_t..b_t]\) using a \(\mathsf{Split}(T,a_{t-1})\) operation.

   2. Shift: Apply \(\mathsf{Shift}(T^2, -\delta_t)\) to obtain \(T^2_\delta\).

   3. Merge: merge \(T^1\) and \(T^2_\delta\) into \(T\) using \(\mathsf{Merge}(T^1,T^2_{\delta})\)

3. Deletion: as long as there is a node \(v\in T\) with \(E(v)\ge a_t\), find \(v\) and remove it from \(T\).

After applying the subroutine for \(t=1\), output \(A\).

In each iteration, the algorithm applies \(O(1)\) operations of type \(\mathsf{Split}\), \(\mathsf{Shift}\), and \(\mathsf{Merge}\) to the data structure. Additionally, the subroutine deletes nodes, with each node deleted at most once throughout the running time of the algorithm. Navigating to nodes with maximal \(E\) value can be done in \(O(\log n)\) using the auxiliary \(M\) information. Since we apply \(|I|\) deletions and \(z\) operations of types \(\mathsf{Split},\mathsf{Shift},\mathsf{Merge}\), the total running time is \(O((z+|I|)\log^2n)\).

We proceed to show that the algorithm correctly computes all \(\mathsf{pre}\) values. For every \(t\in [z]\), denote as \(T_t\) the single tree \(T\) stored in \(X\) at the start of the \(t\)-th iteration of the algorithm (where the \(z\)-indexed operation is the first one and the \(1\)-indexed iteration is the last one)

We start by proving the following invariant.

We now prove the following invariant, intuitively stating that when we change the value of a node throughout the algorithm, the newly created node represents an equivalent query.

The last invariant we need is that when the algorithm removes a node, the value assigned in \(A\) is the correct \(\mathsf{pre}\) value for the query represented by this node.

Let us conclude the correctness of the algorithm. In every iteration, we either delete vertices or change their value. When the algorithm concludes, all vertices are deleted since the first phrase in \(\mathcal{Z}\) must be \(S[1..1]\). Therefore, at iteration \(1\) we will remove all vertices \(v\) with \(\mathsf{val}(v) \ge 1\), which is satisfied for all remaining vertices by 24.

When the vertex \(v\) with \(I(v)=i\) is deleted, we set \(A[i] = \mathsf{val}(v)\). By 26, it holds that \(\mathsf{val}(v) = \mathsf{pre}(\mathsf{val}(v),E(v))\). By 25, it holds that \(\mathsf{val}(v) = \mathsf{pre}(b_i,e_i)\), as required.

6.0.0.2 Substituting \(\log n\) factors with \(\log \frac{n}{z}\).

We now describe how to implement the above approach, replacing the \(\log n\) factors with \(\log \frac{n}{z}\) factors. We uniformly partition the domain \([1..n]\) into \(z\) intervals \(U_i = (i \cdot \frac{n}{z}..(i+1)\frac{n}{z}]\), each of size \(\frac{n}{z}\). Instead of maintaining one tree containing all queries, we maintain a separate tree \(T_i\) maintaining queries \((b,e)\) with \(b\in U_i\). The queries are sorted according to the primary order \(b\), and the secondary order \(e\).

When we implement a split, the split interval corresponds to some phrase \(P_i = S[a_i..b_i]\). Due to [lem:no-big-phrases], we have that \(|P_i| \le \frac{n}{z}\), which means that \([a_i..b_i]\) spans at most two intervals \(U_x\),\(U_{x+1}\). We partition the range \([a_i.,b_i]\) into at most two sub-ranges, and remove each of them from the corresponding \(U_i\). Similarly, when we merge the shifted version of \([a_i..b_i]\) back intro a tree, we first find in constant time the at most two intervals \(U_x,U_{x+1}\) intersecting the (shifted) range, split \([a_i..b_i]\) accordingly and merge each piece into the corresponding \(U_x\),\(U_{x+1}\). Finding the \(U_x\) intersecting \([a_i..b_i]\) in both of these cases can be done in constant time.

We would maintain the invariant that every tree is of size \(O((\frac{n}{z})^2)\), so each search tree operation costs \(O(\log \frac{n}{z})\). Since \(T_i\) contains only queries \((b,e)\) with \(b\in U_i\), the number of distinct \(b\) values in \(T_i\) is bounded by \(\frac{n}{z}\). Notice that the distance between \(b\) and \(e\) never changes throughout the lifetime of a node. Since initially we have \(e-b \le \frac{n}{z}\) for every query, we have that this inequality holds for every query throughout the running time of the algorithm. Therefore, for every \(b\) there are at most \(\frac{n}{z}\) possible values of \(e\), and the possible distinct \((b,e)\) pairs that can be in a tree \(T_i\) is bounded by \((\frac{n}{z})^2\). In \(T_i\), every node with values \((b,e)\) stores, as auxiliary information, a linked list of all \(i\) such that the query \(q_i\) in the initial input currently corresponds to this node. Initially, each node is attached with a single \(i\), but we may combine nodes with identical \(b\) and \(e\) values throughout the running time of the algorithm, connecting their corresponding lists.

Whenever the size of a tree \(T_i\) exceeds \(2 (\frac{n}{z})^2\), we iterate \(T_i\) and merge every duplication we find in \(O(1)\) time. Since \(|T_i| \ge (\frac{n}{z})^2\) and we have less than \((\frac{n}{z})^2\) distinct values of \(T_i\) that may belong in \(T_i\), we are guaranteed to find at least \((\frac{n}{z})^2\) duplications in this process. It follows that we find a duplication in amortized constant time. After applying the above, the size of \(T_i\) is again bounded by \((\frac{n}{z})^2\).

Since every merge increase the total number of queries across all trees by 1, we will have at most \(z\) merges throughout the running time of the algorithm, each found and implemented in \(O(1)\) time.

Another change that the partition into intervals introduces to the algorithm is in the tests for the maximal value \(e\) across all queries in our data structures. We would not like to check all \(T_i\)’s individually, and even storing a heap over all of \(T_i\)’s maximal elements is too costly (This will introduce an extra cost of \(O(\log z)\)). Instead, recall that every \((b,e)\) pair has \(e\in [b..b+\frac{n}{z}]\). We also recall that at every point throughout the running time of the algorithm, we have some prefix of the domain still containing queries, so \(U_1,U_2,\ldots U_x\) are active, and every \(U_y\) with \(y>x\) is empty. Together, these two properties imply that the maximal \(e\) values is either in \(T_x\) or in \(T_{x-1}\), so it is sufficient to query both \(T_i\) and \(T_{i-1}\) for their maximal value in \(O(1)\) time.

7 Data Structure for Finding a Bad Parent↩︎

In this section, we prove 12. We will describe a data structure with running time \(O(z (\log^2 \frac{n}{z} + (\log \log n)^2))\). Then, we will discuss how to replace the \(\log\log n\) factor with \(\log\log \frac{n}{z}\). In this section, \(k\)-bad parent corresponds to the definition presented in 4 (following 11), i.e., the \(k\)-bad parent of \(P\) is the parent of \(P\) in \(T_k\).

Our data structure consist of two main component. The primary ingredient is a mechanism that allows us, given a query phrase \(P\) and \(k\in \mathbb{K}\), to retrieve a set of \(O(1)\) candidates for being the \(k\)-bad parent of \(P\) in \(O(1)\) time. The second, complementary component is a verification algorithm, allowing us to check if a given phrase is the \(k\)-bad parent of \(P\) in constant time.

We start by presenting the verification algorithm. The main part of the verification algorithm is the following characterization of the \(k\)-bad parent.

27 immediately implies an \(O(1)\) verification algorithm, given below.

We proceed to show that a set of \(O(1)\) candidates can be retrieved efficiently. As a means to that end, we show how to use 27 to find the \(k\)-bad parent of a given \(P\) in \(O(\log \frac{n}{z})\) time. This is not fast enough for our final goal - which is supporting such queries in constant time. However, it will be useful in the construction of the data structure.

We are now ready to describe the main part of the data structure for finding the \(k\)-bad parent of a given \(P\). We define the notion of critical bad values.

Intuitively, one can consider the process of fixing a phrase \(P\) and increasing \(k\) from \(\min (\mathbb{K})\) to \(\max(\mathbb{K})\). The critical bad values of \(P\) are the values of \(k\) where the \(k\)-bad parent changes in this process (excluding very large \(k\) values with \(k>|P|/2\)). We prove several useful properties of the \(k\)-critical bad values. We start by showing that for \(k\)-critical values, the \(k\)-bad parents of \(P\) is of size roughly \(k\).

Next, we show that the set of values \(k\) such that a phrase \(P'\) is the \(k\)-bad parent of \(P\) form a consecutive interval.

We are ready to present our data structure for efficiently finding the \(k\)-bad parent. For every phrase \(P=S[a..b]\in\mathcal{Z}\) we store the following information.

1. \(k(P) \subseteq \mathbb{K}\): the at most two unique values \(k\in \mathbb{K}\) such that \(|P| \in [k..2k)\)

2. \(P'(P) \subseteq \mathcal{Z}\): for every \(k\in k(P)\), the \(k\)-bad phrase of \(P\), if it exists.

3. \(C(P)\): a bit vector of size \(\log_{1.5}|P| \in O(\log n)\). If \(k\) is a critical bad value of \(P\), then \(C(P)[k] = 1\), otherwise \(C(P)[k]=0\).

4. \(K(P)\in \mathbb{K}\): the unique power of \(1.5\) satisfying \(|P| \in [K(P)..1.5 K(P))\).

5. \(h(P) \in [1..n]\): the minimal integer multiple of \(K(P)\) contained in \(P\). Formally, \(h_P = \min(\{ i \cdot K(P) \mid i\in \mathcal{Z}\} \cap [a..b])\)

Additionally, we build the hash table \(H\) in which for every \(P\), we have \(H(h(P)) = P\) (\(P\) is represented as its index in \(\mathcal{Z}\)). The construction of \(H\) requires \(O(z(\log \log z)^{2})\) time with 1. The stored information for each phrase can be computed in \(O(\log^2 \frac{n}{z})\) time for every phrase as follows. The values \(k(P)\), \(K(P)\) and \(h(P)\) can be obtained in \(O(1)\) time via simple arithmetic operations. \(P'(P)\) can be obtained in \(O(\log \frac{n}{k})\) time using the data structure of 28. To construct \(C(P)\), we iterate all values in \(\mathbb{K}\). For each such value, we check if it is a critical bad value directly according to the definition. To do that, we need to be able to retrieve the \(k\)-bad parent of \(P\) for a given \(k\in \mathbb{K}\), which we do in \(O(\log \frac{n}{k})\) time using 28. The total running time for finding \(C(P)\) is \(O(|\mathbb{K}| \cdot \log \frac{n}{z})=O(\log^2\frac{n}{z})\).

Let us prove that the above information is sufficient to retrieve the \(k\)-bad parent of \(P\) in \(O(1)\) time.

7.0.0.1 Substituting \((\log \log z)^{2}\) with \(\log \frac{n}{z}\).

We notice that the \((\log \log z)^{2}\) factor arises from computing the deterministic hash of [23] over \(z\) elements from domain of size \(n\). We can instead partition the domain \(n\) into \(z\) uniform intervals \(U_1,U_2,\ldots U_z\) of size \(\frac{n}{z}\). Then, we construct a separate hash \(H_i\) for every \(U_i\), only mapping the values in \(U_i\) to their respective elements in \([z]\). When constructing the hash of \(U_i = (i\cdot \frac{n}{z}.. (i+1) \cdot \frac{n}{z}]\), we use relative values instead of absolute values (i.e., \(x \in U_i\) is encoded as \(x- i\cdot \frac{n}{z}\)). Therefore, the hash is over a domain of size \(\frac{n}{z}\). Now, when we wish to find \(H(x)\), we first find \(U_i\) containing \(x\) in constant time, and query \(H_i[x']\) with \(x'-i\cdot \frac{n}{z}\) in constant time. The time for constructing \(H_i\) is \(z_i (\log\log z_{i})^{2} = O(z_{i} \log \frac{n}{z})\), where \(z_i\) is the number of hashed values within \(U_i\). Since \(\sum_{i=1}^z(z_i)= z\), the total running time for constructing all hashes is \(O(z \log \frac{n}{z})\) as required. The query time remains \(O(1)\).

8 Shift-Split-Merge Structure↩︎

This section is dedicated to proving the following lemma. As mentioned earlier, it has been already proven by Farach and Thorup [24], and we only present our proof for completeness. Also, we make it more clear that the time complexity depends on \(n\), the maximum number of distinct elements in a tree. We briefly comment that Iacono and Özkan [26] claimed a faster data structure, but a complete description of the shift operation isn’t present in the published version, and it is not immediately clear if their complexity could be made dependant on the number of distinct elements.

We implement each balanced search tree with e.g. red-black trees [27]. Recall that a red-black tree \(T\) has the property that, given a node \(u\in T\), we can split \(T\) into a tree containing all elements strictly smaller or equal to \(u\) and a tree containing all elements larger than \(u\) in \(O(\log N)\) time. Similarly, given two trees \(T_{1}\) and \(T_{2}\) such that every element stored in \(T_{1}\) is smaller or equal to every element stored in \(T_{2}\), we can obtain a tree storing all elements in \(T_{1}\) and \(T_{2}\) in \(O(\log N)\) time. We call the former operation splitting and the latter joining (to distinguish from merging, which is defined as in the statement of the lemma). Of course, because the tree is balanced, we are able to find the (strict) successor/predecessor of any element in \(O(\log N)\) time, and insert/delete new elements in the same time complexity.

Each node \(v\) of the tree is decorated with a shift \(\delta_{v}\), and the invariant is that the, a node \(u\) physically storing an element \(x\) actually corresponds to \(x\) increased by the sum of \(\delta_{v}\), over every \(v\) that is an ancestor of \(u\). It i straightforward to maintain the invariant during a rotation. Initialize, insertion/deletion, split, and shift are immediate to implement, with the first working in worst-case constant time, and the remaining operations working in \(O(\log N)\) worst-case time. The non-trivial step is implementing a merge.

For a tree \(T\), let \(\mathsf{distinct}(T)\) denote the number of distinct elements in \(T\). We first observe that, given two trees \(T_{1}\) and \(T_{2}\), we can compute their merge in \(O(\min\{\mathsf{distinct}(T_{1}),\mathsf{distinct}(T_{2})\}\log N)\) time. This is done as follows. We first retrieve the smallest elements of \(T_{1}\) and \(T_{2}\), denoted \(x_{1}\) and \(y_{1}\), respectively. By symmetry, let us assume that \(x_{1} \leq y_{1}\). We split \(T_{1}\) at \(y_{1}\) to obtain \(T'_{1}\) and \(T'_{1}\) and we similarly split \(T_{2}\) at \(y_{1}\) to obtain \(T'_{2}\) (containing only elements equal to \(y_{1}\)) and \(T''_{2}\). We join \(T'_{1}\), \(T'_{2}\), and the result of repeating the procedure on \(T''_{1}\) and \(T''_{2}\). The time complexity is \(O(\min\{\mathsf{distinct}(T_{1}),\mathsf{distinct}(T_{2})\}\log N)\), and more precisely it is upper bounded by the interleave between the distinct elements of \(T_{1}\) and \(T_{2}\) times \(O(\log N)\). However, we will establish that the amortized complexity is actually much better.

To analyze the amortized complexity of a merge, we use the following potential function, where to avoid clutter each unit of potential suffices to pay for \(O(\log N)\) time. Consider a tree \(T\), and let its elements (ignoring the duplicates) be \(x_{1} < x_{2} < \ldots < x_{k}\). We define potential of \(T\) to be \(\sum_{i} 1+\log (x_{i+1}-x_{i})\), and then the potential of the whole structure is the sum of the potentials of its constituent trees. It is immediate that the amortized cost of initialization is \(O(1)\), the amortized complexity of insertion is \(O(\log n \log N)\) as we must account for the increase in the potential, while the amortized complexity of deletion, split and shift is \(O(\log n \log N)\) as the potential cannot increase. To analyze the change in the potential after a merge operation, we first observe that the additional \(1\) in the definition allows us to absorb the cost for the elements that occur in both trees. Thus, we will assume that the elements stored in both trees are distinct. To analyze the change in the potential, it is enough to analyze the situation after inserting a range of \(k\) elements \(x_{i}<x_{i+1}<\ldots x_{i+k-1}\) from one tree between two consecutive elements \(y_{j} < y_{j+1}\) of the other tree, which corresponds to a single step of the merging procedure. Then, the distance of \(y_{j}\) to its successor is decreased by at least half while the distance of every other element to its successor does not increase, or the distance of \(y_{j}\) to its predecessor is decreased by at least half while the distance of every other element to its predecessor does not increase. The potential can be equivalently defined by considering the distance of each element to its successor or the distance of each element to its predecessor, so we obtain that for at least half steps of the merging procedure the potential decreases by at least \(1\), which allows us to pay for all the steps.

9 Eliminating Large Phrases↩︎

This section is dedicated to proving the following lemma.

We start by showing that a large phrase can be replaced by a small number of smaller phrases. We then show how to apply this replacement iteratively and efficiently.

We are now ready to prove [lem:no-big-phrases].

10 Data Structure for Substring Extraction↩︎

In this section, we present an efficient compressed data structure for substring extraction, proving 2. That is, given \([i..j]\), return \(S[i..j]\). We will present a data structure that uses \(O(z)\) space and supports queries in \(O(\log^2 \frac{n}{z}+ j-i)\) time. That is, the best conceivable query time without improving upon the query time for random access presented in 1.

We will assume that \(j-i \le \log^2\frac{n}{z}\), and show an algorithm with running time \(O(\log^2 \frac{n}{z})\). In the general case where \(j-i\) is large, we can break \(S[i..j]\) into pieces of size \(\log^2\frac{n}{z}\) and extract each piece separately for a total running time of \(O(j-i)\).

Intuition and Overview. As a primary tool, we will first present an optimal data structure with \(O(z)\) space and \(O(j-i)\) query time for the special case where \(j\) is the ending index of a phrase \(P\) (also given at query time)¹. We call this data structure a suffix extraction data structure, and we will make extensive use of this data structure in our general substring extraction data structure.

The existence of the suffix extraction data structure naturally defined an ‘advantageous’ setting where general substring extraction can be done efficiently. For instance, if \(S[i..j]\) contains a phrase boundary \(b\), we can extract \(S[i..b]\) in \(O(b-i+\log \frac{n}{z})\) time (the \(O(\log \frac{n}{z})\) factor is required to find \(b\) via 7). This allows us to assume that our input does not contain a phrase boundary

With this assumption in place, another convenient case for extraction arises. If \(r_{i} \in O(j-i)\) we can use suffix extraction to extract \(S[i..i+r_i]\) in \(O(j-i)\) time. Due to our assumption that \([i..j]\) has no phrase boundaries, we have \(i+r_i > j\) and we therefore have \(S[i..j]\) at hand as a prefix of \(S[i..i+r_i]\).

Our goal now shifts to reducing a general input \(i,j\) into an input with \(r_i \in O(j-i)\). To this end, we will employ the epoch approach of the random access algorithm. Intuitively, we would like to say that this goal is obtainable by simply running the random access algorithm on \(i\), and halting the algorithm prematurely when a sufficiently small \(r\)-value is obtained. Recall that the random access algorithm consists of epochs, each reducing the \(r\)-value to the next exponential level compared to the value seen at the start of the epoch. Therefore, one may expect that when running a sequence of epochs on index \(i\), we will encounter a sequence of indices \(i = i_1,i_2,\ldots i_x\) such that if \(r_{i_x}\in [k..1.5k)\), then \(r_{i_{x+1}} \in [k/1.5..k)\) (i.e., in the next smallest exponential level). Combined with the observation that as long as \(r_{i_x}>j-i\), it holds that \(S[i_x..i_x+j-i] = S[i..j]\), this structure immediately leads to an extraction algorithm. We can run the random access algorithm on \(i\), and instead of halting upon reaching \(i'\) with \(r_{i'}=0\), we halt upon reaching \(r_{i'}\in [j-i..1.5 (j-i)]\) This should occur within \(O(\log \frac{n}{z})\) epochs, leading to \(O(\log^2\frac{n}{z})\) running time, with an additional \(O(j-i)\) running time to apply suffix extraction on the reduced instance.

Unfortunately, the above structure does not necessarily occur in our random access algorithm. It may be the case that the \(r\)-value of \(i_x\) is arbitrarily smaller than \(r_{i_{x-1}}\), leading to an \(r\)-value smaller than \(j-i\). This means that following the source of the phrase containing \(i_x\) will not necessarily lead to an occurrence of \(S[i..j]\), making any further step following \(i_x\) potentially lose some of the information we are required to extract.

To bypass this problem, we define a modified variant of the epoch procedure. Our epoch procedure takes indices \(i,j\) as input with \(r_i \in [\max(10(j-i),k)..1.5k)\) for some \(k\in \mathbb{K}\). The implied assumption that \(r_i >10(j-i)\) can be enforced as we established in the previous discussion.

The epoch procedure has two outputs. First, it outputs the prefix \(S[i..i')\) for some index \(i'\in [i..j+1]\) (notice that if \(i'=i\), this component of the output is trivial). Additionally, the epoch outputs an index \(i^*\) on which we can recourse, and that makes progress towards a termination condition. That is, the index \(i^*\) has \(S[i^*..j^*] = S[i'..j]\) for \(j^* = i^*-i'+j\), which means that the remaining suffix to be extracted from \(S[i..j]\) occurs at \(i^*\). We also demand that the index \(i^*\) has \(r_{i^*} \in [j-i..k)\), bringing us closer towards the termination condition of the algorithm. The running time is \(O(i'-i + \log \frac{n}{z})\).

For the special case where \(i'=j+1\), we simply have that the epoch procedure extracted \(S[i..j]\) in its entirety, and completing the execution of the extraction query. In this special case, we allow the epoch to consume \(O(j-i+ \log^2\frac{n}{z})\) time. For the formal presentation of the epoch procedure, see 34.

We implement the epoch by essentially running the epoch of the extraction procedure on \(i\). If it happen to result in a gradual decrease in \(r\)-value, we can simply return its output. Otherwise, we carefully analyze the cases that arise from an \(r\)-value below \(j-i\), and exploit the structure that arises in each of these cases to extract some prefix of \(S[i..j]\) while locating an alternative \(i^*\) with a sufficiently small \(r\)-value.

10.1 Suffix Extraction↩︎

. We start by solving the special case where \(j\) is an ending index of a phrase. We assume that the query specifies the phrase \(P\) that ends in index \(j\). We will show a data structure with \(O(z)\) space, \(O(z \log^2 \frac{n}{z})\) construction time, and \(O(j-i)\) query time.

10.1.0.1 Preprocessing and tree structure

In preprocessing time, we compute \(\mathsf{\delta}\text{-}\mathsf{pre}{}(a,b)\) for every phrase \(P=S[a..b]\) in \(O(z\log^2\frac{n}{z})\) using 8. We defined for each \(P=S[a..b]\) a parent phrase \(P'\) as follows. Let \(b'= b - \mathsf{\delta}\text{-}\mathsf{pre}{}(a,b)\). The phrase containing \(b'\) is \(P'\). This defines a forest structure over the phrases of \(\mathcal{Z}\), we compute and store this forest \(T\). Finally, we construct an unweighted ancestor data structure for \(T\).

10.1.0.2 Query

Our query procedure is recursive. Given a query \(S[i..j]\) with the phrase ending at index \(j\), we simply return \(S[j]\) if \(i=j\).

Otherwise, we recurse on the LZ-End phrases strictly contained within \(S[i..j]\). We find the phrases intersecting \(S[i..j]\) in time proportional to their number by simply starting with the phrase \(P=P_y\) ending in \(j\) and traversing \(P_{y-1},P_{y-2}\ldots\) until we reach some \(P_x=[a_x..b_x]\) such that \(a_x\le i\). For every \(p\in[x..y]\) seen in this process, we recursively extract \(S[a_p..b_p]\) by recursing on \(S[a'_p..b'_p]\) where \(a'_p = a_p- \mathsf{\delta}\text{-}\mathsf{pre}{}(a_p,b_p)\) and \(b'_p = b_p-\mathsf{\delta}\text{-}\mathsf{pre}{}(a_p,b_p)\).

The leftmost phrase \(P_x= S[a_x..b_x]\) intersecting \(S[i..j]\) requires special care We use an ancestor query to find the root of the tree containing \(P_x\) in the forest \(T\). Notice that this must be a phrase of length \(1\), so it is equal to a suffix of \(S[a_x..b_x]\) (of length 1) contained within \(S[i..j]\). Further notice that every ancestor of \(P_x\) is an occurrence of some suffix \(S[b_x-\ell..b_x]\) of \(P_x\). Let \(P^1\) be the root of the tree in \(T\) containing \(P_x\). We generate the sequence \(P^1,P^2,\ldots P^{x'}\) of phrases as follows. For \(k \le x\), if \(|P_k| < b_x-i\) we set \(P^{k+1}\) to be the child of \(P^{k}\) in \(T\) towards \(P_x\). Otherwise, if \(|P^k|\ge b_x-i\), we set \(P^{k-1}=P^{x'}\) as the last element of the sequence and terminate. In words, this is the prefix of the path from the root to \(P_x\) that is truncated before the first phrase with length at least \(b_x-i\). Notice that the lengths \(|P^1|,|P^2|,\ldots\) form an increasing sequence.

Denote for every \(k\in[1..x']\) the endpoints \(P^k=S[a^k..b^k]\). The algorithm recurses on \(S[b^k-|P^{k+1}|..b^k - |P^k|]\). Finally for \(P^{x'}\) the algorithm recurses on \(S[b^{x'}-(b_x-i)..b^{x'}-|P^{x'}|]\)

10.1.0.3 Correctness.

Clearly, \(P_{x+1},P_{x+2},\ldots,P_y\) form a suffix of \(P[i..j]\), so extracting each of them leads to the extraction of this suffix.

As for the prefix covered by \(P_x\), we claim that the recursive calls induced by \(P^1,P^2,\ldots P^{x'}\) are for strings that form a partition of \(S[i..b_x]\). More precisely, we claim that for every \(k\in [1..x')\) it holds that \(S[b_x-|P^{k+1}|..b_x-|P^k|]=S[b^k-|P^{k+1}|..b^k-|P^k|]\), and that \(S[i..b_x- |P^{x'}]=S[b^{x'}-(j-b_x)..b^{x'}-|P^{x'}|]\).

This follows immediately from the following stronger property

32 shows that the equality \(S[b_x-|P^{k+1}|..b_x-|P^k|]=S[b^k-|P^{k+1}|..b^k-|P^k|]\) indeed holds. Further notice that the substring \(S[b^k-|P^{k+1}|..b^k-|P^k|]\) ends in a phrase boundary, as \(b^k-|P^k|+1\) is the first index of \(P^k\), so \(.b^k-|P^k|\) is the last index of the phrase preceding \(P^k\).

In conclusion, we have shown that the recursive calls we made are for strings that together form a partition of \(S[i..j]\), and that each of them is smaller than \(S[i..j]\). It follows that the algorithm returns the correct answer, and that it terminates.

10.1.0.4 Complexity.

During the running time of the query, we are either in a termination case of the recursion - and return \(S[j]\) in constant time, or we make \(R\) recursive calls, and work \(O(R)\) time in total to make these calls for some integer \(R>1\).

This process can be described as a tree, where the children of each recursive call are the recursive calls made by it. As every recursive call partition the substring it is responsible for, this tree has \(j-i\) leaves, and each leaf correspond to \(O(1)\) time of the algorithm. Every external node of the tree with degree \(R\) corresponds to a recursive calls which is executed in \(O(R)\) time.

It follows that the total running time is bounded by the number of edges in a tree with \(j-i\) leafs such that all internal degrees are at least 2, which is \(O(j-i)\) as required.

We conclude with the following.

10.2 The General Case↩︎

As in the random access algorithm of 1, our algorithm is partition into epochs, where each epoch may extract some prefix \(S[i..i')\) of \(S[i..j]\), and provide an index \(i^*\) that is an occurrence of \(S[i'..j]\), and \(i^*\) has a significantly lower \(r\)-value than \(i\). An epoch is described as the following procedure.

Given 34 36, we can prove 2.

For the rest of this section, we prove 34. As in the random access algorithm, we split the epoch into a naive part and a stable part. We will reuse a lot of concepts and terminology from the random access algorithm. Let us prove some helpful properties of the \(\mathsf{pre}\) function.

The following two are immediate corollaries of 35

We now present an adjusted version of the naive part of the epoch from the random access algorithm (2).

Similarly to the random access algorithm, we have that the naive part, specified above as 36, may already return a satisfactory output as \(S[i'..j'] = S[i..j]\) with \(r_{i}\in [j-i..k)\). We prove the following useful properties of \(sJ()\).

We proceed to show that in each of the second and the third cases for the output of 36, we can apply an additional procedure to obtain a valid output for 34. We start by providing the following subroutine. Intuitively, we show that if \([i..j]\) contains a phrase boundary, and \(j\) is contained in phrase of length less than \(1.5k\), we can efficiently return a valid output for the epoch.

We now show another case where we can efficiently find a valid output for the epoch. Namely, we show that if we have an occurrence of \(S[i..j]\) such that \(i\in L(P)\), i.e. in the leftmost 2/3 indices of the phrase \(P\) containing \(i\), then we can efficiently find a valid output for the epoch. More precisely: we either find a valid output for the epoch in \(O(i'-i + \log \frac{n}{z})\), or we completely extract all of \(S[i..j]\) in time \(O(\log^2 \frac{n}{z})\). The latter case correspond to the looser bound on the running time allowed in the statement of 34 for the case in which the epoch extracts all of \(S[i..j]\).

We are finally ready to put it all together and prove 34.

References↩︎

---

1. Kreft and Navarro [6] also introduced an algorithm for this case, but their definition of LZ-End is slightly different from the one we use, which is the common definition in recent works on LZ-End.↩︎