Testing Suffixient Sets
read the original abstract
Suffixient sets are a novel prefix array (PA) compression technique based on subsampling PA (rather than compressing the entire array like previous techniques used to do): by storing very few entries of PA (in fact, a compressed number of entries), one can prove that pattern matching via binary search is still possible provided that random access is available on the text. In this paper, we tackle the problems of determining whether a given subset of text positions is (1) a suffixient set or (2) a suffixient set of minimum cardinality. We provide linear-time algorithms solving these problems.
This paper has not been read by Pith yet.
Forward citations
Cited by 4 Pith papers
-
Computing Smallest Suffixient Arrays in Sublinear Time
Algorithm computes smallest suffixient arrays in sublinear time O((n log σ)/√log n + min(r, r-bar) log^ε n) when alphabet is small and BWT has few runs.
-
Practical Linear-Time Computation of Smallest Suffixient Sets
A linear-time one-pass practical algorithm for building smallest suffixient sets is presented and empirically shown to dominate prior constructions.
-
Smallest suffixient set maintenance in near-real-time
The smallest suffixient set can be maintained online in polyloglog time per letter in either left-to-right or right-to-left direction via Weiner's suffix tree primitives.
-
Smallest suffixient set maintenance in near-real-time
Online maintenance algorithms for the smallest suffixient set achieve polyloglog time per character using Weiner's suffix tree construction.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.