寻找所有子字符串的编辑距离算法

Question

寻找所有子字符串的编辑距离算法

stringalgorithmlevenshtein-distancesimilarityedit-distance

16

给定2个字符串s和t，我需要找到每个子字符串与t的编辑距离（Levenshtein距离）。实际上，我需要知道对于s中的每个i位置，从该位置开始的所有子字符串的最小编辑距离是多少。

例如：

t = "ab"    
s = "sdabcb"

我需要得到类似以下的内容:

{2,1,0,2,2}

解释：

1st position:
distance("ab", "sd") = 4 ( 2*subst )
distance("ab", "sda") = 3( 2*delete + insert )
distance("ab", "sdab") = 2 ( 2 * delete)
distance("ab", "sdabc") = 3 ( 3 * delete)
distance("ab", "sdabcb") = 4 ( 4 * delete)
So, minimum is 2

2nd position:
distance("ab", "da") = 2 (delete + insert)
distance("ab", "dab") = 1 (delete)
distance("ab", "dabc") = 2 (2*delete)
....
So, minimum is 1

3th position:
distance("ab", "ab") = 0
...
minimum is 0

等等。

当然，我可以使用暴力算法来解决这个任务。但有更快的算法吗？

感谢您的帮助。

- Ivan Bianko

1

我知道你的答案 {2,1,**0,2**,2} 是错误的，因为相邻数字之间最多只能相差1：如果存在一个子串s[i..j]与t的编辑距离为k，那么子串s[(i+1)..j]可以通过在字符串开头进行第一次编辑操作插入s[i]来匹配t，其代价最多为k+1。在你的例子中，对于第4个位置，distance("ab", "b") = 1（1次插入），对于第5个位置，distance("ab", "cb") = 1（1次替换）。 - j_random_hacker

@Anderson Green 只是为了澄清，你是否仍然寻找（与原始问题相同）从s的每个位置开始的最小编辑距离，还是其他更多的东西？ - kcsquared

@kcsquared，是的，我想找到具有最小编辑距离的子字符串。 - Anderson Green

2个回答

5

瓦格纳-费舍尔算法可以免费得出所有前缀的答案。瓦格纳-费舍尔矩阵的最后一行包含从每个前缀s到t的编辑距离。因此，作为第一步，对于每个i，请运行Wagner-Fischer并选择最后一行中的最小元素。我很想知道是否还有其他人知道（或能找到）更好的方法。请参考http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm。

- Nemo

谢谢，但我指的是这个解决方案是暴力破解...我希望存在更好的解决方案（相关时间复杂度）。 - Ivan Bianko

如果没有示例，我怀疑任何人都不会理解你的答案。 - Elmue

如果您正在参考维基中提到的s和t，则最后一行包含从s到t每个前缀的编辑距离，而不是从s的每个前缀到t的距离。 - mangusta

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Elmue · Accepted Answer

To find substrings in a given string is very easy. You take the normal Levenshtein algorithm and modify it slightly.

FIRST: Instead of filling the first row of the matrix with 0,1,2,3,4,5,... you fill it entirely with zeros. (green rectangle)

SECOND: Then you run the algorithm.

THIRD: Instead of returning the last cell of the last row you search for the smallest value in the last row and return it. (red rectangle)

Example: needle: "aba", haystack: "c abba c" --> result = 1 (converting abba -> aba)

我测试过它，它可以工作。

这比你在问题中逐个字符地遍历字符串的建议要快得多。您只需创建矩阵一次。