Testing Suffixient Sets
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915335191396352 |
|---|---|
| author | Cenzato, Davide Olivares, Francisco Prezza, Nicola |
| author_facet | Cenzato, Davide Olivares, Francisco Prezza, Nicola |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_08225 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Testing Suffixient Sets Cenzato, Davide Olivares, Francisco Prezza, Nicola Data Structures and Algorithms 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. |
| title | Testing Suffixient Sets |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.08225 |