Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2604.04377 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911605383495680 |
|---|---|
| author | Shibata, Hiroki Bannai, Hideo |
| author_facet | Shibata, Hiroki Bannai, Hideo |
| contents | Repetitiveness measures quantify how much repetitive structure a string contains and serve as parameters for compressed representations and indexing data structures. We study the measure $χ$, defined as the size of the smallest suffixient set. Although $χ$ has been studied extensively, its reachability, whether every string $w$ admits a string representation of size $O(χ(w))$ words, has remained an important open problem. We answer this question affirmatively by presenting the first such representation scheme. Our construction is based on a new model, the substring equation system (SES), and we show that every string admits an SES of size $O(χ(w))$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_04377 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | String Representation in Suffixient Set Size Space Shibata, Hiroki Bannai, Hideo Data Structures and Algorithms Repetitiveness measures quantify how much repetitive structure a string contains and serve as parameters for compressed representations and indexing data structures. We study the measure $χ$, defined as the size of the smallest suffixient set. Although $χ$ has been studied extensively, its reachability, whether every string $w$ admits a string representation of size $O(χ(w))$ words, has remained an important open problem. We answer this question affirmatively by presenting the first such representation scheme. Our construction is based on a new model, the substring equation system (SES), and we show that every string admits an SES of size $O(χ(w))$. |
| title | String Representation in Suffixient Set Size Space |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.04377 |