class InciScore::Levenshtein
Public Class Methods
new(s, t)
click to toggle source
# File lib/inci_score/levenshtein.rb, line 13 def initialize(s, t) @s = s.downcase.unpack("U*") @t = t.downcase.unpack("U*") end
Public Instance Methods
call()
click to toggle source
# File lib/inci_score/levenshtein.rb, line 18 def call n, m = @s.length, @t.length return 0 if @s == @t return m if n.zero? return n if m.zero? d = Array.new(m+1) { |i| i } x = nil n.times do |i| e = i + 1 m.times do |j| c = @s[i] == @t[j] ? 0 : 1 ins = d[j + 1] + 1 del = e + 1 sub = d[j] + c x = ins < del ? ins : del x = sub if sub < x d[j] = e e = x end d[m] = x end x end