ruby - 单独统计Levenshtein距离算法中的删除次数

Question

所以我知道 Levenshtein Distance 算法考虑了将字符串 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 的总编辑中涉及的删除次数。

Answer 1

我们可以通过使表的每个条目成为一个由两个数量组成的列表，使删除计数与替换次数一起发生变化。 (作为副作用，次要优化目标是最小化删除次数。我不知道这是否可取。)

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