论文标题
语法压缩的自我指数用lyndon单词
Grammar-compressed Self-index with Lyndon Words
论文作者
论文摘要
我们介绍了一类新的直线程序（SLP），名为Lyndon SLP，灵感来自Lyndon树（Barcelo，1990）。基于此SLP，我们提出了一个可以从$ o（n \ lg n）$预期时间构建的$ o（g）$空间单词的自我指数数据结构，从而取回了$ p $ lengthy $ p $ p $ lengthy $ m $ in $ o（m + \ lg lg n + lg n $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t的开始位置， $ t $的Lyndon SLP和$ occ $是$ t $中的$ p $的数量。
We introduce a new class of straight-line programs (SLPs), named the Lyndon SLP, inspired by the Lyndon trees (Barcelo, 1990). Based on this SLP, we propose a self-index data structure of $O(g)$ words of space that can be built from a string $T$ in $O(n \lg n)$ expected time, retrieving the starting positions of all occurrences of a pattern $P$ of length $m$ in $O(m + \lg m \lg n + occ \lg g)$ time, where $n$ is the length of $T$, $g$ is the size of the Lyndon SLP for $T$, and $occ$ is the number of occurrences of $P$ in $T$.
