2026-07-22T11:09:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13964 2024-03-06T10:53:01Z ddc:004 open_access

A Fast and Small Subsampled R-Index Cobas, Dustin Gagie, Travis Navarro, Gonzalo Pattern matching r-index compressed text indexing repetitive text collections The r-index (Gagie et al., JACM 2020) represented a breakthrough in compressed indexing of repetitive text collections, outperforming its alternatives by orders of magnitude. Its space usage, 𝒪(r) where r is the number of runs in the Burrows-Wheeler Transform of the text, is however larger than Lempel-Ziv and grammar-based indexes, and makes it uninteresting in various real-life scenarios of milder repetitiveness. In this paper we introduce the sr-index, a variant that limits a large fraction of the space to 𝒪(min(r,n/s)) for a text of length n and a given parameter s, at the expense of multiplying by s the time per occurrence reported. The sr-index is obtained by carefully subsampling the text positions indexed by the r-index, in a way that we prove is still able to support pattern matching with guaranteed performance. Our experiments demonstrate that the sr-index sharply outperforms virtually every other compressed index on repetitive texts, both in time and space, even matching the performance of the r-index while using 1.5-3.0 times less space. Only some Lempel-Ziv-based indexes achieve better compression than the sr-index, using about half the space, but they are an order of magnitude slower. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dustin Cobas and Travis Gagie and Gonzalo Navarro 2021 Is Part Of LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2021.13 urn:nbn:de:0030-drops-139647 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.13 eng https://creativecommons.org/licenses/by/4.0/legalcode