Order-preserving indexing
Order-preserving indexing
复制标题
保序索引
DOI：
10.1016/j.tcs.2015.06.050
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Tomasz Waleń
中科院分区：
文献类型：
--
作者：
M. Crochemore;C. Iliopoulos;Tomasz Kociumaka;M. Kubica;A. Langiu;S. Pissis;J. Radoszewski;W. Rytter;Tomasz Waleń
Kubica et al. [33]和Kim等人[29]引入保序模式匹配：对于给定文本，目标是找到其具有与给定模式相同的“形状”的因子。已知的结果包括这个问题的线性时间算法（在多项式有界字母表的情况下）和推广到多个模式。我们提出了一个索引，使保序模式匹配查询的时间成比例的模式长度。该索引可以在O（n log log n）的预期时间内构造，也可以在O（n log 2 log n/log log log n）的最坏情况下构造。它是一个不完整的保序后缀树，在每个分支节点可能会丢失一个单一的边缘标签。对于大多数应用，这种不完整的后缀树提供了与完整后缀树相同的功能。我们展示了一些他们的应用，包括计算最长的共同因素，最长的先前出现的因素和平方在一个字符串中的顺序保持设置。我们还给出了一个O（nlog n）时间算法构造完全保序后缀树。
Abstract Kubica et al.[33] and Kim et al.[29] introduced order-preserving pattern matching: for a given text the goal is to find its factors having the same ‘shape’as a given pattern. Known results include a linear-time algorithm for this problem (in case of polynomially-bounded alphabet) and a generalization to multiple patterns. We propose an index that enables order-preserving pattern matching queries in time proportional to pattern length. The index can be constructed in O (n log log n) expected time or in O (n log 2 log n/log log log n) worst-case time. It is an incomplete order-preserving suffix tree which may miss a single edge label at each branching node. For most applications such incomplete suffix trees provide the same functional power as the complete ones. We show a number of their applications, including computation of longest common factors, longest previously occurring factors and squares in a string in the order-preserving setting. We also give an O (n log n)-time algorithm constructing complete order-preserving suffix trees.