Edited at

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

More than 1 year has passed since last update.


説明

未記入


コード


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



ruby

p levenshtein_distance("abc", "abc")

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

=> 0
=> 1
=> 1