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

Question

Итак, я знаю, что алгоритм расстояния Левенштейна учитывает минимальное количество удалений, вставок и замен, необходимых для изменения строки 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