Testing Suffixient Sets
For researchers in string algorithms and data compression, this work offers efficient methods to verify and optimize a novel compression scheme.
The paper introduces suffixient sets as a new compression technique for prefix arrays and provides linear-time algorithms to determine if a given subset of text positions is a suffixient set and to find a suffixient set of minimum cardinality.
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.