1

所以我知道 Levenshtein 距离算法考虑了将字符串 A 更改为字符串 B 所需的最小删除、插入和替换次数。但是，我想知道如何单独跟踪总编辑中的删除次数需要进行更改。我在看这个算法的实现，

def levenshtein(first, second)
    first = first.split
    second = second.split
    first_size = first.size
    second_size = second.size
    matrix = [(0..first_size).to_a]
    (1..second_size ).each do |j|
        matrix << [j] + [0] * (first_size)
    end
    count = 0
    (1..second_size).each do |i|
       (1..first_size).each do |j|
         if first[j-1] == second[i-1]
           matrix[i][j] = matrix[i-1][j-1]
         else
           matrix[i][j] = [matrix[i-1][j],matrix[i][j-1], matrix[i-1][j-1]].min + 1
         end
       end
    end
    return matrix.last.last 
end

因此，为了跟踪删除，我尝试了：

if matrix[i-1[j] == [matrix[i-1][j],matrix[i][j-1], matrix[i-1][j-1]].min

然后增加计数。但是，这似乎不起作用。我还尝试获取两个字符串的大小差异，但在以下情况下失败

String 1: "my response to prompt#1"
String 2: "my edited response to"

这里显然有 1 个删除，但仅仅获得大小的差异不会检测到这一点。

我想知道是否有人知道如何跟踪将字符串 A 更改为字符串 B 的总编辑中涉及的删除数量。

4

1 回答 1

3

我们可以通过使表中的每个条目成为由两个数量组成的列表来使删除计数与替换次数一起增加。（作为一个副作用，二次优化的目标是尽量减少删除的数量。我不知道这是否可取。）

def levenshtein(first, second)
    first = first.split
    second = second.split
    first_size = first.size
    second_size = second.size
    matrix = [(0..first_size).to_a]
    (1..second_size ).each do |j|
        matrix << [[j,0]] + [[0,0]] * (first_size)
    end
    count = 0
    (1..second_size).each do |i|
       (1..first_size).each do |j|
         if first[j-1] == second[i-1]
           matrix[i][j] = matrix[i-1][j-1]
         else
           matrix[i][j] = [[matrix[i-1][j  ][0]+1, matrix[i-1][j  ][1]  ],
                           [matrix[i  ][j-1][0]+1, matrix[i  ][j-1][1]+1],
                           [matrix[i-1][j-1][0]+1, matrix[i-1][j-1][1]  ]].min
         end
       end
    end
    return matrix.last.last 
end
于 2014-10-10T19:14:53.387 回答