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

Question

我能用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

- Caio Tarifa

---

你是指差异吗？ - nzifnab

搜索“levenshtein distance ruby”，并查看Levenshtein-distance。 （虽然我不太确定为什么最后一个调用应该返回5; 编辑距离由输入长度限制。） - user2246674

@nzifnab 嗯，我需要一个整数返回。 - Caio Tarifa

请查看“什么是衡量两个字符串相似度的有效方法？（Levenshtein距离使堆栈太深）” - the Tin Man

Answer 1

由于原生的C绑定，更加容易且快速：

gem install levenshtein-ffi
gem install levenshtein

require 'levenshtein'

Levenshtein.normalized_distance string1, string2, threshold

http://rubygems.org/gems/levenshtein http://rubydoc.info/gems/levenshtein/0.2.2/frames

- Michael Franzl

---

请注意，这不能处理Unicode（截至撰写本文的时候，levensthein-ffi宝石无法处理Unicode）。 - whistler

Answer 2

我为您找到了这个：

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

这篇文章介绍了 Levenshtein 距离的 Ruby 代码实现。Levenshtein 距离是计算两个字符串之间的编辑距离的一种度量方法。在此算法中，有三种操作：插入、删除和替换。

- Hugo Demiglio

Answer 3

Rubygems中有一个实际上应该是公共的实用方法，但它并不是，无论如何：

有一个在Rubygems中的实用方法，实际上应该是公开的，但并没有。无论如何：

require "rubygems/text"
ld = Class.new.extend(Gem::Text).method(:levenshtein_distance)

p ld.call("asd", "sdf") => 2

- Nakilon

---

如果你在代码中加入include Gem::Text，就可以说这个模块已经是公开的了。然后你就可以这样使用它：levenshtein_distance('asd', 'sdf')。 - Jerome Dalbert

Gem::Text 的文档在这里：https://ruby-doc.org/stdlib/libdoc/rubygems/rdoc/Gem/Text.html。@JeromeDalbert 提出的 include 方法对于大多数用途来说最方便，而 @Nakilon 的答案则是最完整的，因为它避免了任何可能的命名空间冲突。 - Masa Sakano

Answer 4

Ruby 2.3 及以后版本附带了 did_you_mean gem，其中包括 DidYouMean::Levenshtein.distance。适用于大多数情况并默认可用。

DidYouMean::Levenshtein.distance("Test", "est") # => 1

- pfac

Answer 5

有时候，我是一个炫耀自己Ruby技能的人...

# Levenshtein distance, translated from wikipedia pseudocode by ross

def lev s, t
  return t.size if s.empty?
  return s.size if t.empty?
  return [ (lev s.chop, t) + 1,
           (lev s, t.chop) + 1,
           (lev s.chop, t.chop) + (s[-1, 1] == t[-1, 1] ? 0 : 1)
       ].min
end

- DigitalRoss

---

这可能会比较慢，但如果你想要将代码适应于计算Levenshtein距离的其他内容（比如单词列表），那么这是一个很好的起点。 - Daniel Wolf

require 'levenshtein' 的答案也适用于单词数组，事实上适用于任何理解 :hash 和 :eql? 的东西的数组。 - Camille Goudeseune

这个答案最像 Ruby 风格。递归和 chop 赢了！ - Camille Goudeseune

这是一个很酷的小演示，但不适用于生产。请尝试lev“123456789123456789”，“123456789”... - dawg

我用这个来比较两个字符串，一个有17个字符，另一个有21个字符。它运行了5分钟，然后我取消了它。被接受的答案立即返回。 - Matt

Answer 6

我创建了一个Damerau-Levenshtein宝石，其中算法采用C语言实现。

require "damerau-levenshtein"
dl = DamerauLevenshtein
dl.distance("Something", "Smoething") #returns 1

- dimus

Answer 7

我喜欢DigitalRoss上面的解决方案。但是，正如dawg所指出的那样，它的运行时间以O(3^n)的顺序增长，对于较长的字符串来说不太好。可以使用备忘录或“动态规划”来显著加快该解决方案：

def lev(string1, string2, memo={})
  return memo[[string1, string2]] if memo[[string1, string2]]
  return string2.size if string1.empty?
  return string1.size if string2.empty?
  min = [ lev(string1.chop, string2, memo) + 1,
          lev(string1, string2.chop, memo) + 1,
          lev(string1.chop, string2.chop, memo) + (string1[-1] == string2[-1] ? 0 : 1)
       ].min
  memo[[string1, string2]] = min
  min
end

然后我们拥有更好的运行时间（我认为它几乎是线性的？我不太确定）。

[9] pry(main)> require 'benchmark'
=> true
[10] pry(main)> @memo = {}
=> {}
[11] pry(main)> Benchmark.realtime{puts lev("Hello darkness my old friend", "I've come to talk with you again")}
26
=> 0.007071999832987785

- Hula_Zell