A Randomized Algorithm for Approximate String Matching
A Randomized Algorithm for Approximate String Matching
复制标题
一种近似字符串匹配的随机算法
DOI：
10.1007/s004530010062
复制
发表时间：
2001
期刊：
影响因子：
1.1
通讯作者：
P. Dumas
中科院分区：
文献类型：
--
作者：
M. Atallah;F. Chyzak;P. Dumas
抽象的。我们给出了一个在确定时间O（Nlog M）内估计长度为N的文本串与长度为M的模式串之间匹配的得分向量的随机算法，即，当图案沿着文本滑动时获得的矢量，并且对每个位置的匹配数量进行计数。一个直接的应用是近似字符串匹配。随机化算法使用卷积来找到分数的估计值;对于接近M的分数，估计值的方差特别小，即，文本中模式的近似出现。没有对输入的概率特性或字母表的大小进行假设。该解决方案扩展到与类，类补充，“永远不匹配”和“总是匹配”符号，加权情况和更高的维度的字符串匹配。
Abstract. We give a randomized algorithm in deterministic time O(Nlog M) for estimating the score vector of matches between a text string of length N and a pattern string of length M , i.e., the vector obtained when the pattern is slid along the text, and the number of matches is counted for each position. A direct application is approximate string matching. The randomized algorithm uses convolution to find an estimator of the scores; the variance of the estimator is particularly small for scores that are close to M , i.e., for approximate occurrences of the pattern in the text. No assumption is made about the probabilistic characteristics of the input, or about the size of the alphabet. The solution extends to string matching with classes, class complements, ``never match'' and ``always match'' symbols, to the weighted case and to higher dimensions.