Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915571971391488 |
|---|---|
| author | Adudodla, Ankith Reddy Kempa, Dominik |
| author_facet | Adudodla, Ankith Reddy Kempa, Dominik |
| contents | Compressed indexing enables powerful queries over massive and repetitive textual datasets using space proportional to the compressed input. While theoretical advances have led to highly efficient index structures, their practical construction remains a bottleneck, especially for complex components like recompression RLSLP, a grammar-based representation crucial for building powerful text indexes that support widely used suffix and LCP array queries.
In this work, we present the first implementation of recompression RLSLP construction that runs in compressed time, operating on an LZ77-like approximation of the input. Compared to state-of-the-art uncompressed-time methods, our approach achieves up to $46\times$ speedup and $17\times$ lower RAM usage on large, repetitive inputs. These gains unlock scalability to larger datasets and affirm compressed computation as a practical path forward for fast index construction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12011 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text Adudodla, Ankith Reddy Kempa, Dominik Data Structures and Algorithms Compressed indexing enables powerful queries over massive and repetitive textual datasets using space proportional to the compressed input. While theoretical advances have led to highly efficient index structures, their practical construction remains a bottleneck, especially for complex components like recompression RLSLP, a grammar-based representation crucial for building powerful text indexes that support widely used suffix and LCP array queries. In this work, we present the first implementation of recompression RLSLP construction that runs in compressed time, operating on an LZ77-like approximation of the input. Compared to state-of-the-art uncompressed-time methods, our approach achieves up to $46\times$ speedup and $17\times$ lower RAM usage on large, repetitive inputs. These gains unlock scalability to larger datasets and affirm compressed computation as a practical path forward for fast index construction. |
| title | Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.12011 |