0

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

4

2 回答 2

2

你读过http://www.merriampark.com/ld.htm吗？

您正在计算将一个字符串转换为另一个字符串所需的转换成本——插入和删除的数量。

这种转换的“成本”表示两个字符串之间的距离。

交易所呢？这就是Damerau-Levenshtein算法，它是不同的。包括交换并没有太大改善。

本质是在两个单词之间创建一个矩阵，并逐列计算每个单词的每个字母到另一个单词的每个字母的“距离”。该矩阵的右下角是考虑到所有字母的总距离。

问题1）

“上方”的单元格反映了更改的历史，并且该行的字符（通常）与此不同，因此该单元格相对于它是一个删除。

“左侧”单元格反映了更改的历史，并且该列的字符（通常）与此不同，因此该单元格是相对于它的插入。

这通常是错误的唯一一次是具有三个字母序列的单词。少见的英文。

行列比较的成本为 0 或 1。

“历史加一变更”与变更的实际成本的最小值为适用成本。

问题2）

变量i和j不是任何东西的长度。它们是比较矩阵中的位置。“插入”和“删除”是将一个单词转换为另一个单词所需的动作。插入/删除动作的计数是单词之间的距离。

于 2009-05-13T10:03:43.563 回答
1

1）这些行计算删除情况下的距离，插入情况下的距离，以及在替换情况下使用“成本”的距离......

删除和插入在距离计算中有效地算作“1”，因此是 +1。

我们可以相信只有当字符不同时才会有替换，因此如果两个字符相等，则“成本 = 0”......

新的距离就是这 3 个假设之间的最小距离，所以你并不总是加 1 ...

2）如果我计算“FooBar”和“FoBaWhatever”之间的距离，即使第二个字符串比第一个字符串长，我也会删除一些字符......

当然，如果第二个字符串比第二个字符串短（ FooBar -> FoBa ）我会发现一些删除但无法提前知道它们在哪里......

于 2009-05-13T09:58:36.377 回答