More RLBWT Tricks

arXiv:2609.40299 · cs.DS · Submitted 2026-09-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "More RLBWT Tricks".

Jane: Here's the gist of the paper. FM-indexes and compressed suffix arrays are often treated as interchangeable, but they behave differently as the alphabet grows The hybrid is correct and simple to implement On synthetic repetitive data it has the following properties • Its query time barely depends on the alphabet size, because the Huffman-shaped wavelet tree over the encoding has depth about 2 whatever the alphabet • At intermediate alphabet sizes (10 to 10,000) with 1% noise, it is the fastest of the indexes we tried, by 1.1 to 1.8 times (the smallest margin is within measurement noise) • It is never the smallest The main open question is whether this hybrid means anything on real data, such as parses and minimizer digests Hybrid Encoding Mechanism The encoding of a character is defined by the rank of its frequency among the characters that follow the previous character in the text The encoded text E is then mostly small numbers (on our test data, mostly 1s) A pattern P

0: is encoded using the text’s rankings, and the catch is that the encoding of P only makes sense given P’s first character The encoding of T can be decoded from left to right given T

0: and the lists Counting and Locating The lemma proves that counting is exact by stating that a pattern occurs if and only if T

p: = P

0: and E

p + 1 to p + m − 1: = Q

1 to m − 1: Locating with suffix-array samples works unchanged, where the rows we need to locate are the positions k of P

0: in ΨE The result is an FM-index for all but one step of the search, and a CSA for the last one Performance Analysis The query time barely depends on the alphabet size because the Huffman-shaped wavelet tree over the encoding has depth about 2 whatever the alphabet At intermediate alphabet sizes (10 to 10,000) with 1% noise, it is the fastest of the indexes we tried, by 1.1 to 1.8 times (the smallest margin is within measurement noise) The compact version of the hybrid is dominated because its encoding and ΨE together have more runs than the original Burrows–Wheeler transform Space and Real Data Implications The hybrid’s size is dominated by the runs of BWT(E) and especially ΨE On real data, the size of E can be up to 2z(T), but we see no reason for r(E) ≤ r(T) in general The extra runs are the main cost of the hybrid when compared to other indexes Future Directions The paper suggests a combination: a move structure on BWT(E), followed by one CSA-style step on ΨE The hybrid suggests that move structures are best suited to small alphabets, whereas the standard fixes store pointers or counts for every character which costs space proportional to σ per sample Open questions include implementing and evaluating locating, including the ϕ-based approach of Section 3.4 and comparing against the relabeled-block FM-index baseline The hybrid may be useful for the parse level of a two-level index

3: The idea of the hybrid is due to the author References

1: O.

Tom: Y.

Jane: Ahmed, M.

Tom: Rossi, T.

Paper summary: Tom: Welcome back to the show, folks, we're diving into a paper titled "More RLBWT Tricks" today, which looks at combining FM-indexes and compressed suffix arrays in a new way. It sounds like they’ve developed a hybrid structure that works well with certain types of data.

Jane: Exactly. The main idea here is that they are creating this hybrid structure to be really practical for real-world use, even though the authors admit it isn't just some magic solution Lu They’re focusing on making this combination correct and simple to implement, especially when you look at how the encoding works over a small alphabet.

Meng: But my immediate concern is the size. The paper shows that when you put everything together, the resulting index can be quite large compared to other existing methods Lalam I'm worried about what happens if we try to deploy this at scale.

Lalam: Well, I can tell you that they found this specific combination is fast—it’s actually faster than some of the indexes we were testing at intermediate alphabet sizes with one percent noise Tom So it’s not just theoretical; they’re seeing concrete performance gains when they test it on synthetic repetitive data, specifically in that ten to ten thousand alphabet range with one percent noise.

Jane: That makes sense for synthetic data, but the authors are pointing out that while this hybrid is fast in those specific conditions, we still don't know if it translates well when you look at things like actual parses or minimizer digests Lu So they’re leaving that big question hanging about real data.

Tom: It’s a really interesting point because it suggests that move structures might be better for smaller alphabets, but it also reminds us that the standard fixes still have their place for certain things Jane If we look at the future work they suggest, it points toward combining move structures on the bwt E with one CSA step on psi E for even better results down the line.

Lu: That sounds like a solid direction because it acknowledges the strengths of both parts while trying to fix their weaknesses Meng From an engineering standpoint, I’m still thinking about how much space this extra structure eats up compared to something simpler like Elias–Fano run-length CSA Tom It’s a trade-off, right? Faster query time now versus potentially bigger storage later on for real text Jane

Lalam: The paper does show the space analysis, and it points out that the compact hybrid is one point seven to three point nine times larger than a compressed run-length CSA of the text Tom And when we look at those runs, BWT E has up to one point two five times as many runs as BWT T with zero point one percent noise Jane

Meng: I see that size increase is something we have to account for before we even think about deployment on real traffic Lu What about the actual query time? Does it keep pace?

Tom: The paper says that the query time barely depends on the alphabet size because the Huffman-shaped wavelet tree over the encoding has a depth about two whatever the alphabet Jane At intermediate alphabet sizes with one percent noise, it’s faster than some indexes we tried by a factor of one point one to one point eight times Lu

Jane: So they are claiming speed improvements when things are in that middle ground of complexity and noise. But the paper also notes the main limitation: whether this hybrid structure actually means anything on real data, like parses or minimizer digests Lalam

Tom: That’s what they emphasize as the open question for now, even though they confirm it's correct and simple to implement Lu The encoding of a character is defined by the rank of its frequency among the characters that follow the previous character in the text.

Jane: And then they use this encoding over a small, skewed alphabet during their backward search, and they recover that one piece of information—the first character of the pattern—with just one CSA-like step on an array called psi E Lu It’s a clever way to get the lookup done.

Meng: From an engineering viewpoint, it sounds like they are solving a specific bottleneck in the search process by turning what used to be a complex FM-index step into something simpler Tom But I still need to see how this scales when we move beyond synthetic data and onto messy, real text.

Lalam: The paper also suggests that locating works with standard suffix-array sampling, and counting is exact because of the lemma they prove Jane That means the location part is solid, even if the first step relies on this new hybrid trick.

Lu: In terms of future work, they suggest a combination: a move structure on bwt E followed by one CSA-style step on psi E for even better results down the line Tom That suggests combining these two indexing ideas for improved performance later on.

Jane: It’s interesting because it shows that move structures are best suited for smaller alphabets, but the standard fixes still store pointers or counts for every character which costs space proportional to sigma per sample Lu That’s a real cost comparison.

Tom: So we have this hybrid structure that is fast under specific noisy conditions but potentially larger than other methods, and the authors are looking ahead to a more combined approach for better results.

Jane: The title "More RLBWT Tricks" suggests they are showing how to creatively mix these existing indexing tools together, rather than inventing something entirely new.

Lu: It’s a practical demonstration of how combining different indexing ideas can lead to something functional, even if it’s not immediately obvious how it will perform on real data like parses and minimizer digests Meng That combination might be useful for the parse level of a two-level index.

Tom: So they've shown that this approach has some specific wins in terms of speed under certain noise levels, but the big question remains whether those wins are general enough to matter when you look at actual text data.

Jane: That’s a fair assessment. It’s a neat trick for intermediate alphabet sizes, but we need more evidence that it holds up when things get more complex.

Lu: We should keep an eye on their suggested future work about combining move structures and CSA steps because that sounds like the logical next step to try and improve those real-data performance metrics Meng

Lalam: So, the paper gives us a specific, simple hybrid structure that has some concrete speedups on repetitive data under certain noise levels but leaves the real-world applicability uncertain.

Tom: That's all we have for "More RLBWT Tricks" today. We’ll be right back after these messages.

Conclusion: Tom: So we’re looking at "More RLBWT Tricks," and what they’ve done is combine FM-indexes and compressed suffix arrays in a specific, simple way to improve search speed under certain conditions.

Jane: It seems like the authors are really focused on making this hybrid structure practical for real-world use, even though they admit it isn't a silver bullet.

Lu: They’re showing that this combination is correct and simple to implement, especially when you look at how the encoding works over a small alphabet.

Meng: But Meng’s concern is definitely the size of the index. The paper shows that when you put everything together, the resulting index can be quite large compared to other existing methods.

Lalam: Lalam confirms that they found this specific combination is fast—it's actually faster than some of the indexes we were testing at intermediate alphabet sizes with one percent noise.

Tom: So, it’s not just theoretical; they’re seeing concrete performance gains when you test it on synthetic repetitive data, specifically in that ten to ten thousand alphabet range with one percent noise.

Jane: And the authors are pointing out that while this hybrid is fast in those specific conditions, we still don't know if it translates well when you look at things like actual parses or minimizer digests.

Lu: The implication is they suggest moving toward a structure that combines move structures on the bwt e with one CSA-style step on psi E for better results down the line.

Meng: That combination might be useful for the parse level of a two-level index. It shows that combining different indexing ideas can lead to something practical, even if it’s not immediately obvious how it will perform on real data like parses or minimizer digests.

Tom: So they've shown us a neat trick for intermediate alphabet sizes, but the big question is whether that performance holds up when we move to more complex structures like actual text data.

Center for Biotechnology and Bioengineering (CeBiB), Chile

cs.DS

Submitted: 2026-09-30

Updated: 2026-11-15

Code: https://github.com/TravisGagie/Hybrid-FM-CSA

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 79/100

The gist: FM-indexes and compressed suffix arrays are often treated as interchangeable, but they behave differently as the alphabet grows The hybrid is correct and simple to implement On synthetic repetitive…

Key concepts

Hybrid Encoding Mechanism
Character encoding is defined by the rank of a character's frequency among characters that follow it in the text. This results in an encoded text E composed mostly of small numbers. A pattern P is encoded using these rankings, and decoding requires knowing the first character of P.
FM-index
An FM-index uses a wavelet tree over the encoding to answer rank queries efficiently. Its performance depends on the alphabet size, which can slow it down as the alphabet grows. The hybrid structure aims to mitigate this dependency.
Compressed Suffix Array (CSA)
A CSA stores $\Psi[i] = SA^{-1}[SA[i] + 1]$, which is the row of the suffix starting one position later. Locating patterns in a CSA involves binary searching blocks of these values, offering an alternative to standard FM-index steps.
$\Psi$E
$\Psi$E is a sequence derived from the hybrid encoding that is a primary concern for space analysis. It has more runs than the original Burrows–Wheeler transform (BWT(T)), making it a major contributor to the index size.

Terminology

Summary

FM-indexes and compressed suffix arrays are often treated as interchangeable, but they behave differently as the alphabet grows The hybrid is correct and simple to implement On synthetic repetitive data it has the following properties • Its query time barely depends on the alphabet size, because the Huffman-shaped wavelet tree over the encoding has depth about 2 whatever the alphabet • At intermediate alphabet sizes (10 to 10,000) with 1% noise, it is the fastest of the indexes we tried, by 1. p. 11 to 1.8 times (the smallest margin is within measurement noise) • It is never the smallest The main open question is whether this hybrid means anything on real data, such as parses and minimizer digests

Hybrid Encoding Mechanism

The encoding of a character is defined by the rank of its frequency among the characters that follow the previous character in the text The encoded text E is then mostly small numbers (on our test data, mostly 1s) A pattern P[0] is encoded using the text’s rankings, and the catch is that the encoding of P only makes sense given P’s first character The encoding of T can be decoded from left to right given T[0] and the lists

Counting and Locating

The lemma proves that counting is exact by stating that a pattern occurs if and only if T[p] = P[0] and E[p + 1 to p + m − 1] = Q[1 to m − 1] Locating with suffix-array samples works unchanged, where the rows we need to locate are the positions k of P[0] in ΨE The result is an FM-index for all but one step of the search, and a CSA for the last one

Performance Analysis

The query time barely depends on the alphabet size because the Huffman-shaped wavelet tree over the encoding has depth about 2 whatever the alphabet At intermediate alphabet sizes (10 to 10,000) with 1% noise, it is the fastest of the indexes we tried, by 1.1 to 1.8 times (the smallest margin is within measurement noise) The compact version of the hybrid is dominated because its encoding and ΨE together have more runs than the original Burrows–Wheeler transform

Space and Real Data Implications

The hybrid’s size is dominated by the runs of BWT(E) and especially ΨE On real data, the size of E can be up to 2z(T), but we see no reason for r(E) ≤ r(T) in general The extra runs are the main cost of the hybrid when compared to other indexes

Future Directions

The paper suggests a combination: a move structure on BWT(E), followed by one CSA-style step on ΨE The hybrid suggests that move structures are best suited to small alphabets, whereas the standard fixes store pointers or counts for every character which costs space proportional to σ per sample Open questions include implementing and evaluating locating, including the ϕ-based approach of Section 3.4 and comparing against the relabeled-block FM-index baseline The hybrid may be useful for the parse level of a two-level index [3] The idea of the hybrid is due to the author

References

[1] O. Y. Ahmed, M. Rossi, T. Gagie, C. Boucher, and B. Langmead

[3] N. K. Brown, T. Gagie, G. Manzini, G. p. 3 Navarro, and M. p. 3-Sciortino

[8] P. Ferragina and G.-Manzini

[13] R. Grossi and J. S. Vitter

[15] D. Kempa and T. p. 8 p. 8 p. 8 Kociumaka

[16] V.-Mäkinen and G. p. 9 p. 9 p. 9-Navarro

[17] V.-Mäkinen, G. p. 9 p. 9 p. 9-Navarro, J. p. 3 p. 3 p. 3 Sirén, and N. p. 8 p. 8 p. 8 Välimäki

[18] T. Nishimoto and Y. Tabei

[19] D.-Okanohara and K.-Sadakane

[20] A.-Ordóñez, G. p. 5 p. 5 p. 5-Navarro, and N. p. 3 p. 3 p. 3 R. Brisaboa

[21] K.-Sadakane

[23] J. Sirén

[3] M. Zakeri, N.-K. Brown, O.-Y. Ahmed, T.-Gagie, and B. p. 0-Langmead

[4] B. Chapin and S. p. 8 R. Tate

[5] J.-J. Deng, W.-K.-Hon, D.-Köppl, and K.-Sadakane

[6] A. Fariña, N. R. Brisaboa, G. p. 5-Navarro, F. p. 3 Claude, Á. S., and E. Rodríguez

[7] P.-Fenwick

[8] P.-Ferragina and G.-Manzini

[11] I. Grebnov

[12] R. Grossi and J. S. Vitter

[13] R.-Grossi and J. S. Vitter

[14] A.-Hong, M.-Oliva, D.-Köppl, H.-Bannai, C. Boucher, and T.-Gagie

[15] D. Kempa and T. Kociumaka

[16] V.-Mäkinen and G.-Navarro

[17] V.-Mäkinen, G.-Navarro, J. Sirén, and N. Välimäki

[18] T. Nishimoto and Y. Tabei

[19] D.-Okanohara and K.-Sadakane

[20] A.-Ordóñez, G.-Navarro, and N. R. Brisaboa

[21] K.-Sadakane

[23] J. Sirén

--- Page 1 ---

Mixing FM-indexes and CSAs: Travis Gagie Center for Biotechnology and Bioengineering (CeBiB), Chile Preliminary version, October 1, 2026 --- Page 1

Abstract FM-indexes and compressed suffix arrays (CSAs) are often treated as interchangeable, but they behave differently as the alphabet grows An FM-index step costs about one cache miss per level of a wavelet tree, so it gets slower with the alphabet size A CSA step is a binary search whose range shrinks as characters get rarer We describe a simple hybrid Each character of the text is replaced by the rank of its frequency among the characters that follow the previous character We backward-search on this encoding, which is over a small, skewed alphabet, and recover the one piece of information the encoding loses (the first character of the pattern) with a single CSA-like step on an array we call ΨE Counting is exact, and locating works with standard suffix-array sampling

--- Page 3 ---

i SA[i] Ψ[i] suffix T[SA[i] [15] SA[15] 5 BANANA CABANA

0 28 14 S A

1 27 0 A&N

2 23 13 ABANA&C

3 25 &B ANA&B

4 1 &ANANA BANDANA BANANA CABANA&B

--- Page 4 ---

i SA[i] Ψ[i] suffix T[SA[i] [15] SA[15] 5 BANANA CABANA

0 28 14 S A

1 27 &0 A&N

2 23 &13 ABANA&C

3 25 &B ANA&B

--- Page 4 ---

Backward Search and FM-indexes

Backward search finds the SA interval of each suffix of a pattern P, from shortest to longest If [s, e] is the interval for P[j + 1 to m − 1] and c = P[j], then the interval for cP[j + 1 to m − 1] is [C[c] + rankc(L, s), C[c] + rankc(L, e + 1) − 1] The FM-index [8] answers rankc queries with a wavelet tree [12] over L A balanced tree has ⌈lg σ⌉ levels A Huffman-shaped tree has fewer than H0(T) + 1 levels on average, where H0 is the empirical entropy Locality

Compressed Suffix Arrays

A CSA [13] stores Ψ[i] = SA−1[SA[i] + 1]: the row of the suffix that starts one position later To extend the interval [s, e] of P[j+1 to m−1] by c, we binary-search c’s block of Ψ for the values that lie in [s, e]

Hybrid Structure

For each character a, list the distinct characters that follow occurrences of a in T (ignoring the final 5) ordered by how often they follow a, with ties broken consistently (we use the alphabet order) Call the position of b in a’s list its rank after a, ρa(b), starting from 1 The encoding of T is E[i] = ρTi−1 for 1 ≤ i ≤ n − 2, E[n − 1] = S A pattern P[0 to m − 1] (without S) is encoded the same way, using the text’s lists

The hybrid is correct and simple to implement To count BANA, we search for Q = 1 1 1. Its interval in SAE is [3, 12] (Figure 3) The other seven encode BAN after a, NAN after an A, and ANA after a D or an N: once encoded, they look the same as ANA after a B

Space Analysis

The index consists of the rank lists (one entry per distinct bigram), a run-length representation of BWT(E), and a run-length representation of ΨE ΨE is the bigger concern It is a sequence over the full alphabet, and on our test data with σ ≥ 10 it has 1.3 to 2.3 times as many runs as BWT(T) The compact hybrid is 1. p. 17 to 3.9 times larger than a compressed run-length CSA of the text

Experiments

Table 1 shows the number of runs, in millions, for n = 5 × 10 7 BWT(E) has up to 1.25 times as many runs as BWT(T) with 0. p. 11% noise For σ ≥ 10, ΨE has 1. p. 0 p. 03 to 2.3 times as many runs than BWT(T) Together the two have 1. p. 1 p. 17 to 3.0 times as many runs as BWT(T) at 0. p. 1 p. 11% noise

--- Page 5 ---

i SA[i] Ψ[i] suffix T[SA[i] [15] SA[15] 5 BANANA CABANA

0 28 14 S A

1 27 &0 A&N

2 23 &13 ABANA&C

3 25 &B ANA&B

--- Page 6 ---

Locating Sketch

Locating with suffix-array samples works unchanged Samples would be needed: • at run boundaries of the preceding characters listed in SA′ order; • at the σ boundaries in SA′ where the first character changes; • at run ends of ΨE, to get an initial toehold from an r-index on E The hybrid suggests a combination: a move structure on BWT(E), followed by one CSA-style step on ΨE, which is a binary search and needs no scanning The rough model says the scans then cost about σE runs

--- Page 7 ---

The hybrid offers a different point on the space–time curve: at intermediate alphabet sizes with some noise it is the fastest index, at 2.7 to 4 times the space of the smallest one

[1] O. Y. Ahmed, M.-Rossi, T.-Gagie, C. Boucher, and B.-Langmead

[3] N. K. Brown, T.-Gagie, G.-Manzini, G. p. 3-Navarro, and M. p. 3-Sciortino

[8] P. Ferragina and G.-Manzini

[13] R. Grossi and J. S. Vitter

[15] D. Kempa and T. Kociumaka

[16] V.-Mäkinen and G.-Navarro

[17] V.-Mäkinen, G.-Navarro, J. Sirén, and N. Välimäki

[18] T. Nishimoto and Y. Tabei

[19] D.-Okanohara and K.-Sadakane

[20] A.-Ordóñez, G.-Navarro, and N. R. Brisaboa

[21] K.-Sadakane

[23] J. Sirén

--- Page 11 ---

Table 1 shows the number of runs, in millions, for n = 5 × 10 7 BWT(E) has up to 1.25 times as many runs as BWT(E) with 0. p. 11% noise For σ ≥ 10, ΨE has 1.3 to 2.3 times as many runs than BWT(T) Together the two have 1.7 to 3.0 times as many runs as BWT(T) at 0.1% noise

--- Page 13 ---

Table 2 shows the query time in µs per query for m = 32 / index size in MB, for n = 5×10 7 In each row, the fastest query time is in bold red and the smallest size is in bold The compact hybrid is dominated on this data: it is always larger than the Elias–Fano RLCSA of T, and about as fast or up to 1.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Backward search over an order-1 rank encoding allows searching patterns in highly repetitive text collections like pangenomes or minimizer digests where alphabets are large, by replacing characters with their relative frequency among subsequent characters. This enables efficient pattern matching in contexts where traditional FM-indexes become slow due to large alphabet sizes.

  2. The hybrid index combines an FM-index step over the encoding E with a CSA step on an array PsiE, allowing recovery of the lost information (the first character of the pattern) with a single CSA-like step. This hybrid is described as being correct and simple to implement and achieves query times that barely depends on the alphabet size.

  3. The system can perform exact counting for patterns in text sequences, as the lemma proves: T[p] = P if and only if T[p] = P[0] and E[p + 1 to p + m − 1] = Q[1 to m − 1]. This means the AI system can accurately determine the number of occurrences of a pattern in a complex text structure.

  4. Locating operations can be performed using suffix-array sampling, which works unchanged, and leveraging the CSA-style lists derived from PsiE to find occurrences quickly. This provides an efficient mechanism for finding where specific patterns start within the indexed text.

Related papers