Compressed Index with Construction in Compressed Space

Given a string $s$ of length $n$ over the alphabet $\{0,1,\mathrm{\dots },\sigma -1\}$ with $\sigma \le n^{O(1)}$, a compressed index is a data structure that stores $s$ in a compressed form supporting fast substring search. Currently best indexes use $O(\delta \log \frac{n}{\delta \alpha })$ space [34, 35, 32, 33], measured in $O(\log n)$-bit machine words, where $\alpha ={\log }_{\sigma }n$ and $\delta$ is a compression measure called string complexity [47], and they can search a substring of length $m$ in $O(m+(\mathrm{occ}+1){\log }^{ϵ}n)$ time, where $\mathrm{occ}$ is the number of occurrences and $ϵ>0$ is any fixed constant (the big-O in the space bound hides factor $\frac{1}{ϵ}$). This space $O(\delta \log \frac{n}{\delta \alpha })$ is known to be tight for a wide range of parameters [32, 33] and it lowerbounds the space of most dictionary-based compressed indexes such as indexes on the Lempel–Ziv parsing [16, 52], run-length grammars [17, 31], Burrows–Wheeler transform [24], and string attractors [29] (see [43] for an overview).

There are essentially two primary methods to achieve $O(m\log n)$ search time within the space $O(\delta \log \frac{n}{\delta })$, which both enhance the basic idea of Claude and Navarro [18]: (1) a neat scheme [24] first outlined by Gagie et al. [23] that combines the Karp–Rabin hashing [22, 27] and z-fast tries [4, 5]; (2) a variant of the so-called locally consistent parsing [17, 19, 26, 40]. Known indexes that achieve $O(m+{\log }^{ϵ}n)$ search time combine both approaches [17, 33]. Method (1) is applicable for many indexes; unfortunately, it has a serious drawback: the Karp–Rabin hashing must be collision-free for all substrings of length $2^k$, for $k=1,2,\mathrm{\dots }$, and the only known algorithm that verifies this condition uses $O(n)$ space and $O(n\log n)$ time [10], which is prohibitive in use cases where the uncompressed data barely fits into memory. This issue hinders a wider usage of such indexes and it is the reason for the scarcity of experimental studies that try to translate the theoretical state-of-the-art methods to practice (we note that there are many works on construction of indexes, e.g., [1, 20, 28, 37, 50, 51], but they never use the collision-free Karp–Rabin hashing as the best theoretical results do).

We make a step forward to solve this problem by presenting an index with $O(\delta \log \frac{n}{\delta })$ space and $O(m+(\mathrm{occ}+1){\log }^{ϵ}n)$ search time that can be built in $O(n\log n)$ expected time by one left-to-right pass in a streaming fashion with $O(\delta \log \frac{n}{\delta })$ construction space. We do not use the Karp–Rabin hashes and the randomization in the construction can be removed using deterministic dictionaries instead of hash tables (with a slowdown by an $O(\sqrt{\frac{\log n}{\log \log n}})$ factor, see [3, 48]). The result is purely theoretical due to large constants under the big-O but, we believe, its ideas might inspire practical designs. We conjecture that the index can be further improved to $O(\delta \log \frac{n}{\delta \alpha })$ space (also the construction space) and $O(m/\alpha +(\mathrm{occ}+1){\log }^{ϵ}n)$ time in the string packed model (see [11, 41]); this direction is left for a future work.

Throughout, $s$ is the input string of length $n$ with letters $s[0],s[1],\mathrm{\dots },s[n-1]$ from an alphabet $\{0,1,\mathrm{\dots },n^{O(1)}\}$. For $i,j$, let $s[i..j]$ be the substring $s[i]s[i+1]\mathrm{\cdots }s[j]$ (empty if $i>j$). For sequence $t=t_0,t_1,\mathrm{\dots },t_{m-1}$ (maybe a string), denote by $\stackrel{}{t}=t_{m-1},\mathrm{\dots },t_1,t_0$ its reversal. Denote $|t|=m$, $s[i..j)=s[i..j-1]$, $[i..j]=\{i,i+1,\mathrm{\dots },j\}$, $[i..j)=[i..j-1]$.

The string complexity, $\delta$, for $s$ is defined as $\delta =\max \{d_k(s)/k:k\in [1..n]\}$, where $d_k(s)$ denotes the number of distinct substrings of $s$ of length $k$ [35, 47].

We heavily use the concept of blocks: a block $B$ for string $s$ is an object attached to a certain substring $s[i..j]$; denote $𝖻(B)=i$ and $𝖾(B)=j$. The blocks are not “fragments”: two distinct blocks $B$ and $B^{\prime }$ can be attached to the same substring $s[i..j]$. If unambiguous, we treat a block $B$ as a string, writing $|B|$, $B=s[i^{\prime }..j^{\prime }]$ (with not necessarily $i^{\prime }=𝖻(B)$), etc. Two blocks $B$ and $B^{\prime }$ are equal as strings if $s[𝖻(B)..𝖾(B)]=s[𝖻(B^{\prime })..𝖾(B^{\prime })]$. When defining a new block, we usually use words like “generate”, “create”, “copy” (when the new block is a copy of an old one) and it must be clear to which substring the new block is attached. We sometimes treat the concept of blocks loosely but, hopefully, it will be clear from the context.

What follows is a high level description of main ideas behind our index. Details and precise definitions follow. We first focus on a static index. Its construction algorithm is in Section 6.

Recent results on block trees [34, 44] showed that the space $O(\delta \log \frac{n}{\delta })$ for indexes is surprisingly easy to obtain by, roughly, the following scheme (or its variants): one constructs a hierarchy of blocks with $\log n$ levels such that the level-$k$ blocks are $\lceil n/2^k\rceil$ substrings $s[i\cdot 2^k..(i+1)2^k)$ of length $2^k$ (the rightmost block might be shorter) and, for $k>0$, each level-$k$ block has two child blocks from level $k-1$: its prefix and suffix of length $2^{k-1}$, respectively; then, each block $B=s[i\cdot 2^k..(i+1)2^k)$ for which the substring $\overline{B}=s[(i-1)2^k..(i+2)2^k)$ has an occurrence at a position smaller than $(i-1)2^k$ is encoded by a pointer to the leftmost occurrence of $B$ in $s$ and all descendants of $B$ in the hierarchy are removed (for precise and detailed definitions, see [6, 7, 34, 42, 44]). The result is a block tree [6, 42].

After a closer inspection of the proof from [35] of the bound $O(\delta \log \frac{n}{\delta })$ for the block tree size, one can notice that the bound still holds if the block boundaries are slightly “jiggled”. Our idea is to construct a “jiggy block tree”, in which level-$k$ blocks are not of exact size $2^k$ but somewhat close to this “on average”, and each block might have up to $O(\log \log n)$ children. The variability of block lengths will be used to form a kind of locally consistent parsing, more specifically, we will use a “cut” version of the so-called deterministic coin tossing (DCT) [19] and the blocks will be built level by level bottom-up using this “cut DCT” (the idea of such level-by-level construction itself is not novel [46] but it is usually used with the full DCT and it leads to a grammar of size $\mathrm{\Omega }(\delta \log \frac{n}{\delta }{\log }^{\ast }n)$, not to a kind of block tree). Then, the same arguments as in [35] show that the resulting tree has $O(\delta \log \frac{n}{\delta })$ internal nodes. However, some nodes might have up to $\mathrm{\Theta }(\log \log n)$ leaf children, blowing up the space by an $\mathrm{\Omega }(\log \log n)$ factor, which seems unavoidable when using the DCT [12, 39, 40, 46, 49, 50].

We eliminate the factor $\mathrm{\Omega }(\log \log n)$ by introducing a novel intermediate step in the level by level bottom-up construction: given a block $B$ with $O(\log \log n)$ children $B_i,\mathrm{\dots },B_j$, we greedily unite the children from left to right into larger “intermediate blocks” $B^{\prime }=B_m\mathrm{\cdots }{B}_{m+r-1}$ such that the sequence of blocks $B_m\mathrm{\cdots }{B}_{m+r-1}$ occurs somewhere to the left in the block hierarchy; then, we store in the intermediate block $B^{\prime }$ a pointer to this earlier occurrence. Due to the property of “local consistency” of DCT, the pointers will be somewhat “aligned” on the block structure and our jiggly block tree will resemble a grammar with elements of the block tree structure (like a collage system [30] but more structured). There are many details in this scheme to make it efficient that are explained in the sequel.

For the pattern matching, we follow the standard approach based on the locally consistent parsing and z-fast tries [17, 33] but we replace the Karp–Rabin fingerprints [27] with new deterministic fingerprints that are derived from our locally consistent block structure.

At the core of our index is a hierarchy of blocks (see Fig. 1, the leftmost picture): it has $O(\log n)$ levels where the topmost level has one block equal to $s$ and the bottom level $0$ contains $n$ one-letter blocks $s[0],\mathrm{\dots },s[n-1]$; the concatenation of all blocks from one level equals $s$; for $\mathrm{\ell }>0$, each level-$\mathrm{\ell }$ block $B$ either is a copy of a level-$(\mathrm{\ell }-1)$ block $B^{\prime }$ with $𝖻(B)=𝖻(B^{\prime })$ and $𝖾(B)=𝖾(B^{\prime })$ or is the concatenation of corresponding consecutive level-$(\mathrm{\ell }-1)$ blocks. We define the hierarchy of blocks by a bottom-up construction process.

The bottom level-$0$ blocks are $n$ one-letter blocks $s[0],s[1],\mathrm{\dots },s[n-1]$. On a generic step with $k\ge 0$, we have a sequence of blocks $B_1,\mathrm{\dots },B_b$ of level $2k$ whose concatenation is $s$ itself. To produce new blocks of levels $2k+1$ and $2k+2$, the construction process will unite some adjacent blocks or will copy some blocks unaffected; in particular, all blocks of length $>2^k$ are copied to levels $2k+1$ and $2k+2$ unaffected. Every block $B$ is assigned an $O(\log n)$-bit integer identifier $\mathrm{𝗂𝖽}(B)$; the level-$0$ blocks have identifiers equal to the letters they represent (recall that the alphabet is $\{0,1,\mathrm{\dots },n^{O(1)}\}$). Blocks with equal identifiers are equal as strings but the converse is not necessarily true. We choose an arbitrary unambiguous method to encode any pair of $O(\log n)$-bit integers $x,y$ into one $O(\log n)$-bit integer, denoted $⟨x,y⟩$. The process maintains a counter to assign new unique identifiers to new blocks.

The described hierarchy of blocks for $s$ naturally forms a tree $H$ with blocks as vertices in which the root is the (only) topmost block and the parent of any level-$\mathrm{\ell }$ block $B$ with $B\ne s$ is the level-$(\mathrm{\ell }+1)$ block $B^{\prime }$ such that $[𝖻(B^{\prime })..𝖾(B^{\prime })]\supseteq [𝖻(B)..𝖾(B)]$ (note that $B$ and $B^{\prime }$ may be equal as strings). For our index, we create a tree $\widehat{H}$ that is a copy of $H$ with vertices removed according to the following rules 1–4 while it is possible to apply them (see Fig. 1):

1. 1.

   if a level-$0$ block $B$ has parent $B^{\prime }$ with $\mathrm{𝗂𝖽}(B)=\mathrm{𝗂𝖽}(B^{\prime })$, merge $B$ and $B^{\prime }$ by removing $B^{\prime }$ and connecting $B$ to the parent of $B^{\prime }$;

2. 2.

   if, for $\mathrm{\ell }>0$, a level-$\mathrm{\ell }$ block $B$ has parent $B^{\prime }$ with $\mathrm{𝗂𝖽}(B)=\mathrm{𝗂𝖽}(B^{\prime })$, merge $B$ and $B^{\prime }$ by removing $B$ and connecting all children of $B$ to $B^{\prime }$;

3. 3.

   if, for $\mathrm{\ell }>0$ and ${\mathrm{\ell }}^{\prime }>0$, a level-$\mathrm{\ell }$ block $B$ has a “preceding” level-${\mathrm{\ell }}^{\prime }$ block $B^{\prime }$ such that $\mathrm{𝗂𝖽}(B)=\mathrm{𝗂𝖽}(B^{\prime })$ and , remove all descendants of $B$;

4. 4.

   if, for $\mathrm{\ell }>0$, all children of a level-$\mathrm{\ell }$ block $B$ have equal $\mathrm{𝗂𝖽}$, remove them all except for the leftmost child (note that, by removing a child, we remove its descendants).

The idea of such construction is not novel (however, usually the full DCT is used, not the “cut” DCT as we do) and it leads to an index with $\omega (\delta \log \frac{n}{\delta })$ space [12, 39, 40, 46, 49, 50]. As it turns out, the obtained tree has $O(\delta \log \frac{n}{\delta })$ non-leaf vertices and the main issue with space is due to some vertices having up to $O(\log \log n)$ leaves from levels $2k+1$. To reduce the space, our idea is to parse the sequences of leaves by a specialized variant of LZ77 [52]. The construction is quite technical and requires some preparations to define it.

Let $B_1,\mathrm{\dots },B_b$ be all blocks on a level $2k+1$. Recall that the block construction process has marked some of the blocks, thereby splitting them into ranges $B_i,\mathrm{\dots },B_j$, where $B_i,\mathrm{\dots },B_{j-1}$ are unmarked and $B_j$ is marked. Fix such range $B_i,\mathrm{\dots },B_j$ with such that $B_i,\mathrm{\dots },B_j$ were not removed from $\widehat{H}$ after the rules 1–4 above. Let $B$ be the parent of $B_i,\mathrm{\dots },B_j$. We are to parse $B_i,\mathrm{\dots },B_j$ into subranges. To define the parsing, we need some notation.

For any block $B_m$ and $\mathrm{\ell }\ge 0$, choose the largest $h\le \mathrm{\ell }$ such that, for all $h^{\prime }\in [m-h..m)$, $B_{h^{\prime }}$ is not marked; define $𝗅𝖾𝖿𝗍(m,\mathrm{\ell })$ as the sequence $\beta ,\mathrm{𝗂𝖽}(B_{m-h}),\mathrm{𝗂𝖽}(B_{m-h+1}),\mathrm{\dots },\mathrm{𝗂𝖽}(B_{m-1})$, where $\beta$ is empty (i.e., it is really not in the sequence) if $h=\mathrm{\ell }$, and $\beta$ is a special symbol $\$$ if . Choose the largest $h\le \mathrm{\ell }$ such that, for all $h^{\prime }\in [m..m+h-1)$, $B_{h^{\prime }}$ is not marked (but $B_{m+h-1}$ may be marked); define $𝗋𝗂𝗀𝗁𝗍(m,\mathrm{\ell })$ as the sequence $\mathrm{𝗂𝖽}(B_m),\mathrm{𝗂𝖽}(B_{m+1}),\mathrm{\dots },\mathrm{𝗂𝖽}(B_{m+h-1})$.

We greedily parse $B_i,\mathrm{\dots },B_j$ into subranges from left to right: suppose that $B_i,\mathrm{\dots },B_{m-1}$ have already been parsed (initially $m=i$), let $B_m,\mathrm{\dots },B_{m+r-1}$ be the longest subrange with $m+r-1\le j$ for which there is such that $𝗅𝖾𝖿𝗍(m^{\prime },4r)=𝗅𝖾𝖿𝗍(m,4r)$ and $𝗋𝗂𝗀𝗁𝗍(m^{\prime },5r)=𝗋𝗂𝗀𝗁𝗍(m,5r)$ (note that $\mathrm{𝗂𝖽}(B_m),\mathrm{\dots },\mathrm{𝗂𝖽}(B_{m+r-1})$ must be a prefix of $𝗋𝗂𝗀𝗁𝗍(m,5r)$); let $r=1$ if there is no such $B_m,\mathrm{\dots },B_{m+r-1}$; once $r$ is determined, we have obtained a new subrange $B_m,\mathrm{\dots },B_{m+r-1}$ and we continue the parsing for $B_{m+r},\mathrm{\dots },B_j$, assigning $m:=m+r$.

Define a new tree $J$, called the jiggly block tree, that is a copy of $\widehat{H}$ with the following modifications. For each level $2k+1$, we consider each range $B_i,\mathrm{\dots },B_j$ as described above such that all $B_i,\mathrm{\dots },B_j$ were not removed from $\widehat{H}$ after the rules 1–4, and we parse $B_i,\mathrm{\dots },B_j$ into subranges as described above; for each subrange $B_m,\mathrm{\dots },B_{m+r-1}$ with $r>1$, we remove from $J$ the blocks $B_m,\mathrm{\dots },B_{m+r-1}$ (which are children of $B$) and insert in their place a new block $B^{\prime }$ with parent $B$ and no children; $B^{\prime }$ is called intermediate. We do not assign $\mathrm{𝗂𝖽}$ to $B^{\prime }$.

By a simple analysis, one can show that any “original” block $B$ of $H$ cannot disappear from $J$, always a copy of $B$ remains, which is formalized as follows (the proof is in Appendix B).

To support the basic navigation on the string $s$, the tree $J$ is equipped as follows. Each non-intermediate block $B$ in $J$ stores $𝖻(B)$, $𝖾(B)$, $\mathrm{𝗂𝖽}(B)$, pointers to children of $B$, and the lowest level $\mathrm{\ell }(B)$ on which a block with identifier $\mathrm{𝗂𝖽}(B)$ was created in $H$. For each non-leaf block $B$ in $J$, two cases are possible: (1) $B$ has children $B_i^{\prime },\mathrm{\dots },B_j^{\prime }$ in $J$ (some of which might be intermediate blocks inserted in place of old children of $B$ from $H$) whose concatenation, if viewed as strings, equals $s[𝖻(B)..𝖾(B)]$ (i.e., no “gaps” between the children); (2) $B$ has only one child $B^{\prime }$ and all removed children had the same identifiers $\mathrm{𝗂𝖽}(B^{\prime })$, i.e., $B$ was a run block with exactly $|B|/|B^{\prime }|$ children in $H$. If a block $B$ in $J$ with $|B|>1$ has no children, then either $B$ is intermediate or, by Lemma 5, there is a block $B^{\prime }$ with children in $J$ such that $\mathrm{𝗂𝖽}(B^{\prime })=\mathrm{𝗂𝖽}(B)$. In the latter case, we store in $B$ a pointer to $B^{\prime }$; observe that if $B$ is from a level $\mathrm{\ell }$, then all children $B_i^{\prime },\mathrm{\dots },B_j^{\prime }$ of $B^{\prime }$ are from levels $\le \mathrm{\ell }-1$ since, by Lemma 4, $B$ and $B^{\prime }$ originate from blocks created on the same level in the hierarchy $H$. Hence, when one moves from the level-$\mathrm{\ell }$ block $B$ to $B^{\prime }$ and, then, to a child of $B^{\prime }$, the level decreases to at most $\mathrm{\ell }-1$. Thus, if there are no intermediate blocks in $J$, one can read $s[𝖻(B)..𝖾(B)]$ for any block $B$ in $J$ in $O(|B|)$ time by naively descending in $J$ as in grammar indexes [17].

Consider an intermediate block $B$ in $J$ from a level $2k+1$. By construction, it has no children in $J$. Let $B^{\prime }$ be its parent. Denote by $B_1,\mathrm{\dots },B_b$ all blocks from level $2k+1$ in the hierarchy $H$; we mark them according to conditions (a) and (b) from Section 3 so that we can use the notation $𝗅𝖾𝖿𝗍$ and $𝗋𝗂𝗀𝗁𝗍$ from now on. Suppose that $B^{\prime }=B_i\mathrm{\cdots }{B}_j$, where $B_i,\mathrm{\dots },B_j$ is the range of blocks from which $B^{\prime }$ was produced in $H$. Since $B$ is intermediate, we have $B=B_m\mathrm{\cdots }{B}_{m+r-1}$, for some $m$ and $r$ such that $[m..m+r)\subseteq [i..j]$. By construction, there is with $𝗅𝖾𝖿𝗍(m^{\prime },4r)=𝗅𝖾𝖿𝗍(m,4r)$ and $𝗋𝗂𝗀𝗁𝗍(m^{\prime },5r)=𝗋𝗂𝗀𝗁𝗍(m,5r)$. Choose the smallest $m^{\prime \prime }$ such that $𝗋𝗂𝗀𝗁𝗍(m^{\prime \prime },r)=𝗋𝗂𝗀𝗁𝗍(m,r)$. Obviously, $m^{\prime \prime }\le m^{\prime }$. Let $B_{i^{\prime }},\mathrm{\dots },B_{j^{\prime }}$ be a range of blocks in $H$ such that $i^{\prime }\le m^{\prime \prime }\le j^{\prime }$, and let $\widehat{B}$ be a block on level $2k+2$ produced from this range. Since $𝗋𝗂𝗀𝗁𝗍(m^{\prime \prime },r)=𝗋𝗂𝗀𝗁𝗍(m,r)$, the definition of $𝗋𝗂𝗀𝗁𝗍$ implies that the blocks $B_{m^{\prime \prime }},\mathrm{\dots },B_{m^{\prime \prime }+r-2}$ are unmarked and, therefore, $[m^{\prime \prime }..m^{\prime \prime }+r)\subseteq [i^{\prime }..j^{\prime }]$. Since $m^{\prime \prime }$ is the smallest such index, $\widehat{B}$ must be the leftmost block in $H$ from level $2k+2$ produced from the sequence $\mathrm{𝗂𝖽}(B_{i^{\prime }}),\mathrm{\dots },\mathrm{𝗂𝖽}(B_{j^{\prime }})$, which, by Lemma 4, implies that $\widehat{B}$ is the leftmost block with the identifier $\mathrm{𝗂𝖽}(\widehat{B})$ in the whole hierarchy $H$. By Lemma 5, the block $\widehat{B}$ was retained in $J$ and has children in $J$. We store in $B$ a pointer to $\widehat{B}$ and the following numbers required to identify the location of the copy of $B=B_m\mathrm{\cdots }{B}_{m+r-1}$ among the children of $\widehat{B}$: $\mathrm{𝗈𝖿𝖿}(B)=m^{\prime \prime }-i^{\prime }$ and $𝗋(B)=r$. (Note that $\widehat{B}$ might coincide with $B^{\prime }$, albeit it is unusual.)

Some subranges of blocks in the range $B_{i^{\prime }},\mathrm{\dots },B_{j^{\prime }}$ could be replaced with intermediate blocks in $J$. We claim that any such intermediate block ${\widehat{B}}^{\prime }$ that replaced some of the blocks $B_{m^{\prime \prime }},\mathrm{\dots },B_{m^{\prime \prime }+r-1}$ has $𝗋({\widehat{B}}^{\prime })\le r/2$. Suppose, to the contrary, that ${\widehat{B}}^{\prime }=B_{\widehat{m}}\mathrm{\cdots }{B}_{\widehat{m}+\widehat{r}-1}$ is such that $\widehat{r}=𝗋({\widehat{B}}^{\prime })>r/2$ and $[\widehat{m}..\widehat{m}+\widehat{r})\cap [m^{\prime \prime }..m^{\prime \prime }+r)\ne \mathrm{\varnothing }$. Since $4\widehat{r}>r$, the concatenation of the sequences $𝗅𝖾𝖿𝗍(\widehat{m},4\widehat{r})$ and $𝗋𝗂𝗀𝗁𝗍(\widehat{m},5\widehat{r})$ contains the sequence $\mathrm{𝗂𝖽}(B_{m^{\prime \prime }}),\mathrm{\dots },\mathrm{𝗂𝖽}(B_{m^{\prime \prime }+r-1})$. Hence, by construction, there is such that $𝗋𝗂𝗀𝗁𝗍(m^{\prime \prime \prime },r)=𝗋𝗂𝗀𝗁𝗍(m^{\prime \prime },r)$, which contradicts the minimality of $m^{\prime \prime }$. This claim implies that, for an intermediate block $B$ in $J$, one can compute all $r$ children of $B$ from the original hierarchy of blocks $H$ in $O(r)$ time by the simple traversal of pointers in $J$. Since, by Lemma 3 (local sparsity), any block $B$ has $O({\sum }_{k=1}^{\mathrm{\infty }}|B|/2^k)=O(|B|)$ descendants in the hierarchy $H$, we obtain the following result.

Let us augment the jiggly block tree $J$ to support searching in $s$. Our approach is standard but with modifications since we will not use Karp–Rabin fingerprints [27]. Instead, we invent somewhat analogous deterministic fingerprints. Throughout, we use hash tables supporting queries in $O(1)$ time [9]. Let us fix a string $t$ of length $m$, the pattern to search.