2026-10-08T15:22:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23809 2026-02-09T05:17:17Z ddc:004 open_access

Faster Run-Length Compressed Suffix Arrays Brown, Nathaniel K. Gagie, Travis Manzini, Giovanni Navarro, Gonzalo Sciortino, Marinella Run-length compressed suffix arrays interpolative coding two-level indexing We first review how we can store a run-length compressed suffix array (RLCSA) for a text T of length n over an alphabet of size σ whose Burrows-Wheeler Transform (BWT) consists of r runs in O (r log (n / r) + r log σ + σ) bits such that later, given character a and the suffix-array (SA) interval for P, we can find the SA interval for a P in O (log r_a + log log n) time, where r_a is the number of runs of copies of a in the BWT. We then show how to modify the RLCSA such that we find the SA interval for a P in only O (log r_a) time, without increasing its asymptotic space bound. Our key idea is applying a result by Nishimoto and Tabei (ICALP 2021) and then replacing rank queries on sparse bitvectors by a constant number of select queries. We also review two-level indexing and discuss how our faster RLCSA may be useful in improving it. Finally, we briefly discuss how two-level indexing may speed up a recent heuristic for finding maximal exact matches of a pattern with respect to an indexed text. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathaniel K. Brown and Travis Gagie and Giovanni Manzini and Gonzalo Navarro and Marinella Sciortino 2025 Is Part Of OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Grossi.10 urn:nbn:de:0030-drops-238095 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.10 eng https://creativecommons.org/licenses/by/4.0/legalcode