Wavelet Forests Revisited

Consider a string $S\in {[0..\sigma )}^n$ of length $n$ over the integer alphabet $[0..\sigma )$.

• $\mathrm{■}$

  Given any $i\in [0..n]$ and any symbol $c\in [0..\sigma )$, the rank query returns the value ${\mathrm{rank}}_S(i,c):=|\{j\in [1..i]:S[j]=c\}|$, i.e., the number of occurrences of $c$ in $S[1..i]$;

• $\mathrm{■}$

  Given any $r\in {\mathbb{Z}}_{\ge 1}$ and any symbol $c\in [0..\sigma )$, the select query returns the value ${\mathrm{select}}_S(r,c)$, defined as the $r$th smallest element of the set $\{i\in [1..n]:S[i]=c\}$. If the size of this set is less than $r$, we set ${\mathrm{select}}_S(r,c)=\mathrm{\infty }$.

Rank and select queries are among the most basic queries on sequences. They form the backbone of many compressed data structures for strings [12, 21, 35, 14, 24, 26, 25]. They are also core components of space-efficient representations of more complex data types, including permutations, parentheses, document collections, trees, graphs, and grids [32, 31, 11, 19, 15].

One of the most efficient data structures supporting rank and select queries is the wavelet tree, invented by Grossi, Gupta, and Vitter [20]. For a string $S\in {[0..\sigma )}^n$, wavelet trees use $𝒪(n\log \sigma )$ bits and support rank and select queries in $𝒪(\log \sigma )$ time.¹¹1Space of wavelet trees can also be bounded in terms of the $k$th-order empirical entropy $H_k(S)$ of $S$ [20]. Efficient implementations of wavelet trees have been the subject of intense study, and multiple highly efficient solutions have been designed, optimizing many aspects of wavelet trees, including space usage, query time, construction time, and working space, both in theory and in practice [5, 16, 22, 38, 1, 30, 17, 28, 36, 7, 8, 9, 3, 10, 27].

In this paper, we focus on a particular wavelet-tree implementation called a wavelet forest [18].²²2The technique introduced in [18] is also called fixed-block compression boosting. The basic idea behind wavelet forests is to partition the input sequence into blocks and construct a wavelet tree for each block, while also maintaining global rank values at block boundaries; these boundaries are then grouped into larger hierarchies such as superblocks and hyperblocks. Simply splitting the sequence and constructing a standalone wavelet tree for every block – even using state-of-the-art wavelet-tree implementations – does not yield a significant improvement. However, it is shown in [18] that, when this idea is combined with several algorithmic improvements (including alphabet mapping at the block and superblock levels, merging the bitvectors of all wavelet trees into one, sharing lookup tables, dynamic selection of blocks in each superblock, pointerless tree navigation, etc.), wavelet forests achieve excellent performance, leading to new state-of-the-art results for rank queries. A unique advantage of wavelet forests is their adaptability: they achieve strong practical performance regardless of the underlying sequence type. In particular, they work well on both non-repetitive and highly repetitive input texts, making them an excellent off-the-shelf choice in many applications. The implementation of the wavelet forest from [18] is part of the SDSL library – a powerful and flexible library of succinct data structures [17].³³3Available at https://github.com/simongog/sdsl-lite. However, the implementation of the wavelet forest in [18] supports only rank queries and lacks support for select queries. Until now, it has not been known whether the strong practical performance of wavelet forests also extends to select queries and, if so, at what cost.

In this section, we describe the basic idea behind the wavelet forest [18] and introduce the notation used in the subsequent sections. At a high level, a wavelet forest represents the input text by partitioning it into blocks and building a separate wavelet tree for each block. This approach is justified theoretically by the fixed-block boosting theorem proved in [18].

The input text is partitioned hierarchically into blocks, superblocks, and hyperblocks. Blocks have size $b$, superblocks have size $b_s$, and hyperblocks have size $b_h$, where $b$ divides $b_s$ and $b_s$ divides $b_h$. Thus, each superblock contains $b_s/b$ blocks, and each hyperblock contains $b_h/b_s$ superblocks. In the default wavelet-forest implementation, the superblock size is set to $2^{20}$. Technically, wavelet forests also allow variable-sized blocks, which can improve space efficiency. For clarity, however, we restrict the discussion here to fixed-size blocks.

For each block, superblock, and hyperblock, we store rank information at its left boundary, that is, at the first position of the corresponding range. We refer to this value as the rank at the block, rank at the superblock, and rank at the hyperblock, respectively. These values are represented by arrays $A_b$, $A_s$, and $A_h$. More specifically, let $c$ be a symbol. Then the rank of $c$ at hyperblock $i_h$ is given by $A_h[c,i_h]$. If superblock $i_s$ is contained in hyperblock $i_h$, then the rank of $c$ at superblock $i_s$ is $A_h[c,i_h]+A_s[c,i_s]$. Similarly, if block $i_b$ is contained in superblock $i_s$ and hyperblock $i_h$, then the rank of $c$ at block $i_b$ is $A_h[c,i_h]+A_s[c,i_s]+A_b[c,i_b]$. In other words, these arrays store rank values in a hierarchical, relative form.

Each block is represented by its own wavelet tree, which can be located via superblock and block headers. These wavelet trees are pointerless and Huffman-shaped, and encode their blocks independently of the rest of the text. Moreover, because each wavelet tree is built only for the local alphabet of its block, its height can be smaller than $\log \sigma$.

To further improve query time, the wavelet forest may also use navigational block headers. When enabled, each block stores prefix-rank information for the nodes at each level of its wavelet tree. This reduces the number of bitvector rank queries required during traversal and can speed up traversals used by both rank and select queries.

In this section, we describe how we implemented select queries on wavelet forests. We first provide an outline of the procedure and then describe each step in more detail. To compute ${\mathrm{select}}_S(j,c)$, i.e., the position of the $j$th occurrence of $c$ in $S\in {\mathrm{\Sigma }}^n$, we proceed as follows:

1. 1.

   Identify $i_h$, the index of the hyperblock containing the $j$th occurrence of $c$ in $S$.

2. 2.

   Identify $i_s$, the index of the superblock containing the $j$th occurrence of $c$ in $S$.

3. 3.

   Identify $i_b$, the index of the block containing the $j$th occurrence of $c$ in $S$. Let $j^{\prime }$ denote the localized select query argument relative to the block. In other words, let $j^{\prime }=j-{\mathrm{rank}}_S((i_b-1)b,c)$.

4. 4.

   Navigate the wavelet tree of that block to reach the leaf that corresponds to $c$ while maintaining a stack of nodes on the path to that leaf.

5. 5.

   Navigate back up the same wavelet tree using the standard wavelet-tree select algorithm with $j^{\prime }$ as the query argument. Let $k$ denote the result of this localized select query.

6. 6.

   Return $(i_b-1)b+k$.

In the first step, we determine the hyperblock index $i_h$ by binary searching the array of hyperblock ranks. More precisely, $i_h$ is the largest hyperblock index such that , where $A_h[c,i]$ stores the rank of $c$ at the beginning of the $i$th hyperblock.

In the second step, we determine the superblock index $i_s$ by binary searching only among the superblocks contained in hyperblock $i_h$. Thus, $i_s$ is the largest index in the range $((i_h-1)b_h/b_s..i_h{b}_h/b_s]$ such that .

In the third step, we determine the block index $i_b$ by scanning the block headers of superblock $i_s$ from right to left. Here, a linear scan is necessary because not every block stores the rank of every symbol. A right-to-left scan is preferable to a left-to-right scan because it stops as soon as it reaches the first block whose rank of $c$ is smaller than $j$. Accordingly, $i_b$ is the largest block index in the range $((i_s-1)b_s/b..i_s{b}_s/b]$ such that . Equivalently, $i_b$ is the first block encountered by the right-to-left scan whose rank of $c$ is smaller than $j$. Once $i_b$ is known, we compute the localized query value $j^{\prime }=j-{\mathrm{rank}}_S((i_b-1)b,c)$.

In the fourth step, we access the wavelet tree of block $i_b$ and descend to the leaf corresponding to $c$. This step is needed because the wavelet forest is pointerless, so before starting the localized select query, we must explicitly walk from the root to the correct leaf. During this traversal, we compute the relevant node information on the fly. The traversal is similar to the one used for rank queries, except that it does not perform a bitvector-rank operation at each node. Because the next step backtracks from the leaf to the root, we store the necessary node information in a stack as we descend. The stack can be stored in a small array. Recall that the individual wavelet trees are Huffman-shaped. The minimum total weight of a Huffman tree of height $h$ is attained by leaf weights $1,F_1,F_2,\mathrm{\dots },F_h$, where $F_i$ is the $i$th Fibonacci number and $F_1=F_2=1$. Hence, the minimum block length that can induce height $h$ is $1+{\sum }_{i=1}^h{F}_i=F_{h+2}$. Therefore, for blocks of size at most $2^{16}$, the height is at most $22$, because .

In the fifth step, we perform a localized select query with argument $j^{\prime }$ on the wavelet tree of block $i_b$. This is exactly the standard wavelet-tree select algorithm [20], applied to the canonical Huffman-shaped wavelet tree of a single block. The algorithm uses the stack built in the previous step to recover the required node information while backtracking from the leaf to the root. We denote the resulting local position by $k$.

Finally, in the sixth step, we return $(i_b-1)b+k$. Here, $(i_b-1)b$ is the number of positions preceding block $i_b$, and $k$ is the position of the desired occurrence within that block.