String Covering: A Survey
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914452095369216 |
|---|---|
| author | Mhaskar, Neerja Smyth, W. F. |
| author_facet | Mhaskar, Neerja Smyth, W. F. |
| contents | The study of strings is an important combinatorial field that precedes the digital computer. Strings can be very long, trillions of letters, so it is important to find compact representations. Here we first survey various forms of one potential compaction methodology, the cover of a given string x, initially proposed in a simple form in 1990, but increasingly of interest as more sophisticated variants have been discovered. We then consider covering by a seed; that is, a cover of a superstring of x. We conclude with many proposals for research directions that could make significant contributions to string processing in future. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_11856 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | String Covering: A Survey Mhaskar, Neerja Smyth, W. F. Data Structures and Algorithms The study of strings is an important combinatorial field that precedes the digital computer. Strings can be very long, trillions of letters, so it is important to find compact representations. Here we first survey various forms of one potential compaction methodology, the cover of a given string x, initially proposed in a simple form in 1990, but increasingly of interest as more sophisticated variants have been discovered. We then consider covering by a seed; that is, a cover of a superstring of x. We conclude with many proposals for research directions that could make significant contributions to string processing in future. |
| title | String Covering: A Survey |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2211.11856 |