An Approximate String-Matching Algorithm
An Approximate String-Matching Algorithm
复制标题
一种近似字符串匹配算法
DOI：
10.1016/0304-3975(92)90138-6
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
J. Shawe
中科院分区：
文献类型：
--
作者：
Jong Yong Kim;J. Shawe
在早期的属性匹配算法的基础上，描述了一种近似的字符串匹配算法。该算法涉及从文本字符串构建一个字典树，对于长度为 N 的文本字符串，这需要花费 O(Nlog2N) 时间。一旦建立了这个数据结构，就可以对长度为 m 的模式字符串进行任意数量的近似搜索。基于背景语言的某些规律性假设，给出了算法查找阶段的预期复杂度分析。每个模式的预期查找时间为 O(mlog2N)。该算法所采用的思想之前已经在实践中被证明是有效的，但之前没有得到任何理论分析。
An approximate string-matching algorithm is described based on earlier attribute-matching algorithms. The algorithm involves building a trie from the text string which takes time O(Nlog2N), for a text string of lengthN. Once this data structure has been built any number of approximate searches can be made for pattern strings of lengthm. The expected complexity analysis is given for the look-up phase of the algorithm based on certain regularity assumptions about the background language. The expected look-up time for each pattern is O(mlog2N). The ideas employed in the algorithm have been shown effective in practice before, but have not previously received any theoretical analysis.