ruby-on-rails - 什么是衡量两个字符串之间相似性的有效方法？ (Levenshtein Distance 使堆栈太深)

Question

所以，我从这个开始:http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Ruby

这对非常小的字符串非常有用。但是，我的字符串的长度可能超过 10,000 个字符——并且由于 Levenshtein 距离是递归的，这会导致我的 Ruby on Rails 应用出现堆栈太深的错误。

那么，是否有另一种堆栈密集程度较低的方法来查找两个大字符串之间的相似性？

或者，我需要一种使堆栈具有更大尺寸的方法。 (虽然我认为这不是解决问题的正确方法)

Answer 1

考虑使用非递归版本来避免过多的调用堆栈开销。 Seth Schroeder有一个 iterative implementation in Ruby它改用多维数组；它似乎与 Levenshtein 距离的动态规划方法有关(如 pseudocode for the Wikipedia article 中所述)。 Seth 的 ruby​​ 代码转载如下:

def levenshtein(s1, s2)
  d = {}
  (0..s1.size).each do |row|
    d[[row, 0]] = row
  end
  (0..s2.size).each do |col|
    d[[0, col]] = col
    end
  (1..s1.size).each do |i|
    (1..s2.size).each do |j|
      cost = 0
      if (s1[i-1] != s2[j-1])
        cost = 1
      end
      d[[i, j]] = [d[[i - 1, j]] + 1,
                   d[[i, j - 1]] + 1,
                   d[[i - 1, j - 1]] + cost
                  ].min
      next unless @@damerau
      if (i > 1 and j > 1 and s1[i-1] == s2[j-2] and s1[i-2] == s2[j-1])
        d[[i, j]] = [d[[i,j]],
                     d[[i-2, j-2]] + cost
                    ].min
      end
    end
  end
  return d[[s1.size, s2.size]]
end