Отдельно подсчитывает количество удалений в алгоритме расстояния Левенштейна

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 делеция здесь, но просто получать разницу в размерах не обнаружит так.

мне было интересно, если кто-нибудь знает, как отслеживать количество удалений, которые были вовлечены в общих правках для изменения строки А в строке 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