2026-08-07T07:37:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16138 2024-03-06T10:56:40Z ddc:004 open_access

Bi-Directional r-Indexes Arakawa, Yuma Navarro, Gonzalo Sadakane, Kunihiko Compressed text indexes Burrows-Wheeler Transform highly repetitive text collections Indexing highly repetitive texts is important in fields such as bioinformatics and versioned repositories. The run-length compression of the Burrows-Wheeler transform (BWT) provides a compressed representation particularly well-suited to text indexing. The r-index is one such index. It enables fast locating of occurrences of a pattern within O(r) words of space, where r is the number of equal-letter runs in the BWT. Its mechanism of locating is to maintain one suffix array sample along the backward-search of the pattern, and to compute all the pattern positions from that sample once the backward-search is complete. In this paper we develop this algorithm further, and propose a new bi-directional text index called the br-index, which supports extending the matched pattern both in forward and backward directions, and locating the occurrences of the pattern at any step of the search, within O(r+r_R) words of space, where r_R is the number of equal-letter runs in the BWT of the reversed text. Our experiments show that the br-index captures the long repetitions of the text, and outperforms the existing indexes in text searching allowing some mismatches except in an internal part. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuma Arakawa and Gonzalo Navarro and Kunihiko Sadakane 2022 Is Part Of LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2022.11 urn:nbn:de:0030-drops-161386 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.11 eng https://creativecommons.org/licenses/by/4.0/legalcode