| 1 |
FM-Index Reveals the Reverse Suffix Array
|
|
|
|
Abstract:
Given a text T[1,n] over an alphabet ? of size ?, the suffix array of T stores the lexicographic order of the suffixes of T. The suffix array needs ?(nlog n) bits of space compared to the n log ? bits needed to store T itself. A major breakthrough [FM - Index, FOCS'00] in the last two decades has been encoding the suffix array in near-optimal number of bits (? log ? bits per character). One can decode a suffix array value using the FM-Index in log^{O(1)} n time. We study an extension of the problem in which we have to also decode the suffix array values of the reverse text. This problem has numerous applications such as in approximate pattern matching [Lam et al., BIBM' 09]. Known approaches maintain the FM - Index of both the forward and the reverse text which drives up the space occupancy to 2nlog ? bits (plus lower order terms). This brings in the natural question of whether we can decode the suffix array values of both the forward and the reverse text, but by using nlog ? bits (plus lower order terms). We answer this question positively, and show that given the FM - Index of the forward text, we can decode the suffix array value of the reverse text in near logarithmic average time. Additionally, our experimental results are competitive when compared to the standard approach of maintaining the FM - Index for both the forward and the reverse text. We believe that applications that require both the forward and reverse text will benefit from our approach.
|
|
Keyword:
Burrows - Wheeler transform; Compression; Data processing Computer science; Data Structures; FM-Index; String Algorithms; Suffix Trees
|
|
URN:
urn:nbn:de:0030-drops-121388
|
|
URL: https://doi.org/10.4230/LIPIcs.CPM.2020.13
https://drops.dagstuhl.de/opus/volltexte/2020/12138/
|
|
BASE
|
|
Hide details
|
|
|
| 3 |
On the Complexity of BWT-Runs Minimization via Alphabet Reordering ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 4 |
On the Hardness and Inapproximability of Recognizing Wheeler Graphs
|
|
Gibney, Daniel; Thankachan, Sharma V.. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. : LIPIcs - Leibniz International Proceedings in Informatics. 27th Annual European Symposium on Algorithms (ESA 2019), 2019
|
|
BASE
|
|
Show details
|
|
|
| 5 |
On the Hardness and Inapproximability of Recognizing Wheeler Graphs ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 6 |
On the Complexity of BWT-runs Minimization via Alphabet Reordering ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 7 |
On the Hardness and Inapproximability of Recognizing Wheeler Graphs ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 9 |
Structural Pattern Matching - Succinctly
|
|
Ganguly, Arnab; Shah, Rahul; Thankachan, Sharma V.. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. : LIPIcs - Leibniz International Proceedings in Informatics. 28th International Symposium on Algorithms and Computation (ISAAC 2017), 2017
|
|
BASE
|
|
Show details
|
|
|
| 11 |
Space-Time Trade-Offs for the Shortest Unique Substring Problem
|
|
Ganguly, Arnab; Hon, Wing-Kai; Shah, Rahul. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. : LIPIcs - Leibniz International Proceedings in Informatics. 27th International Symposium on Algorithms and Computation (ISAAC 2016), 2016
|
|
BASE
|
|
Show details
|
|
|
| 13 |
Forbidden Extension Queries
|
|
Biswas, Sudip; Ganguly, Arnab; Shah, Rahul. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. : LIPIcs - Leibniz International Proceedings in Informatics. 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015), 2015
|
|
BASE
|
|
Show details
|
|
|
|
|
