用Ruby测量两个字符串之间的距离？

发布时间：2020-12-16 20:28:33 所属栏目：百科来源：网络整理

导读：我可以用Ruby测量两个字符串之间的距离吗？即： compare('Test','est') # Returns 1compare('Test','Tes') # Returns 1compare('Test','Tast') # Returns 1compare('Test','Taste') # Returns 2compare('Test','tazT') # Returns 5 解决方法我找到了你： d

我可以用Ruby测量两个字符串之间的距离吗？

即：

compare('Test','est') # Returns 1
compare('Test','Tes') # Returns 1
compare('Test','Tast') # Returns 1
compare('Test','Taste') # Returns 2
compare('Test','tazT') # Returns 5

解决方法

我找到了你：

def levenshtein_distance(s,t)
  m = s.length
  n = t.length
  return m if n == 0
  return n if m == 0
  d = Array.new(m+1) {Array.new(n+1)}

  (0..m).each {|i| d[i][0] = i}
  (0..n).each {|j| d[0][j] = j}
  (1..n).each do |j|
    (1..m).each do |i|
      d[i][j] = if s[i-1] == t[j-1]  # adjust index into string
                  d[i-1][j-1]       # no operation required
                else
                  [ d[i-1][j]+1,# deletion
                    d[i][j-1]+1,# insertion
                    d[i-1][j-1]+1,# substitution
                  ].min
                end
    end
  end
  d[m][n]
end

[ ['fire','water'],['amazing','horse'],["bamerindos","giromba"] ].each do |s,t|
  puts "levenshtein_distance('#{s}','#{t}') = #{levenshtein_distance(s,t)}"
end

这是令人敬畏的输出：=)

levenshtein_distance('fire','water') = 4
levenshtein_distance('amazing','horse') = 7
levenshtein_distance('bamerindos','giromba') = 9

资料来源：http://rosettacode.org/wiki/Levenshtein_distance#Ruby

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!