Levenshtein 거리 알고리즘에서 삭제 횟수를 개별적으로 계산

Question

Levenshtein Distance 알고리즘은 String A를 String 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" 

실패합니다.

사람이

Answer 1

우리는 대체의 번호와 함께 삭제 카운트를 타고을 할 수 문자열 B.으로 변경 문자열 A의 총 편집에 참여했다 삭제의 수를 추적하는 방법을 알고 있다면 궁금 해서요 표의 각 항목을 두 개의 양으로 구성된 목록으로 만드십시오. (부작용으로, 삭제의 횟수를 최소화하는 것이 2 차적인 최적화 목표입니다.이 것이 바람직한 지 아닌지는 잘 모르겠습니다.)

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