ruby中的levenshtein_distance

我写了如下levenshtein_distance来计算两个字符串之间的距离：

  def min3(a, b, c) if a < b && a < c then a elsif b < c then b else c end end def levenshtein_distance(s, t) m = s.length n = t.length return m if n.zero? return n if m.zero? d = (0..m+1).to_a x = nil s.each_char.each_with_index do |ch1, i| e = i + 1 t.each_char.each_with_index do |ch2, j| cost = ch1 == ch2 ? 0 : 1 x = min3(d[j + 1] + 1, e + 1, d[j] + cost) d[j] = e e = x end d[m] = x end x end 

当两个字符串不同时，它会给出一条错误消息：

 NoMethodError - undefined method `+' for nil:NilClass 

错误检测到行：

 x = min3(d[j + 1] + 1, e + 1, d[j] + cost) 

我认为这是由于指数超过了定义的d的限制。 但是扩大d的长度并不能解决这个问题。

在实现算法时我是否遗漏了一些东西？

这是我在irb测试的情况

 irb(main):052:0> levenshtein_distance("a", "abc") NoMethodError: undefined method `+' for nil:NilClass from (irb):24:in `block (2 levels) in levenshtein_distance' from (irb):22:in `each_char' from (irb):22:in `each_with_index' from (irb):22:in `block in levenshtein_distance' from (irb):20:in `each_char' from (irb):20:in `each_with_index' from (irb):20:in `levenshtein_distance' from (irb):52 from /usr/bin/irb:12:in `' 

Answer 1

我根据维基百科改写了算法：

 def ld(s, t) v0 = (0..t.length).to_a v1 = [] #p v0 s.chars.each_with_index do |s_ch, i| v1[0] = i + 1 t.chars.each_with_index do |t_ch, j| cost = s_ch == t_ch ? 0 : 1 v1[j + 1] = [v1[j] + 1, v0[j + 1] + 1, v0[j] + cost].min end v0 = v1.dup #p v1 end v0[t.length] end 

它似乎工作。 此外，您还可以取消注释p v1和p v0以查看向量在每次迭代时的变化情况。