Time-space trade-offs for longest common extensions
Time-space trade-offs for longest common extensions
复制标题
最长公共扩展的时空权衡
DOI：
10.1016/j.jda.2013.06.003
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Bille P
中科院分区：
文献类型：
--
作者：
Bille P
我们回顾了最长公共扩展(LCE)问题，即将字符串T预处理为支持快速LCE查询的紧凑数据结构。LCE查询获取T中的一对索引(i，j)，并返回从位置i和j开始的T后缀中最长公共前缀的长度。我们研究了该问题的时空权衡，即用于数据结构的空间与回答LCE查询的最差情况时间的权衡。设n是T的长度，给定一个参数τ，1⩽τ⩽n，我们展示了如何获得O(n/τ)空间和O(τ)查询时间，或者O(n/τ)空间和O(τ(i，j)|/τ))查询时间，其中|lce(i，j)|表示查询返回的LCE的长度。当τ=1或τ=n时，这些界提供了第一个平滑的折衷，并且几乎匹配了已知的极值界。我们将结果应用于几个应用，其中包括近似字符串匹配和计算回文，这些应用是计算瓶颈。我们还提出了一种有效的技术，将对两个字符串的LCE查询减少为一个字符串。最后，我们给出了非均匀单元探针模型中LCE数据结构的时空积的一个下界，表明我们的第二种权衡是接近最优的。
We revisit the longest common extension (LCE) problem, that is, preprocess a string T into a compact data structure that supports fast LCE queries. An LCE query takes a pair (i, j) of indices in T and returns the length of the longest common prefix of the suffixes of T starting at positions i and j. We study the time–space trade-offs for the problem, that is, the space used for the data structure vs. the worst-case time for answering an LCE query. Let n be the length of T. Given a parameter τ, 1⩽ τ⩽ n, we show how to achieve either O (n/τ) space and O (τ) query time, or O (n/τ) space and O (τ log (| LCE (i, j)|/τ)) query time, where| LCE (i, j)| denotes the length of the LCE returned by the query. These bounds provide the first smooth trade-offs for the LCE problem and almost match the previously known bounds at the extremes when τ= 1 or τ= n. We apply the result to obtain improved bounds for several applications where the LCE problem is the computational bottleneck, including approximate string matching and computing palindromes. We also present an efficient technique to reduce LCE queries on two strings to one string. Finally, we give a lower bound on the time–space product for LCE data structures in the non-uniform cell probe model showing that our second trade-off is nearly optimal.