Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913426909954048 |
|---|---|
| author | Cleary, Alan M. Winjum, Joseph Dood, Jordan Inenaga, Shunsuke |
| author_facet | Cleary, Alan M. Winjum, Joseph Dood, Jordan Inenaga, Shunsuke |
| contents | Grammar-based compression is a widely-accepted model of string compression that allows for efficient and direct manipulations on the compressed data. Most, if not all, such manipulations rely on the primitive \emph{random access} queries, a task of quickly returning the character at a specified position of the original uncompressed string without explicit decompression. While there are advanced data structures for random access to grammar-compressed strings that guarantee theoretical query time and space bounds, little has been done for the \emph{practical} perspective of this important problem. In this paper, we revisit a well-known folklore random access algorithm for grammars in the Chomsky normal form, modify it to work directly on general grammars, and show that this modified version is fast and memory efficient in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_08190 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings Cleary, Alan M. Winjum, Joseph Dood, Jordan Inenaga, Shunsuke Data Structures and Algorithms Grammar-based compression is a widely-accepted model of string compression that allows for efficient and direct manipulations on the compressed data. Most, if not all, such manipulations rely on the primitive \emph{random access} queries, a task of quickly returning the character at a specified position of the original uncompressed string without explicit decompression. While there are advanced data structures for random access to grammar-compressed strings that guarantee theoretical query time and space bounds, little has been done for the \emph{practical} perspective of this important problem. In this paper, we revisit a well-known folklore random access algorithm for grammars in the Chomsky normal form, modify it to work directly on general grammars, and show that this modified version is fast and memory efficient in practice. |
| title | Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.08190 |