Adaptive encodings for small and fast compressed suffix arrays Journal: TALG CCS: Theory of computation Data compression CCS: Applied computing Computational genomics CCS: Theory of computation Pattern matching Diego Díaz-Domínguez, Veli Mäkinen Abstract . Compressed suffix arrays index large repetitive collections and are widely used in bioinformatics, version control, and natural language processing. The r r -index and its variants combine the run-length Burrows–Wheeler transform (BWT) with a sample of the suffix array to achieve space proportional to the number of equal-symbol runs. While effective for near-identical strings, their size grows quickly when edited copies are added to the collection as the number of BWT runs is sensitive to variation. Existing approaches either apply extra compression at the cost of slower queries or prioritize speed at the expense of space, limiting practical tradeoffs at large scale. We introduce variable-length blocking (VLB), an adaptive encoding for BWT-based compressed suffix arrays. Our technique adapts the amount of indexing information to the local run structure: compressible regions retain less auxiliary data, while incompressible areas store more. Specifically, we recursively partition the BWT until each block contains at most w w runs (a parameter), and organize the blocks into a tree. Accessing a position requires descending a root-to-leaf path followed by a short run scan. Compressible regions are placed near the root, while incompressible regions lie deeper and are augmented with additional indexing data to speed up access. This strategy balances space and query speed by reallocating bits saved in compressible areas to accelerate access to incompressible ones. The VLB-tree also improves memory locality by colocating related BWT and suffix array information. Backward search relies on rank and successor queries over the BWT. We introduce a sampling technique that relaxes global correctness by guaranteeing that these queries are correct only along valid backward-search states. This restriction reduces space usage without affecting the speed or correctness of pattern matching. We further extend the concepts of the VLB-tree to encode suffix array samples and then to the subsampled r r -index ( s ​ r sr -index), thus producing a small fully-functional compressed suffix array. Experiments show that VLB-tree variants outperform the r r -index and s ​ r sr -index in query time, while retaining space close to that of the s ​ r sr -index. The move data structure, a recent encoding, achieves better speed performance than the VLB-tree but uses considerably more space, yielding a clear space–time tradeoff. 1. Introduction The search for patterns in large collections of strings is a fundamental task in information retrieval, data mining, and bioinformatics. This problem has been studied for decades, producing iconic solutions such as the suffix array ( 22 ) or the suffix tree ( 29 ) , but our ability to accumulate textual data has far exceeded the limits of those solutions, motivating the development of compressed indexes. Large collections are often repetitive, and these repetitions induce regularities in suffix arrays and trees that the compressed variants exploit to reduce space. However, the continuous accumulation of data and the development of new technologies have led to the creation of even larger collections that can reach the terabyte scale, and even compressed solutions fall short in this context. Compressed suffix arrays are space-efficient indexes that support the same two basic queries as plain suffix arrays: count and locate the occurrences of a pattern in a text. Several variants have been proposed ( 16 ; 26 ; 12 ) , with the FM index ( 11 ) being the most widely used. The FM index represents a string S[1..n] via the Burrows–Wheeler transform (BWT) ( 5 ) plus a sample of the suffix array SA[1..n] of S , and fits in nH_{k}(S)+o(n\log\sigma) bits, where H_{k} is the k -th order entropy of S and \sigma is the alphabet size. Given a pattern P[1..m] , it reports the occ matches in O(m\log\sigma+occ\log^{1+\epsilon}n) time for any constant \epsilon>0 . In practice, its space is close to n\log\sigma bits, far below the n(\log\sigma+\log n) bits needed to support count and locate with S and the plain suffix array. This efficiency has made the FM index a workhorse in genomics ( 20 ; 18 ) , yet even space close to the plain-text representation can be prohibitive at massive scales. The r -index of Gagie et al. ( 12 ) is a variant of the FM index that reduces the space to O(r) by run-length encoding the BWT and sampling 2r elements of the SA, where r is the number of equal-symbol runs in the BWT. In collections of near-identical sequences, r is much smaller than n , achieving important space reductions that have motivated new r -index-based data structures ( 4 ; 25 ; 7 ; 1 ; 30 ; 27 ; 10 ) for genomic analysis. However, the BWT is sensitive to edits, as a single text modification can increase r by a \Theta(\log n) factor ( 13 ) . The sensitivity rapidly increases r with new variation until the r -index approaches the size of the FM index ( 6 ) . This poses a problem for terabyte-scale collections, where the level of repetitiveness is often not extreme. An important observation is that runs are distributed unevenly, with some BWT areas having few long runs, while others have many short runs; the suffix array samples of the r -index show a similar locality. This property makes uniform encoding inefficient and motivates adaptive schemes. Existing approaches only partially exploit this idea: the fixed block boost of Gog et al. ( 15 ) breaks the BWT into equal-length blocks and encodes them independently, while the subsampled r -index (or sr -index) of Cobas et al. ( 6 ) discard values of SA from text areas where the sampling is dense. These techniques help but remain coarse or limited in scope. Another challenge is query speed, as searching for long patterns in BWT-based indexes triggers multiple cache misses. The move data structure of Nishimoto and Tabei ( 23 ) alleviates this problem by reorganizing the run-length BWT data in a cache-friendly manner, achieving significantly faster queries than the r -index but at the cost of being 2-2.5 times larger ( 2 ; 9 ) . Thus, existing work splits into two directions: minimizing space ( sr -index) or maximizing speed ( move ), with no structure achieving both. Our contribution. We present variable-length blocking (VLB), a technique for representing BWT-based compressed suffix arrays that balances query speed and space usage. We exploit the skewed distribution of BWT runs to redistribute indexing costs. We recursively divide the BWT into variable-length blocks so that each block contains a bounded number of runs, and organize the output in a hierarchical structure (the VLB-tree). Compressible blocks remain near the root and require little auxiliary data, while less compressible regions induce deeper subtrees enriched with additional indexing information. This non-uniform layout reallocates space from areas where access is fast to areas where queries are more expensive, yielding a structure whose depth and space adapts to the compressibility of the BWT. • The VLB-tree (Section 3 ): we formalize the VLB-tree and analyze its performance. Given a block size \ell , branching factor f , and run threshold w , a query traverses a tree path of height O(\log_{f}(\ell/w)) and scans at most w consecutive runs in a leaf. Counting the occurrences of a pattern P[1..m] takes O(m(\log_{f}(\ell/w)+w)) time. Importantly, processing each query symbol incurs approximately one cache miss in sparse BWT regions and up to \log_{f}(\ell/w) cache misses in dense, high-run regions, assuming w consecutive runs fit the cache. • Counting with toehold (Section 4 ): we integrate suffix array samples within the VLB-tree so that an occurrence of the pattern can be extracted cache-efficiently while counting. Similarly to the r -index, this occurrence serves as a toehold to decode the other text positions. • VLB-tree sampling (Section 5 ): we introduce a sampling mechanism for rank and successor queries; core operations for pattern matching. The sampled data relax global correctness, only guaranteeing correct answers when the output induces a BWT range that is reachable during pattern matching. By exploiting the invariants of backward search, we reduce index space without affecting the pattern-matching speed or correctness. This relaxation principle is independent of VLB and may be applicable to other indexing schemes. • VLB-tree for \phi^{-1} (Section 6 ): we extend the VLB-tree to represent the \phi^{-1} function, which decodes the occurrences of a pattern from its toehold. The combined VLB-trees of the BWT and \phi^{-1} yield a compressed suffix array equivalent to the r -index. Section 7 describes how to subsample this representation to produce a cache-friendly sr -index, including a fast variant that speeds up the location of pattern occurrences. We implemented two VLB-based data structures: a run-length BWT supporting count queries and a fast sr -index supporting both count and locate . Our experiments show speedups of up to 5.5 for count queries and 9.77 for locate queries over state-of-the-art alternatives. In terms of space, our run-length BWT achieves up to a 2-fold reduction, while our sr -index requires space comparable to that of Cobas et al. ( 6 ) . Although the move data structure ( 23 ; 2 ) attains faster query times, it does so at the cost of being typically 2.55 – 8.33 times larger, yielding a less favorable space–time tradeoff. Finally, cache-miss measurements indicate that the performance gains of our framework are largely due to its cache-aware hierarchical layout, underscoring its practical impact. 2. Preliminaries Strings. A string S[1..n] is a sequence of n symbols over an alphabet \Sigma=\{1,2,\ldots,\sigma\} , where the smallest symbol is a sentinel 1=\$ that appears only at the end ( S[n]=\$ ). A run is a maximal equal-symbol substring S[h..t]=c^{t-h+1} , with head S[h] and tail S[t] . The run-length encoding of S[1..n]=c_{1}^{l_{1}}c_{2}^{l_{2}}{\cdots}c_{r}^{l_{r}} is rle(S)=(c_{1},l_{1})(c_{2},l_{2})\ldots(c_{r},l_{r}) . Operations over sequences. For c\in\Sigma , rank_{c}(S,i) is the number of occurrences of c in S[1..i] , and select_{c}(S,j) is the position of the j -th occurrence of c in S . The queries succ_{c}(S,j) and pred_{c}(S,j) return the nearest occurrence of c at or after j , and at or before j , respectively (returning n+1 and 0 if no such occurrence exists). 2.1. The suffix array The suffix array SA[1..n] ( 22 ) is a permutation of [1..n] that lists the suffixes of S in increasing lexicographic order. Its inverse ISA[1..n] stores positions such that ISA[j]=i iff SA[i]=j . The SA supports two fundamental queries. The operation count(P[1..m]) returns the number of occurrences of P\in\Sigma^{*} in S , and locate(P[1..m]) returns the set \mathcal{O}\subset[n] of indices such that for each i\in\mathcal{O} , S[i..i+m-1]=P[1..m] . A concept related to the suffix array is the \phi^{-1} function: Definition 2.1. (Definition 2 ( 12 ) ) Let i be a text position and let ISA[i]=j be the corresponding index for SA[j]=i . The function \phi^{-1} is a permutation of [1..n] defined as \phi^{-1}(i)=\begin{cases}SA[j+1]=SA[ISA[i]+1]&\text{ if }jSA[j] , SA[j] falls within a valid prefix and Equation 3 still applies. (3) If V[a]=0 and b+M[rank_{0}(V,a)]\leq SA[j] , then SA[j] falls within an invalid area and \phi(SA[j]) is recovered via LF steps. This scheme ensures that LF traversal is only used when strictly necessary, significantly reducing query time in practice. Figure 1 illustrates the components of the sr -index and its fast variant. 3. The VLB-tree: an adaptive representation of the BWT A single random edit in the text typically creates multiple new short runs in the BWT. This happens because even a local modification may change the lexicographic order of many suffixes, which ultimately determines the ordering of symbols in the BWT. As a consequence, small edits may have a disproportionate impact on the number of BWT runs r , directly increasing the space usage of the r -index, whose size depends on that number. A key observation, however, is that these newly created short runs are not distributed uniformly across the BWT. In practice, some regions remain highly compressible after edits, while others become locally irregular. This phenomenon is also reflected in the BWT’s ability to benefit from block-based compression, where independent zeroth-order encoding of blocks can still achieve high-order compression ( 11 ) . The r -index does not fully exploit this property, as it treats all runs uniformly, regardless of their local density or distribution. This motivates an adaptive representation that varies its granularity according to the local distribution of runs, keeping compressible regions compact while recursively refining irregular ones. We now introduce variable-length blocking (VLB) to form a hierarchical representation of the BWT that realizes this adaptive strategy (the VLB-tree). Our encoding naturally enables a more cache-friendly layout, as large compressible regions can be processed with minimal memory accesses, while irregular regions are explored only when necessary. 3.1. Overview of the VLB-tree The VLB-tree decomposes L into blocks whose sizes adapt to the local distribution of runs: • Compressible regions (few runs) are stored in large leaf blocks. • Irregular regions (many runs) are subdivided recursively until their fragments have a manageable number of runs. We begin by dividing L into n/\ell blocks L_{1},L_{2},\ldots,L_{n/\ell} of size \ell , processed from left to right. For each L_{b} , we compute rle(L_{b}) and compare its number of runs to a threshold w , the maximum allowed in a leaf. Compressible blocks If rle(L_{b}) has fewer than w runs, we try to extend it by concatenating consecutive blocks L_{b}{\cdots}L_{b+z-1} . We increase z while rle(L_{b,b+z-1}) has at most w runs and stop when rle(L_{b,b+z}) exceeds this threshold. The fragment rle(L_{b,b+z-1}) becomes a leaf superblock whose parent is the root of the tree. Incompressible blocks If rle(L_{b}) has more than w runs, L_{b} is considered incompressible and is subdivided. Given a branching factor f , we split L_{b} into f equal-length parts of size |L_{b}|/f and process them recursively from left to right using the same merging-and-splitting rule. Some parts may merge into a leaf superblock; others may subdivide further. The process adapts automatically to the local run structure. The resulting structure places highly compressible regions close to the root, yielding small access costs, while irregular regions are recursively refined and incur access costs that reflect their local run complexity. Recursive partitioning by a constant factor f simplifies navigation to the appropriate fragment of the BWT. Given a position L[i] , we compute the top-level block b=\lceil i/\ell\rceil , its local position i^{\prime}=i-(b-1)\ell , and apply the same procedure recursively with block size \ell/f until a leaf is reached. At the same time, the formation of superblocks reduces the number of nodes and thus the space overhead. Data removed by merging blocks is recomputed on the fly by scanning up to w runs in a cache-friendly manner, which remains practical when w is small. The only problem with superblocks is that they break direct index-based access to the BWT. We restore efficient navigation by storing compact bitvectors that map positions recursively to the correct child blocks. 3.2. Layout and access in the VLB-tree Leaves of the VLB-tree store BWT fragments, while internal nodes store routing information that enables efficient navigation to these fragments. Let L^{u} denote the recursive fragment of L associated with a node u . If u is not the root, there exists a parent node v whose fragment L^{v} was partitioned into equal-length blocks, and where one of its blocks L^{v}_{b} corresponds to the start of L^{u} . Let \Sigma^{v}=[1..\sigma^{v}] be the alphabet of L^{v} , and let \Sigma^{u}\subseteq\Sigma^{v} be the subset of symbols appearing in L^{u} . The operator alphacomp(L^{u}) maps the symbols of \Sigma^{u} to the compact alphabet [1..\sigma^{u}] . Unless stated otherwise, symbols in L^{u} are referred to using their compacted identifiers. Each node stores its local alphabet, which typically becomes smaller at deeper levels of the tree. Several auxiliary structures are defined with respect to \Sigma^{u} ; the first is a prefix-count array used to answer rank queries. Thus, the first two components stored at node u are: • A bitvector A[1..\sigma^{v}] that sets A[c]=1 if the parent symbol c\in\Sigma^{v} appears in L^{u} . • A prefix-count array O[1..\sigma^{u}] where the symbols of \Sigma^{u} are indexed in compacted form. For each parent symbol c\in\Sigma^{v} with A[c]=1 , O[rank_{1}(A,c)] stores the number of occurrences of c in L^{v}_{1,b-1} . The remaining components depend on whether u is a leaf or an internal node. 3.2.1. Leaves A leaf u corresponds to a maximal fragment L^{u}=L^{v}_{b}\cdots L^{v}_{b+z-1} , with z\geq 1 , such that rle(L^{u}) contains at most w runs, but including block L^{v}_{b+z} would exceed w runs. The leaf stores: • An array E=rle(alphacomp(L^{u})) . Encoding of the runs We encode the runs in E using a space-efficient layout that supports fast scans. Each run is stored as an integer x , whose first p bits encode the run symbol and whose remaining bits encode the run length, where p depends on the local alphabet of E . The encoding applies to these integers. Our design is inspired by the vbyte-based scheme of Lemire and Boytsov ( 19 ) and enables parallel decompression, making it amenable to SIMD implementations. We represent E as a byte stream C_{1}U_{1}\cdot C_{2}U_{2}\cdots C_{k}U_{k} , where each 8-bit control byte C_{k} specifies the byte lengths of the runs stored in the variable-length stream U_{k} . The number of runs packed in each U_{k} depends on the largest run encoding in the leaf: eight runs if all fit in at most two bytes, four runs if up to four bytes are needed, and two runs otherwise (up to eight bytes). Accordingly, the bits of C_{k} encode the byte length of each run. The number of runs packed in each C_{k}U_{k} block also determines the degree of parallel decompression. As a special case, when all runs fit in a single byte, we store E in plain format. During VLB-tree queries, SIMD instructions are used to accelerate scans of E . 3.2.2. Internal nodes A node u is internal when its fragment L^{u}=L^{v}_{b} contains more than w runs. In this case, we divide L^{u} into f equal-length parts L^{u}_{1},L^{u}_{2},\ldots,L^{u}_{f} of length \ell_{u}=|L^{u}|/f , and process them recursively from left to right using the same merging-and-splitting rule. Some parts become internal nodes (if they have >w runs), while other consecutive parts within the same parent may merge into leaf superblocks (if their concatenation has \leq w runs). The variable-length partition of L^{u} prevents direct index-based access, but we restore efficient navigation with additional routing information. Let L^{u}[i] be a position falling within a fragment L^{e}=L^{u}_{o,o+z-1} of a child e of u , with z\geq 1 . We compute: • The index b=\lceil i/\ell_{u}\rceil for the block L^{u}_{b} where i falls, with b\in[o..o+z-1] . • The index o for L^{u}_{o,o+z-1} . This value maps L^{u}[i] to its position i-(o-1)\ell_{u} within L^{e} . • The child index q for e among the children of u . This information tells us what pointer to follow to visit L^{e} . Accordingly, an internal node u stores: • A bitvector X[1..f] marking which of the f parts begin a child. If f=4 and X=1001 , then L^{u}_{1},L^{u}_{2},L^{u}_{3} defines the first child and L^{u}_{4} the second, so u has f^{\prime}=2 children. • An array P[1..f^{\prime}] containing pointers to the children of u . We compute o=pred_{1}(u.X,b) , q=rank_{1}(u.X,o) , and follow the pointer u.P[q] to reach e . The branching factor f is kept small (e.g. f\leq 64 ) so that pred_{1} and rank_{1} in X[1..f] are implemented with bitwise operations on a single machine word. Figure 2 and Example 3.1 illustrate the VLB-tree construction. Example of the VLB-tree Figure 2. VLB-tree built on the BWT L from Figure 1 . The parameters are \ell=16 , f=2 , and w=2 . In nodes v,u,e , we label the stored node fields (omitted elsewhere for readability). We also omit array X as it is the same in all nodes ( X=11 , no superblocks), and the pointer array P . In the alphabet bitvector A , a 1 indicates that the corresponding parent symbol appears in the node. Subscripts annotate each 1 (and the run-length sequence E ) with the original text symbols. Dashed boxes correspond to Example 3.1 . Example of the VLB-tree Example 3.1. The VLB-tree of Figure 2 . The sequence of L is initially partitioned into \lceil n/\ell\rceil=\lceil 45/16\rceil=3 blocks L_{1},L_{2},L_{3} . The first block rle(L_{1})=(\texttt{T},2)(\texttt{A},1)(\texttt{T},8)(\texttt{\$},1)(\texttt{C},3)(\texttt{G},1) has 6>w runs, so we create a new internal node v . The local alphabet of L_{1} has all the symbols of \Sigma and L_{1} does not have a left context, so the alphabet bitvector is v.A=11111 and the prefix-count array is v.O=00000 . We now build the subtree of v using L^{v}=alphacomp(L_{1}) and block size \ell=16/2=8 . L^{v} has two parts L^{v}_{1},L^{v}_{2} , and their compressed sequences are rle(L^{u}_{1})=(\texttt{T},2)(\texttt{A},1)(\texttt{T},5) (blue dashed boxes) and rle(L^{u}_{2})=(\texttt{T},3)(\texttt{\$},1)(\texttt{C},3)(\texttt{G},1) (red dashed boxes). Both yield internal nodes as they have more than w runs each. Assume that we have already processed L^{v}_{1} , and now we have to create an internal node u for L^{u}=alphacomp(L^{v}_{2}) . The local alphabet of L^{v}_{2} is \Sigma^{u}=\{\$,\texttt{C},\texttt{G},\texttt{T}\} , so the alphabet bitvector becomes u.A=10111 . From the symbols in L^{v}_{2} , only T (compact index 4 ) occurs in the left context L^{v}_{1} (seven times), meaning that the prefix-count array is u.O=0007 . The block size now becomes \ell=8/2=4 and the rest of the tree is computed similarly. 3.2.3. The root as special case The VLB-tree root represents the entire sequence L , and therefore does not store the prefix-count array. However, unlike internal nodes — which have at most f children — the root may have up to \lceil n/\ell\rceil children. Storing the bitvector X[1..\lceil n/\ell\rceil] with fast rank_{1} and select_{1} operations would be costly. Instead, we use an array P[1..\lceil n/\ell\rceil] that encodes both the children’s pointers and collapsed runs of zeros in X . If the (logical) bitvector X has X[b]=1 , then P[b] stores a pointer to child q=rank_{1}(X,b) of the root. If X[b]=0 , then P[b] stores the offset b-pred_{1}(X,b) . The least significant bit of P[b] indicates whether it is a pointer or an offset. To locate the root child covering L[i] , we compute the top-level block b=\lceil i/\ell\rceil , read P[b] , and either follow the pointer directly (if it is a pointer), or follow the pointer stored at P[b-P[b]] (if P[b] is an offset). Although P may be larger than storing X plus rank and predecessor data structure, it keeps navigation cache-friendly. 1 u\leftarrow\text{root of the VLB-tree} 2 b\leftarrow\lceil i/\ell\rceil,o\leftarrow b 3 if P[b] is an offset o\leftarrow b-P[b] 4 5 i\leftarrow i-(o-1)\ell 6 \ell\leftarrow\ell/f 7 u\leftarrow\text{node in }u.P[o] 8 {P}\leftarrow\emptyset 9 10 while u\neq\text{leaf} 11 P\leftarrow P\cup\{u\} 12 b\leftarrow\lceil i/\ell\rceil,o\leftarrow pred_{1}(u.X,b),q\leftarrow rank_{1}(u.X,o) 13 i\leftarrow i-(o-1)\ell 14 \ell\leftarrow\ell/f 15 u\leftarrow\text{node in }u.P[q] 16 17 c\leftarrow\text{symbol of the run }u.E[z]\text{ that contains }i 18 c\leftarrow select_{1}(u.A,c) 19 20 for j\leftarrow|P| to 1 do 21 u\leftarrow P[j] 22 c\leftarrow select_{1}(u.A,c) 23 24 return c 25 Algorithm 1 access(L,i) Practical considerations. The construction of the tree uses the parameters \ell , f , and w . We assume \ell>w and that both \ell and w are powers of f ; that is, \ell=f^{x} and w=f^{y} for some integers x and y . All nodes are stored in a contiguous memory region in depth-first (DFS) order. Each node’s encoding is byte-aligned, so the pointers in the array P are byte offsets into this memory region. 3.3. Accessing positions of the BWT For any position i , define path(i)=u_{1},u_{2},\ldots u_{l} as the list of nodes in the VLB-tree visited to locate L[i] , where u_{1} is the root and u_{l} is a leaf. The operation access(L,i) consists of three phases: a top-down descent to identify the leaf containing position L[i] , a local scan of the leaf to find the compacted symbol, and a bottom-up ascent to recover the original symbol in \Sigma . The descent follows the navigation mechanism described in Sections 3.2.2 and 3.2.3 . Starting from the root, we repeatedly use the routing information stored at each internal node to select the child fragment containing the current position and update i to its local offset within that fragment. The descent terminates at a leaf u_{l} such that L[i]\in L^{u_{l}} . When the descent halts at the leaf u_{l} , we scan u_{l}.E to find the leftmost run u_{l}.E[z]=(c,l) whose cumulative length reaches i . We then ascend along u_{l},u_{l-1},\ldots,u_{2} updating the compacted symbol c at each level to the corresponding parent symbol c=select_{1}(u_{j}.A,c) . This process yields the original L[i] in \Sigma . Algorithm 1 shows the process in more detail. Theorem 3.2. Let \mathcal{T} be a VLB-tree built on top of the BWT L of S with parameters f,w , and \ell . Accessing L[i] in \mathcal{T} takes O(\log_{f}(\ell/w)+w) time. Proof. The total time is the height of \mathcal{T} plus the time spent scanning a leaf. During the construction of \mathcal{T} , blocks of size \ell are repeatedly divided by a factor f until the resulting fragments have at most w runs. We choose \ell=f^{x} and w=f^{y} with x>y . A node at depth h encodes a fragment of length \ell/f^{h-1} . These fragments range from size \ell (children of the root) down to w (where the subdivision stops). Thus the maximum depth is \log_{f}\ell-\log_{f}w=\log_{f}(\ell/w) nodes. Each leaf has \leq w runs, which gives the additive term w . ∎ The worst case arises when roughly \ell BWT runs of length 1 occur consecutively — an uncommon situation in highly repetitive data. If i falls inside a leaf superblock attached directly to the root — a common case in repetitive inputs — , then path(i) has two nodes, so the time drops to O(w) . Choosing a small threshold w (e.g., \approx 64 ) makes the final linear scan over E effectively constant using SIMD. The number of cache misses along path(i) is bounded by \log_{f}(\ell/w) (assuming each node fits in cache), and deeper nodes exhibit better locality. A small w also keeps E cache-resident, further reducing misses. 3.4. Adding support for rank and successor The compressed suffix array requires rank and successor queries to support pattern matching. However, implementing these operations in the VLB-tree is challenging because each node only stores information about its local alphabet, whereas the queries receive as input an arbitrary symbol c and a position i . We augment the VLB-tree to address this issue. The operations rank_{c}(L,i) and succ_{c}(L,i) return different information, but they can be implemented using the same traversal strategy in the VLB-tree. We begin by following path(i)=u_{1},u_{2},\ldots,u_{l} and stop at the first node whose local alphabet does not contain c . At that level, the traversal diverges to a close node (typically a sibling) that leads to the answer. In the case of the rank query, this corresponds to the one leading to the closest occurrence of c to the left of i ( pred_{c}(L,i) ), while for the successor query, it leads to the closest occurrence of c to the right of i . Our current encoding does not allow us to infer the diverging nodes efficiently, so we will augment the internal nodes with additional routing information to visit these paths. Consider an internal node u corresponding to the fragment L^{u} . Its compacted alphabet is \Sigma^{u}=[1..\sigma^{u}] , and the partition of L^{u} induces f^{u} children for u . We add: • A bitvector N[1..f^{u}\sigma^{u}] storing the concatenation of \sigma^{u} bitvectors N_{1}[1..f^{u}]{\cdot}N_{2}[1..f^{u}]{\cdots}N_{\sigma^{u}}[1..f^{u}] . For a symbol c\in\Sigma^{u} and the child index q\in[1..f^{u}] , N_{c}[q]=1 iff the q -th child of u contains c\in\Sigma^{u} . The bitvector N indicates whether the symbol c appears in each child of u , and using succ_{1} and pred_{1} queries on N_{c} redirects the traversal to the nearest left/right sibling containing c . When N_{c} fits a machine word, these queries run in O(1) time via word operations. The additional f^{u}\sigma^{u} bits per internal node impose only a small overhead because f^{u}\leq f and the local alphabet size \sigma^{u} is small in repetitive texts and typically decreases at deeper tree levels. The root also requires such routing information. However, the size of its corresponding bitvector can reach \sigma(n/\ell) bits, too large to fit a machine word, thus requiring auxiliary data structures to support succ_{1} and pred_{1} . These extra structures would likely reside far from the root in memory, causing cache misses — similarly to the issue with bitvector X (Section 3.1 ). To avoid this overhead, we reorganize the routing information of the root by distributing it across its children. For each root child u , we create: • An array Z[1..\sigma] that stores in Z[c] the distance between u and its closest right-hand sibling y such that c occurs in L^{y} . Thus, if u and y are the children q and q^{\prime} of the root (respectively), then u.Z[c]=q^{\prime}-q . We use Z only when redirection is required from the second node (root child) in the traversal, ensuring that the necessary routing information is local and avoiding cache misses. The aggregate space of all Z arrays may exceed that of the root’s bitvector N and its auxiliary data structures, but we adopt this design to preserve cache efficiency. In Section 5 , we describe a technique to reduce the space of Z with no penalty in query time. u_{2}\leftarrow\text{ root child in }path(i) 1 if u_{2}.A[c]=0 2 y_{1}\leftarrow\text{node indicated by }u_{2}.Z[c] 3 return y_{1}.O[rank_{1}(y_{1}.A,c)] 4 r\leftarrow 0 5 6 for u_{j}\in u_{2},u_{3},\ldots,u_{l}\subset path(i) do 7 c\leftarrow rank_{1}(u_{j}.A,c) 8 r\leftarrow r+u_{j}.O[c] 9 q\leftarrow\text{ child index of }u_{j+1}\text{ in }u_{j} 10 if u_{j}.N_{c}[q]=0 11 y_{1}\leftarrow\text{nearest left sibling of }u_{j+1}\text{ with }c 12 if y_{1}=\textsc{NULL}\text{{ then}} return r 13 for y\in y_{1},y_{2},\ldots,y_{l} do 14 c\leftarrow rank_{1}(y.A,c) 15 r\leftarrow r+y.O[c] 16 return r+\text{cumulative run lengths of }c\text{ in }y_{l}.E 17 r^{\prime}\leftarrow\text{cum. run lengths of }c\text{ in }u_{l}.E\text{ up to local }i 18 return r+r^{\prime} 19 Algorithm 2 rank_{c}(L,i) 1 u_{2}\leftarrow\text{ root child in }path(i) 2 3 if u_{2}.A[c]=0 4 y_{1}\leftarrow\text{node indicated by }u_{2}.Z[c] 5 for y\in y_{1},y_{2},\ldots,y_{l} do 6 c\leftarrow rank_{1}(y.A,c) 7 return \text{global idx of the first }c\text{ in }y_{l}.E[z] 8 c_{k}\leftarrow c,p_{k}\leftarrow u_{2}.Z[c]\text{ } \triangleright candidate for divergence 9 for u_{j}\in u_{2},u_{3},\ldots,u_{l}\subset path(i) do 10 11 q\leftarrow\text{ child index of }u_{j+1}\text{ in }u_{j} 12 q^{\prime}\leftarrow succ_{1}(u_{j}.N_{c},q+1)\text{ } \triangleright next sib. of u_{j} with c if q^{\prime}\neq\textsc{NULL} then c_{k}\leftarrow c , p_{k}\leftarrow u_{j}.P[q^{\prime}] 13 14 if u_{j}.N_{c}[q]=0 15 c\leftarrow c_{k} , y_{1}\leftarrow\text{ node indicated by }p_{k} 16 execute Lines 3 - 3 17 c\leftarrow rank_{1}(u_{j}.A,c) 18 19 \text{find the first run }u_{l}.E[z]\text{ for }c\text{ after local }i\text{ in }u_{l} 20 21 if u_{l}.E[z] is found then return global idx its first c 22 23 c\leftarrow c_{k} , y\leftarrow\text{node indicated by }p_{k} 24 execute Lines 3 - 3 25 Algorithm 3 succ_{c}(L,i) Pseudocode for $rank$ and $succ$ queries 3.4.1. Rank algorithm We begin the algorithm for rank_{c}(L,i) by descending path(i)=u_{1},u_{2},\ldots,u_{l} as described in Section 3.3 . Throughout the process, the variable c is updated to denote the compacted symbol corresponding to the current node. Root-child special case If u_{2}.A[c]=0 , the fragment L^{u_{2}} does not contain c , so we visit the right-hand sibling y_{1} indicated by u_{2}.Z[c] and report the prefix count from y_{1}.O[c] . Node y_{1} lies on path(succ_{c}(L,i)) , not on path(pred_{c}(L,i)) , which we previously stated would be used for rank_{c} . However, the answer in y_{1}.O is still correct because it considers the occurrences of c preceding L^{u_{2}} . This is exceptional because u_{2}.Z does not provide information for redirecting to a left-hand sibling. General internal node This case assumes u_{2}.A[c]=1 . For an internal node u_{j}\neq u_{2} with child index q for u_{j+1} , if u_{j}.N_{c}[q]=0 , then u_{j+1} does not contain c . We therefore compute y_{1}=pred_{1}(u_{j}.N_{c},q-1) , the closest left-hand sibling of u_{j+1} that contains c . If there is no y_{1} , we return the cumulative prefix count for c collected up to u_{j} . If y_{1} exists, we descend the rightmost branch y_{1},y_{2},\ldots,y_{l} that contains c , computing each successive child as y_{j+1}=pred_{1}(y_{j}.N_{c},f^{y_{j}}) , where f^{y_{j}} is the number of children for y_{j} . Upon reaching the leaf y_{l} , we scan its entire sequence y_{l}.E , count all occurrences of c , and add them to the cumulative rank for c along the nodes u_{2},\ldots,u_{j} and the redirected branch y_{1},\ldots y_{l} . The full leaf scan is necessary since the subtree of y_{1} lies entirely before position i , so all occurrences in y_{l} contribute to rank. The final rank value is the answer for rank_{c}(L,i) . Algorithm 2 illustrates the procedure. 3.4.2. Successor algorithm As mentioned above, succ_{c}(L,i) operates almost the same way as rank_{c}(L,i) . The most notable change is the node we search after diverging. The query returns a null value if no valid successor for c exists in L[i..n] . We descend path(i) , compacting c accordingly, until we reach the first node u_{j} where u_{j+1} does not contain c ( u_{j}.N_{c}[q]=0 ). From there, we locate the deepest ancestor u_{k}\in path(i) , with k\leq j , such that L^{u_{k}} has an occurrence of c to the right of the local i . Finding the successor node Figure 3. Finding the successor node containing c . Finding the successor node Once we locate u_{k} , we move to the closest right-hand sibling y_{1} of u_{k+1} , and continue descending the leftmost branch y_{1},y_{2},\ldots,y_{l} that contains c . The initial compacted symbol is c_{k} and each subsequent node y_{j+1} is the leftmost child of y_{j} that contains c . Upon reaching y_{l} , the algorithm scans y_{l}.E until it finds the first run y_{l}.E[z] for c , and reports the index in L for the first c in y_{l}.E[z] (i.e., its global index). Figure 3 illustrates the divergence mechanism. If no stopping node u_{j} is found and the descent of path(i) reaches its leaf u_{l} , the algorithm scans u_{l}.E to locate the first run u_{l}.E[z] of c such that the cumulative run length is equal to or greater than the local i . If such a run exists, it returns its global index in L . If the run does not exist, c does not occur in suffix L^{u_{l}}[i..] , so the algorithm follows the leftmost branch of y_{1} as described before. Finding the branching node To avoid backtracking path(i) to find u_{k} , during descent, we maintain, for each internal node u_{j}\in path(i) with j\geq 2 , a pointer p_{k} to a candidate redirection node y_{1} together with the compacted value c_{k} of c in alphacomp(L^{u_{k}}) . For a root child u_{2} , p_{k} is u_{2}.Z[c] and c_{k}=c (or null if no valid successor exists). For a general internal node u_{j}\neq u_{2} where the child index for u_{j+1} is q , p_{k} points to the next right-hand sibling succ_{1}(u_{j}.N_{c},q+1) containing c and c_{k} is the compacted c in u_{j} . If no valid pointer p_{k} is found (i.e., u_{j+1} does not have a right-hand sibling for c ), the pair (p_{k},c_{k}) is inherited from u_{j-1} . Once the stopping node u_{j} is found, the algorithm moves to the node y_{1} indicated by p_{k} , updates c=c_{k} , and starts the descent of the leftmost branch for c in y_{1} . On the other hand, if p_{k} is a null pointer, succ_{c}(L,i) returns a null value. Algorithm 3 shows the successor mechanism in more detail. A modified successor query The operation backwardsearch(P)=(sp_{1},ep_{1},SA[sp_{1}]) internally uses a variant of succ_{c}(L,i)=h_{\rho} that returns the index \rho of the run L[h_{\rho}..t_{\rho}] where h_{\rho} lies. This index indicates the suffix sample SA_{h}[\rho] from which the toehold SA[sp_{1}] is derived (Equation 2 ). Our VLB-tree design will distribute SA_{h} in the leaves to improve cache efficiency (Section 4 ) so an index \rho does not necessarily tell where SA_{h}[\rho] is stored. We define a more convenient query: • msucc_{c}(L,i) : Let succ_{c}(L,i)=i^{\prime} be a successor index for c and let L[h_{\rho}..t_{\rho}] be the run where i^{\prime} falls in L . The memory successor query msucc_{c}(L,i) returns the byte offset within the VLB-tree where SA_{h}[\rho] resides. Theoretical cost We note that the theoretical cost of the rank and successor algorithms remains the same as that of access(i) (Section 3.3 ), and they incur O(\log_{f}(\ell/w)) additional cache misses if they have to diverge the traversal. 4. Counting with toehold The current VLB-tree encoding (Section 3.4 ) already supports the query rank_{c}(L,i) , which is sufficient to compute the backward-search intervals (sp_{l},ep_{l}) using Equation 1 . The next step is to use Equation 2 to obtain the toehold SA_{h}[sp_{1}] . We need: • To determine the step g and its position sp_{g} . • To retrieve SA_{h}[\rho] given g and sp_{g} . We describe how to support both operations in the VLB-tree. 4.1. The step for the toehold Cobas et al. ( 6 ) present a simple method to obtain g and sp_{g} : initially, set g=m+1 and sp_{g}=1 , and run the backward search. Whenever a step (sp_{l},ep_{l}) satisfies L[sp_{l}]\neq P[l-1] , update g=l and sp_{g}=sp_{l} . The final values are obtained once (sp_{1},ep_{1}) is reached. The challenge is to test L[sp_{l}]\neq P[l-1] in a cache-friendly manner because Equation 1 does not necessarily visit the area for L[sp_{l}] . We define a new query \mathit{headrank}_{c}(L,i)=(o,b) in the VLB-tree, where o is the number of occurrences of c in L[1..i] and b is a bit set to 1 if L[i]=c . This operation behaves like \mathit{rank}_{c}(L,i) (Section 3.4.1 ), with one additional check: • If path(i) diverges from path(pred_{c}(L,i)) , then L[i]\neq c and we set b=0 . • Otherwise, both paths coincide. Let v be the leaf reached and let i^{\prime} be the local position of i in L^{v} . We set b=1 if L^{v}[i^{\prime}] matches c , and b=0 otherwise. A subtle issue arises because Equation 1 infers sp_{l-1}=C[P[l-1]]+rank_{P[l-1]}(L,sp_{l}-1)+1 , whereas we now perform rank at position sp_{l} . Since L[sp_{l}-1] and L[sp_{l}] may lie in different fragments of the VLB-tree, we adjust the computation as follows. We first run headrank_{P[l-1]}(L,sp_{l})=(o,b) . If b=1 , we decrement o by one; otherwise, o is left unchanged. The value sp_{l-1}=C[P[l-1]]+o+1 is therefore identical to the original formulation. 4.2. Suffix array samples After computing g and sp_{g} , we must retrieve the index \rho such that succ_{P[g-1]}(L,sp_{g})=h_{\rho} . The VLB-tree query succ_{P[l-1]}(L,sp_{g}) (Section 3.4.2 ) returns the index h_{\rho} , but this alone does not identify where SA_{h}[\rho] is stored. We address this by augmenting the leaves of the VLB-tree with suffix array samples. For a leaf v whose sequence v.E contains m^{\prime} runs, we store an array W[1..m^{\prime}] such that W[z] equals the value of SA_{h} associated with the z -th run of v.E (from left to right). With this structure in place, retrieving SA_{h}[\rho] is straightforward. Given g and sp_{g} , we call \mathit{msucc}_{P[g-1]}(L,sp_{g}) (Section 3.4 ) to obtain the leaf v containing the BWT position h_{\rho} . Let v.E[z] be the run where h_{\rho} lies; the desired suffix array sample is v.W[z]=SA_{h}[\rho] . A key advantage of this design is that msucc_{P[g-1]}(L,sp_{g}) and the subsequent retrieval of SA_{h}[w] are performed in the same memory area (the leaf v ), ensuring excellent locality. In contrast, traditional r -index implementations store SA_{h} and L in different memory locations. Handling run splitting Because the tree construction may split BWT runs across leaves, the first and last elements of v.E may be partial . In particular, v.E[1] is partial if the symbol preceding L^{v} in L is the same as the symbol of v.E[1] . Each leaf stores a flag indicating whether this situation occurs. When v.E[1] is partial, its corresponding BWT area is a proper suffix L[t_{\rho}-q+1..t_{\rho}] of a run L[h_{\rho}..t_{\rho}] . Since the values of SA_{h} are associated with run heads, and v.E[1] does not include L[h_{\rho}] , the array v.W does not have a value for v.E[1] . In this case, each entry v.W[z] corresponds to v.E[z+1] . This situation does not affect the retrieval of SA_{h}[\rho] . The positions sp_{g} and h_{\rho} always belong to different BWT runs. Consequently, if h_{\rho} lies in the run v.E[z] of some leaf v , then v.E[z] cannot be partial and v.W is guaranteed to have a sample for h_{\rho} . 5. Reducing the space usage of the VLB-tree A drawback of the VLB-tree that we have not yet addressed is the space overhead introduced by the satellite data stored at the root level. Each child u_{2} of the root stores an array Z , which allows the traversal of path(i)=u_{1},u_{2},\ldots,u_{l} to jump to an appropriate right-hand sibling whenever a divergence is required. This information is used when answering both rank and successor queries (Section 3.4 ). Since the root may have up to n/\ell children and each Z array has \sigma entries, the space overhead can reach \sigma(n/\ell) bits in the worst case. In this section, we show how to reduce this cost by sampling each array Z while still ensuring that the operation backwardsearch(P[1..m]) works correctly whenever P occurs in S . When P is not in S , operations rank , headrank , and msucc may fail, returning zero or null when they should return a non-zero or non-null value. This behavior is acceptable, since this function naturally returns an empty range ( sp_{1}>ep_{1} ) when P does not appear in S . Intuition Each array Z does not need to store entries for all symbols in \Sigma . Consider the suffix array range SA[sp_{l}..ep_{l}] representing the suffixes of S prefixed by P[l..m] . The next backward-search step computes rank_{P[l-1]}(L,sp_{l}) (or headrank in our case) to obtain sp_{l-1} . However, if the pattern P[l-1..m] does not exist in S , there is no need to store an entry for P[l-1] in the array Z of the root child u_{2} containing position sp_{l} . We now formalise this idea. Let \mathcal{S}\subset\{(s,e)\in[n]\times[n]\mid s\leq e\} be the set of valid ranges 2 2 2 For readers familiar with suffix trees, \mathcal{S} contains the ranges associated with the nodes of the suffix tree of S . in SA that backwardsearch(P) may visit when computing (sp_{1},ep_{1})\in\mathcal{S} for any pattern P in S . For a pair (p,q) with 1\leq p\leq q\leq n , define \begin{array}[]{l}\mathcal{L}(p,q)=\{(s,e)\in\mathcal{S}\mid s\leq p\leq e\leq q\}\text{ and }\\ \mathcal{R}(p,q)=\{(s,e)\in\mathcal{S}\mid p\leq s\leq q\leq e\},\end{array} representing the sets of suffix array ranges overlapping the left and right ends of (p,q) , respectively. The leftmost and rightmost overlaps of (p,q) are \begin{array}[]{l}lmo(p,q)=\arg\min_{(s,e)\in\mathcal{L}(p,q)}s\text{ and }\\ rmo(p,q)=\arg\max_{(s,e)\in\mathcal{R}(p,q)}e,\end{array} respectively, breaking ties for lmo(p,q) by choosing the pair with the largest e , and for rmo(p,q) , the pair with the smallest s . For a BWT substring L[p..q] and its overlapping suffix array ranges (a,b)=lmo(p,q) and (y,z)=rmo(p,q) , let \Sigma^{(a,p-1)}\subseteq\Sigma and \Sigma^{(q+1,z)}\subseteq\Sigma be the alphabets of L[a..p-1] and L[q+1..z] , respectively. Lemma 5.1. Let u_{2} be a root child in the VLB-tree with fragment L^{u_{2}}=L[p..q]\in\Sigma^{*} . The array u_{2}.Z can be sampled so that it stores entries only for symbols in \Sigma^{(a,p-1)}\cup\Sigma^{(q+1,z)} , and backwardsearch(P) still returns the correct result whenever P occurs in S . Proof. Let l\in\{m+1,m,\ldots,2\} be a step in the operation backwardsearch(P) , and let SA[sp_{l}..ep_{l}] be the range of suffixes in S prefixed by P[l..m] . We say that the triple (sp_{l},ep_{l},P[l-1]) is valid if P[l-1] occurs in L[sp_{l}..ep_{l}] , which is equivalent to P[l-1..m] occurring in S . To prove the lemma, it suffices to show that whenever a rank or successor operation in backwardsearch(P) process a valid index i\in[p..q] and a valid symbol c , the sampled array u_{2}.Z contains an entry for c . Indeed, a valid triple (sp_{l},ep_{l},P[l-1]) produces a range (sp_{l-1},ep_{l-1}) for a suffix P[l-1..m] that exists in S . We focus on rank_{c}(L,i) and headrank_{c}(L,i) ; the argument for the successor queries is analogous. For an index i\in[p,q] , the query rank_{c}(L,i) traverses path(i)=u_{1},u_{2},\ldots,u_{v} and may diverge if path(pred_{c}(L,i))\neq path(i) . Furthermore, when L^{u_{2}}=L[p..q] does not have occurrences of c , the algorithm falls into a special root-child case and redirects the traversal from u_{2} to the right-hand sibling y_{1} containing L[succ_{c}(L,i)] . The pointer to y_{1} is stored in u_{2}.Z[c] (Section 3.4.1 ). Two cases must be considered when sampling u_{2}.Z . Case one: i=sp_{l}\text{ and }p\leq sp_{l}\leq q. In the VLB-tree, backwardsearch(P) uses headrank_{P[l-1]}(L,sp_{l}) to compute sp_{l-1} . It may happen that P[l-1] does not occur in L[p..q] but does occur in L[q+1..ep_{l}] , forcing the use of u_{2}.Z[P[l-1]] . Since (sp_{l},ep_{l},P[l-1]) is valid, the entry u_{2}.Z[P[l-1]] must exist in the sampling of u_{2}.Z , otherwise backwardsearch(P) fails with a pattern that exists in S . The sampling of P[l-1]\in\Sigma^{(q+1,z)} is guaranteed because (sp_{l},ep_{l})\in\mathcal{R} overlaps the right end of (p,q) , and (y,z)=rmo(p,q) contains all elements of \mathcal{R} . Case two: i=ep_{l}\text{ and }p\leq ep_{l}\leq q In this case, backwardsearch(P) uses rank_{P[l-1]}(L,ep_{l}) to compute ep_{l-1} . The symbol P[l-1] may occur in L[s_{l}..p-1] but not in L[p..q] , again forcing the use of u_{2}.Z[P[l-1]] . This time, the existence of P[l-1] in the sample of u_{2}.Z is guaranteed because (sp_{l},ep_{l})\in\mathcal{L} overlaps the left end of L[p..q] , and (a,b)=lmo(p,q) contains all elements of \mathcal{L} . In conclusion, a sample of u_{2}.Z that stores information for \Sigma^{(a,b)}\cup\Sigma^{(y,z)} is sufficient to ensure that backwardsearch(P) is answered correctly whenever P exists in S . Figure 4 and Example 5.2 illustrates both cases and the corresponding overlaps within L[p..q] . ∎ Sampling strategy Figure 4. Sampling of Z arrays. The parentheses are the ranges SA[sp_{l}..ep_{l}] that backwardsearch(P) can visit for patterns of length \leq 4 . The gray block L[p,q]=L[17..32] marks the fragment of a root child (the one in the middle in Figure 2 ). The gray parentheses to the left highlight the longest left overlap (a,b)=lmo(p,q) , and the gray parentheses to the right highlight the longest right overlap (y,z)=rmo(p,q) . The alphabet \Sigma^{(a,p-1)} is \{\texttt{\$},\texttt{C},\texttt{G},\texttt{T}\} and the alphabet \Sigma^{(q+1,z)} is \emptyset . The Z array for the root child encoding L[p..q] thus stores pointers for \{\texttt{\$},\texttt{C},\texttt{G},\texttt{T}\} . Sampling strategy Example 5.2. Performing rank with the sampling of Figure 4 . Consider rank_{c}(L,ep_{l}) for c\in\{\texttt{\$},\texttt{C},\texttt{T}\} , where ep_{l}=b . Since c does not occur in L[p..b] (and p\leq b\leq q ), the VLB-tree uses the Z array of the root child encoding L[p..q] . By Lemma 5.1 , c has a pointer in Z , so the query returns a valid answer. Note that rank_{\texttt{A}}(L,b) returns 0 although the correct value is 1 (due to L[3]=\texttt{A} ). This inconsistency is harmless because A does not occur in L[sp_{l}=a..ep_{l}=b] , so the corresponding backward-search step correctly yields an empty range ( sp_{l-1}>ep_{l-1} ). 6. Locating from toehold In this section, we introduce a new representation for the function \phi^{-1} used by locate(P)=SA[sp_{1}..ep_{1}] to decode the suffix array values in SA[sp_{1}+1..ep_{1}] from the toehold SA[sp_{1}] (Section 2.3.1 ). This new encoding balances speed and space using adaptive techniques based on the VLB-tree. The classical data structure for \phi^{-1} uses a bitvector B[1..n] marking text positions that correspond to run tails in the BWT, together with an array D[1..r] storing suffix array differences at run boundaries. The operation \phi^{-1}(SA[j])=SA[j+1] is then solved using Equation 3 . This formulation reveals two opportunities for improvement: • The distribution of 1 s in B is typically skewed, so adaptive structures improve space usage. • Interleaving B,D improves spatial locality when answering \phi^{-1}(SA[j]) . We combine these observations by introducing a VLB-tree for \phi^{-1} , denoted \mathcal{T}_{\phi} . 6.1. The VLB-tree for locating The tree \mathcal{T}_{\phi} is built over a logical sequence Q[1..n] that interleaves the information of B and D . Let b_{1},b_{2},\ldots,b_{r} be the positions in B such that each B[b_{a}]=1 , and let d_{a}=b_{a+1}-b_{a} denote the distance between consecutive 1 s (with d_{r}=n+1-b_{r} ). We define the run-length encoding of Q as rle(Q)=(D[1],d_{1})(D[2],d_{2}),\ldots,(D[r],d_{r}), where each pair (D[a],d_{a}) forms a run, analogous to those in the BWT. The entry in D[a] is the run symbol and d_{a} the run length. We construct \mathcal{T}_{\phi} from Q following the same principles as in Section 3.1 , but storing only the information required to answer the operation access(Q,SA[j]) . Specifically, each internal node u stores only the bitvector u.X marking the superblocks and the array u.P of the child pointers, while each leaf only stores the run-length sequence E corresponding to a substring of Q . Supporting access(Q,SA[j])=D[rank_{1}(B,SA[j])] is sufficient to answer \phi^{-1}(SA[j])=SA[j]+access(Q,SA[j]). In the description of \phi^{-1}(SA[j]) in Section 2.3.1 , positions SA[j] that fall within B[b_{a}..b_{a+1}-1] access D[a] . This range is represented in \mathcal{T}_{\phi} by the run (D[a],d_{a}) , thereby improving spatial locality compared to traditional r -index implementations. Handling run splitting The construction of \mathcal{T}_{\phi} may divide a run (D[a],d_{a}) into several parts (D[a],d_{a.1}),(D[a],d_{a.2}),\ldots depending on the block size \ell and the run length d_{a} . However, this partition does not affect the output of \phi^{-1} because all positions B[b_{a.2}],B[b_{a.3}],\ldots are associated with D[a] . This property follows directly the definition of the BWT (see Section 2.3.1 ). Figure 5 illustrates the construction of \mathcal{T}_{\phi} . 6.1.1. Complexity and adaptivity The traversal of path(SA[j]) in \mathcal{T}_{\phi} allows us to find the run (D[a],d_{a}) containing position SA[j] , which we then use to answer access(Q,SA[j]) . This operation takes O(\log_{f}(\ell/w)+w) time, \ell , w , and f being the VLB-tree parameters. Areas of Q containing long runs (respectively, sparse regions of B ) generate leaves in \mathcal{T}_{\phi} that are close to the root, resulting in fewer cache misses and short leaf scans. Conversely, regions with many short runs (equivalently, dense regions of B ) are placed deeper in \mathcal{T}_{\phi} , increasing space usage, but matching the inherently higher cost of navigating many runs. This adaptive behavior mirrors that of the VLB-tree used for the BWT and achieves a balanced trade-off between space and query performance. 7. Fast subsampled index The VLB-trees for the BWT and for \phi^{-1} together form a compressed suffix array supporting the queries count(P) and locate(P) . However, storing the 2r suffix array samples required by these structures can be expensive for repetitive texts with many small variations. The sr -index solves the space issue, but existing implementations suffer from poor cache locality because queries must traverse multiple disconnected structures (Section 2.3.2 ). In this section, we show how to encode both the sr -index and its fast variant (Section 2.3.3 ) within the VLB-tree framework, improving locality while preserving their space. 7.1. Modifications on the VLB-tree of the BWT Let \mathcal{T}_{L} denote the VLB-tree of the BWT. Each leaf v in \mathcal{T}_{L} stores a run-length encoded fragment v.E[1..m^{\prime}] of L and an array v.W[1..m^{\prime}] with the suffix array samples in SA_{h} associated with v.E (Section 4.2 ). After subsampling, v.W shrinks if some of the runs in v.E do not retain a sample. To represent this situation, we augment each leaf with a bitvector v.R[1..m^{\prime}] , where v.R[z]=0 indicates that v.E[z] retains its sample and v.R[z]=1 otherwise. For a run v.E[z] with v.R[z]=0 , its sample is stored at v.W[rank_{0}(v.R,z)] . Since m^{\prime}\leq m and v.R fits in a machine word, rank_{0} can be computed in constant time using bitwise operations. Backward search The only query in \mathcal{T}_{L} that requires a modification is backwardsearch(P)=(sp_{1},ep_{1},SA[sp_{1}]) . The run \rho in L used to derive the toehold SA_{h}[sp_{1}] (Equations 2 ) may not retain a subsample, in which case we need to recover it (Equation 4 ). We operate as follows: after completing the backward search and obtaining (g,sp_{g}) , we use msucc_{P[g-1]}(L,sp_{g}) to access the VLB-tree leaf v encoding the run L[h_{\rho}..t_{\rho}] associated with SA_{h}[\rho] . Let v.E[z] be run for L[h_{\rho}..t_{\rho}] . If v.R[z]=0 , we return v.W[rank_{0}(v.R^{\prime},z)]=SA_{h}[\rho] , otherwise we recover SA_{h}[\rho] via LF starting from h_{\rho} , as in Equation 4 . 7.2. Modifications on the VLB-tree of locating In the standard sr -index, the query \phi^{-1}(SA[j]) performs up to s LF steps to check if SA[j] falls in valid area. A failed test indicates invalid area but returns SA[j+1] altogether, whereas a successful test does not give the answer but indicates that Equation 3 with subsampled B and D returns the correct SA[j+1] (Section 2.3.2 ). This functionality does not require any modification to the VLB-tree \mathcal{T}_{\phi} . We can build it directly over the logical sequence Q derived from the subsampled B and D . On the other hand, the fast variant of the sr -index marks the invalid areas to save computations (Section 2.3.3 ) and therefore we must incorporate this information into the VLB-tree \mathcal{T}_{\phi} . A run (D[a],d_{a}) in Q represents a range B[b_{a}..b_{a-1}-1] that is fully or partially valid. The run (D[a],d_{a}) of a partially valid range can be split into two halves d_{a,l},d_{a,r} . Let b_{a}