2026-07-22T04:54:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18357 2024-03-06T11:01:35Z ddc:004 open_access

Simple Runs-Bounded FM-Index Designs Are Fast Díaz-Domínguez, Diego Dönges, Saska Puglisi, Simon J. Salmela, Leena data structures efficient algorithms Given a string X of length n on alphabet σ, the FM-index data structure allows counting all occurrences of a pattern P of length m in O(m) time via an algorithm called backward search. An important difficulty when searching with an FM-index is to support queries on L, the Burrows-Wheeler transform of X, while L is in compressed form. This problem has been the subject of intense research for 25 years now. Run-length encoding of L is an effective way to reduce index size, in particular when the data being indexed is highly-repetitive, which is the case in many types of modern data, including those arising from versioned document collections and in pangenomics. This paper takes a back-to-basics look at supporting backward search in FM-indexes, exploring and engineering two simple designs. The first divides the BWT string into blocks containing b symbols each and then run-length compresses each block separately, possibly introducing new runs (compared to applying run-length encoding once, to the whole string). Each block stores counts of each symbol that occurs before the block. This method supports the operation rank_c(L, i) (i.e., count the number of times c occurs in the prefix L[1..i]) by first determining the block i/b in which i falls and scanning the block to the appropriate position counting occurrences of c along the way. This partial answer to rank_c(L, i) is then added to the stored count of c symbols before the block to determine the final answer. Our second design has a similar structure, but instead divides the run-length-encoded version of L into blocks containing an equal number of runs. The trick then is to determine the block in which a query falls, which is achieved via a predecessor query over the block starting positions. We show via extensive experiments on a wide range of repetitive text collections that these FM-indexes are not only easy to implement, but also fast and space efficient in practice. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diego Díaz-Domínguez and Saska Dönges and Simon J. Puglisi and Leena Salmela 2023 Is Part Of LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2023.7 urn:nbn:de:0030-drops-183579 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.7 eng https://creativecommons.org/licenses/by/4.0/legalcode