Zmierz odległość między dwoma strunami za pomocą Ruby?

Question

Czy mogę zmierzyć odległość między dwoma ciągami za pomocą Ruby?

tj .:

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 

Answer 1

znalazłem to dla Ciebie:

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 

To niesamowite wyjście: =)

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

Źródło: http://rosettacode.org/wiki/Levenshtein_distance#Ruby

Answer 2

znacznie prostsze, jestem Ruby show-off czasami ...

# 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 

Answer 3

Znacznie łatwiej i szybko ze względu na rodzimy C oprawa:

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

Answer 4

I utworzono damerau-levenshtein gem, w którym algorytmy są zaimplementowane w C

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

Answer 5

istnieje metoda narzędzie w rubygems które faktycznie powinny być publiczne, ale to nie jest, w każdym razie:

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

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