两个字符串之间如何高效地测量相似度？（Levenshtein距离会使堆栈太深）

Question

两个字符串之间如何高效地测量相似度？（Levenshtein距离会使堆栈太深）

ruby-on-railsstringcomparesimilaritylevenshtein-distance

3

因为我的字符串可以长达10,000个字符，所以我开始使用以下链接中的方法：http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Ruby，对于非常小的字符串效果很好。但是，由于Levenshtein距离是递归的，这会导致我的Ruby on Rails应用程序出现堆栈过深的错误。

有没有另一种更少使用堆栈的方法来找到两个大字符串之间的相似性呢？

或者，我需要一种方法来使堆栈具有更大的大小。（虽然我认为这不是解决问题的正确方式）

- NullVoxPopuli

2

在您提供的页面上，有许多实现。其中大多数都不是递归的，并且使用了少量的固定堆栈空间。只需移植其中一个即可。 - rob mayoff

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bobbymcr · Accepted Answer

考虑使用非递归版本以避免过度的调用栈开销。Seth Schroeder 提供了一个基于多维数组的迭代实现 Ruby 代码，似乎与 Levenshtein 距离的动态规划方法有关（如维基百科文章中所述的伪代码）。以下是 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