メモ書き: Rubyでレーベンシュタイン距離を求めるプログラム

def levenshtein_distance(str1, str2)
    matrix = Array.new(str1.length + 1).map{Array.new(str2.length + 1)}
    (0..str1.length).each do |i1|
        matrix[i1][0] = i1
    end

    (0..str2.length).each do |i2|
        matrix[0][i2] = i2
    end
    (1..str1.length).each do |i1|
        (1..str2.length).each do |i2|
            cost = str1[i1 - 1] == str2[i2 - 1] ? 0 : 1
            matrix[i1][i2] = [
                matrix[i1 - 1][i2] + 1,
                matrix[i1][i2 - 1] + 1,
                matrix[i1- 1][i2-1] + cost
            ].min
        end
    end
    matrix[str1.length][str2.length]
end

p levenshtein_distance("abc", "abc")
p levenshtein_distance("abc", "abcd")
p levenshtein_distance("abd", "abcd")

=> 0
=> 1
=> 1