1)为什么要在这些行上加1?

    d[i-1, j] + 1, // deletion
    d[i, j-1] + 1, // insertion

线路
if s[i] = t[j] then cost := 0

        else cost := 1

应该考虑删除/较低的字长,还是我遗漏了什么?
2)同时,注释状态为删除和插入。我认为它检查两个单词中删除的字符(整数j/i表示单词的长度)是对的吗,因为较低的值将表示删除的字符。
使用的代码在此处(因为它是伪代码,而且我没有特定于语言的问题,所以此线程不在任何语言类别中):
http://www.iterasi.net/openviewer.aspx?sqrlitid=z0cloj7xhk-ce0f72v4cjq

最佳答案

1)这些行计算删除时的距离,插入时的距离,以及替换时使用“成本”的距离……
在距离计算中,删除和插入有效地计算为“1”,因此为+1。
我们可以相信,只有当字符不同时才有替换,因此,如果两个字符相等,则“cost=0”。。。
新的距离是这三个假设之间的最小距离,所以你不必总是加1…
2)如果我计算“FooBar”和“FoBaWhatever”之间的距离,即使第二个字符串比第一个字符串长,我也会删除一些字符。。。
当然,如果第二个字符串比第二个短(foobar->foba),我会发现一些删除,但无法提前知道它们在哪里…

关于algorithm - 关于Levenshtein距离的问题,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/857031/

10-11 22:44
查看更多