Although a significant number of compressed indexes for highly repetitive strings have been proposed thus far, developing compressed indexes that support faster queries remains a challenge. Run-length Burrows-Wheeler transform (RLBWT) is a lossless data compression by a reversible permutation of an input string and run-length encoding, and it has become a popular research topic in string processing. R-index Gagie et al., ACM'20%DIFDELCMD < ] %%% is an efficient compressed index on RLBWTwhose space usage depends not on string length but the number of runs in an RLBWT, and it supports locate queries in an optimal time with \omega are two key functions for building indexes on RLBWT, and the best previous result computes LF and \phi^{-1} in O(\log \log n) time with O} (r) words for the number r of runs in the RLBWTof an input string. Following this line of research, we present the first compressed index on RLBWT, which we callr-index-f , that supports various queries including locate, count, extract queries, decompression and prefix search in the optimal time with smaller working space of O(r) words for small alphabets in this paper. We present efficient data structures for computing two important functions of LF and \phi^{-1} in constant time with O(r) words of space , which is a bit step forward in computation time from the previous best result of O(\log \log n)time for string length n and O(r) words of space. Finally, We present algorithms for computing queries on RLBWT by leveraging those two data structures in optimal time with O(r) words of space.
Indexing highly repetitive strings (i.e., strings with many repetitions) for fast queries has become a central research topic in string processing, because it has a wide variety of applications in bioinformatics and natural language processing. Although a substantial number of indexes for highly repetitive strings have been proposed thus far, developing compressed indexes that support various queries remains a challenge. The run-length Burrows-Wheeler transform (RLBWT) is a lossless data compression by a reversible permutation of an input string and run-length encoding, and it has %DIFDELCMD < ] %%% received interest for indexing highly repetitive strings. LF and \phi^{-1 are two key functions for building indexes on RLBWT, and the best previous result computes LF and \phi^{-1} in O(\log \log n) time with O} (r) words of space for the string length n and the number r of runs in RLBWT. In this paper, we improve LF and \phi^{-1} so that they can be computed in a constant time with O(r) words of space . Subsequently, we present OptBWTR (optimal-time queries on BWT-runs compressed indexes), the first string index that supports various queries including locate, count, extract queries in optimal time and O(r) words of space.
R
Although a significant number of compressed
Indexing highly repetitive strings (i.e., strings with many repetitions) for fast queries has become a central research topic in string processing, because it has a wide variety of applications in bioinformatics and natural language processing. Although a substantial number of
R
faster
various
R
Run-length
The run-length
D
become a popular research topic in string processing. R-index
D
Gagie et al., ACM'20
R
is an efficient compressed index on RLBWTwhose space usage depends not on string length but the number of runs in an RLBWT, and it supports locate queries in an optimal time with \omega
received interest for indexing highly repetitive strings. LF and \phi^{-1
R
for the
of space for the string length n and the
D
the RLBWTof an input string. Following this line of research, we present the first compressed index on RLBWT, which we call
D
r-index-f
R
, that supports various queries including locate, count, extract queries, decompression and prefix search in the optimal time with smaller working space of O(r) words for small alphabets in this paper. We present efficient data structures for computing two important functions of
RLBWT. In this paper, we improve
R
in
so that they can be computed in a
R
, which is a bit step forward in computation time from the previous best result of O(\log \log n)time for string length n and O(r) words of space. Finally, We present algorithms for computing queries on RLBWT by leveraging those two data structures
. Subsequently, we present OptBWTR (optimal-time queries on BWT-runs compressed indexes), the first string index that supports various queries including locate, count, extract queries
R
with
and