Grammar index by induced suffix sorting
Theoretical Computer Science · 2026-09 · 1082 · 116080
DOI: 10.1016/j.tcs.2026.116080 ↗Kurz gefasst
Fachartikel in der Zeitschrift Theoretical Computer Science, 2026-09. Verfasst von Tooru Akagi und 5 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben. Gefördert von: Japan Society for the Promotion of Science, Research Institute for Mathematical Sciences, Japan Society for the Promotion of Science London.
Abstract (Originalsprache)
Pattern matching is the most central task for text indices. Most recent indices leverage compression techniques to make pattern matching feasible for massive but highly-compressible datasets. Within this kind of indices, we propose a new compressed text index built upon a grammar compression based on induced suffix sorting [Nunes et al., DCC'18]. We show that this grammar exhibits a locality sensitive parsing property, which allows us to specify, given a pattern $P$, certain substrings of $P$, called cores, that are similarly parsed in the text grammar whenever these occurrences are extensible to occurrences of $P$. Supported by the cores, given a pattern of length $m$, we can locate all its $occ$ occurrences in a text $T$ of length $n$ within $O(m \lg |\mathcal{S}| + occ_C \lg|\mathcal{S}| \lg n + occ)$ time, where $\mathcal{S}$ is the set of all characters and non-terminals, $occ$ is the number of occurrences, and $occ_C$ is the number of occurrences of a chosen core $C$ of $P$ in the right hand side of all production rules of the grammar of $T$. Our grammar index requires $O(g)$ words of space and can be built in $O(n)$ time using $O(g)$ working space, where $g$ is the sum of the right hand sides of all production rules. We underline the strength of our grammar index with an exhaustive practical evaluation that gives evidence that our proposed solution excels at locating long patterns in highly-repetitive texts.
Förderung
- Japan Society for the Promotion of Science
- Research Institute for Mathematical Sciences
- Japan Society for the Promotion of Science London
Zitieren
APA
Akagi, T., Köppl, D., Nakashima, Y., Inenaga, S., Bannai, H., & Takeda, M. (2026). Grammar index by induced suffix sorting. Theoretical Computer Science, 1082, 116080. https://doi.org/10.1016/j.tcs.2026.116080
Vancouver
Akagi T, Köppl D, Nakashima Y, Inenaga S, Bannai H, Takeda M. Grammar index by induced suffix sorting. Theoretical Computer Science. 2026;1082:116080. doi:10.1016/j.tcs.2026.116080
BibTeX
@article{Akagi2026,
author = {Akagi, Tooru and Köppl, Dominik and Nakashima, Yuto and Inenaga, Shunsuke and Bannai, Hideo and Takeda, Masayuki},
title = {Grammar index by induced suffix sorting},
journal = {Theoretical Computer Science},
year = {2026},
volume = {1082},
pages = {116080},
doi = {10.1016/j.tcs.2026.116080}
}
EUVIMED