1

したがって、レーベンシュタイン距離アルゴリズムでは、文字列 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

次にカウントを増やします。しかし、これはうまくいかないようです。また、2 つの文字列のサイズの違いを取得しようとしましたが、次の場合は失敗します

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

ここには明らかに 1 つの削除がありますが、サイズの違いを取得するだけでは検出されません。

文字列 A を文字列 B に変更するための合計編集に含まれる削除の数を追跡する方法を誰かが知っているかどうか疑問に思っていました.

4

1 に答える 1

3

テーブルの各エントリを 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
于 2014-10-10T19:14:53.387 に答える