Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.17300 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909708229541888 |
|---|---|
| author | Dinklage, Patrick Fischer, Johannes Nalbach, Lukas Zumbrink, Jan |
| author_facet | Dinklage, Patrick Fischer, Johannes Nalbach, Lukas Zumbrink, Jan |
| contents | In pattern matching on strings, a locate query asks for an enumeration of all the occurrences of a given pattern in a given text. The r-index [Gagie et al., 2018] is a recently presented compressed self index that stores the text and auxiliary information in compressed space. With some modifications, locate queries can be answered in optimal time [Nishimoto & Tabei, 2021], which has recently been proven relevant in practice in the form of Move-r [Bertram et al., 2024]. However, there remains the practical bottleneck of evaluating function $Φ$ for every occurrence to report. This motivates enhancing the index by a compressed representation of the suffix array featuring efficient random access, trading off space for faster answering of locate queries [Puglisi & Zhukova, 2021]. In this work, we build upon this idea considering two suitable compression schemes: Relative Lempel-Ziv [Kuruppu et al., 2010], improving the work by Puglisi and Zhukova, and LZ-End [Kreft & Navarro, 2010], introducing a different trade-off where compression is better than for Relative Lempel-Ziv at the cost of slower access times. We enhance both the r-index and Move-r by the compressed suffix arrays and evaluate locate query performance in an experiment. We show that locate queries can be sped up considerably in both the r-index and Move-r, especially if the queried pattern has many occurrences. The choice between two different compression schemes offers new trade-offs regarding index size versus query performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_17300 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | RLZ-r and LZ-End-r: Enhancing Move-r Dinklage, Patrick Fischer, Johannes Nalbach, Lukas Zumbrink, Jan Data Structures and Algorithms In pattern matching on strings, a locate query asks for an enumeration of all the occurrences of a given pattern in a given text. The r-index [Gagie et al., 2018] is a recently presented compressed self index that stores the text and auxiliary information in compressed space. With some modifications, locate queries can be answered in optimal time [Nishimoto & Tabei, 2021], which has recently been proven relevant in practice in the form of Move-r [Bertram et al., 2024]. However, there remains the practical bottleneck of evaluating function $Φ$ for every occurrence to report. This motivates enhancing the index by a compressed representation of the suffix array featuring efficient random access, trading off space for faster answering of locate queries [Puglisi & Zhukova, 2021]. In this work, we build upon this idea considering two suitable compression schemes: Relative Lempel-Ziv [Kuruppu et al., 2010], improving the work by Puglisi and Zhukova, and LZ-End [Kreft & Navarro, 2010], introducing a different trade-off where compression is better than for Relative Lempel-Ziv at the cost of slower access times. We enhance both the r-index and Move-r by the compressed suffix arrays and evaluate locate query performance in an experiment. We show that locate queries can be sped up considerably in both the r-index and Move-r, especially if the queried pattern has many occurrences. The choice between two different compression schemes offers new trade-offs regarding index size versus query performance. |
| title | RLZ-r and LZ-End-r: Enhancing Move-r |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.17300 |