Average-case linear-time similar substring searching by the q-gram distance.
Average-case linear-time similar substring searching by the q-gram distance.
复制标题
通过 q-gram 距离进行平均情况线性时间相似子串搜索。
DOI：
10.1016/j.tcs.2014.02.022
复制
发表时间：
2014
影响因子：
1.1
通讯作者：
M. Kudo and A. Nakamura
中科院分区：
文献类型：
--
作者：
H. Hanada;M. Kudo and A. Nakamura
本文研究了在q-gram距离上的相似子串搜索问题。q-g距离d q （x, y）是两个字符串x和y之间的相似度度量，由它们之间不同的q-g数定义。该距离可以用来代替编辑距离，因为它的计算成本更低，0 (| x|+| y|) vs. 0 (| x|| y|)，并且它很好地逼近了编辑距离。但是，如果将这个距离应用于查找给定模式p的长文本t中所有相似字符串的问题，则总计算成本有时是不可接受的。Ukkonen已经提出了两种快速算法：一种是数组算法，另一种是树算法。当“相似”在dq中表示小于等于k时，它们的时间复杂度分别为O （| ~ |k + |p |）和O （| ~ |log k+ |p |）。在本文中，我们提出了两种平均情况复杂度为O （| t|+| p|）的算法，尽管它们的最坏情况复杂度仍然分别为O （| t| k+| p|）和O （| t| log k+| p|）。在t随机抽样的假设和q大于阈值的条件下，分析了平均情况复杂度的线性关系。该算法利用了这样一个事实，即如果子字符串的起始位置很接近，则t中的相似子字符串通常位于非常接近的位置。在第二种算法中，我们采用由数组和搜索树支持的双链表，在O （log k）时间内搜索列表元素。实验结果支持他们理论的平均情况复杂性。
In this paper we consider the problem of similar substring searching in the q-gram distance. The q-gram distance d q (x, y) is a similarity measure between two strings x and y defined by the number of different q-grams between them. The distance can be used instead of the edit distance due to its lower computation cost, O (| x|+| y|) vs. O (| x|| y|), and its good approximation for the edit distance. However, if this distance is applied to the problem of finding all similar strings, in a long text t, to a given pattern p, the total computation cost is sometimes not acceptable. Ukkonen already proposed two fast algorithms: one with an array and the other with a tree. When “similar” means k or less in d q, their time complexities are O (| t| k+| p|) and O (| t| log k+| p|), respectively. In this paper, we propose two algorithms of average-case complexity O (| t|+| p|), although their worst-case complexities are still O (| t| k+| p|) and O (| t| log k+| p|), respectively. The linearity of the average-case complexity is analyzed under the assumption of random sampling of t and the condition that q is larger than a threshold. The algorithms exploit the fact that similar substrings in t are often found at very close positions if the beginning positions of the substrings are close. In the second proposed algorithm, we adopted a doubly-linked list supported by an array and a search tree to search for a list element in O (log k) time. Experimental results support their theoretical average-case complexities.