Swap and mismatch edit distance
Swap and mismatch edit distance
复制标题
交换和不匹配编辑距离
作者：
A. Amir;E. Eisenberg;E. Porat
没有已知的算法解决具有扩展编辑距离的近似字符串匹配问题的一般情况，其中编辑操作是：插入、删除、不匹配和交换，时间为o（nm），其中n是文本的长度，m是模式的长度。为了研究这个问题，对编辑操作进行了独立分析。结果表明，只进行失配运算的近似匹配问题的求解时间为O（n <$mlogm）.如果唯一允许的编辑操作是交换，那么问题可以在时间O（n logm logσ）内解决，其中σ=min（m，|Σ|).本文证明了以swap和mismatch为编辑操作的近似字符串匹配问题的时间复杂度为O（n <$mlogm）。
There is no known algorithm that solves the general case of theapproximate string matching problem with the extended edit distance, where the edit operations are: insertion, deletion, mismatch and swap, in timeo(nm), wheren is the length of the text andm is the length of the pattern. In an effort to study this problem, the edit operations were analysed independently. It turns out that the approximate matching problem with only the mismatch operation can be solved in timeO(n √m logm). If the only edit operation allowed is swap, then the problem can be solved in timeO(n logm logσ), whereσ=min(m, |Σ|). In this paper we show that theapproximate string matching problem withswap andmismatch as the edit operations, can be computed in timeO(n √m logm).