.png){kind=icon}
.png){kind=icon}
Return
Relative Compressed Reverse Suffix Array
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.62.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Suffix trees and suffix arrays are two fundamental data structures in the field of string algorithms. For a string (a.k.a. text or sequence) of length n over an alphabet of size sigma, these structures typically require O(n log n) bits of space. The FM-index provides a compressed representation of the suffix array in approximate to n log sigma bits, allowing for efficient queries on both the suffix array and its inverse array in near logarithmic time. In certain applications, such as approximate pattern matching (i.e., with wildcards, mismatches, edits), there is a need to access the suffix array of a text, as well as the suffix array of text's reverse. Motivated by this, we explore the possibility of encoding the suffix array of the reversed text in a compact form, assuming the availability of the FM-index for the original text. Our first solution is an O(n)-bit (relative) encoding of the suffix array of the reversed text, with the time for decoding an entry being only O(log* n) times that of decoding an entry in the text's suffix array using FM-index. We then demonstrate how to reduce the space to O(n/kappa) bits for a parameter kappa, while multiplicative factor in time becomes approximately O(kappa log* n + kappa(3)). We can also support inverse suffix array and longest common extension queries on the reversed text. These results are achieved through some careful and non-trivial application of various succinct data structure techniques.
Keywords:
String Matching
Text Indexing
Data Structures
Suffix Trees
Journal
4
IF:
0
Papers:
81
Citations:
0
View more organizations