Space-time Trade-offs for the LCP Array of Wheeler DFAs.
Int Symp String Process Inf Retr
; 14240: 143-156, 2023 Sep.
Article
in En
| MEDLINE
| ID: mdl-39108943
ABSTRACT
Recently, Conte et al. generalized the longest-common prefix (LCP) array from strings to Wheeler DFAs, and they showed that it can be used to efficiently determine matching statistics on a Wheeler DFA [DCC 2023]. However, storing the LCP array requires O n log n bits, n being the number of states, while the compact representation of Wheeler DFAs often requires much less space. In particular, the BOSS representation of a de Bruijn graph only requires a linear number of bits, if the size of alphabet is constant. In this paper, we propose a sampling technique that allows to access an entry of the LCP array in logarithmic time by only storing a linear number of bits. We use our technique to provide a space-time tradeoff to compute matching statistics on a Wheeler DFA. In addition, we show that by augmenting the BOSS representation of a k -th order de Bruijn graph with a linear number of bits we can navigate the underlying variable-order de Bruijn graph in time logarithmic in k , thus improving a previous bound by Boucher et al. which was linear in k [DCC 2015].
Full text:
1
Collection:
01-internacional
Database:
MEDLINE
Language:
En
Journal:
Int Symp String Process Inf Retr
Year:
2023
Type:
Article
Affiliation country:
Italy