Class: InciScore::Levenshtein

Inherits:
Object
  • Object
show all
Defined in:
lib/inci_score/levenshtein.rb

Instance Method Summary collapse

Constructor Details

#initialize(s, t) ⇒ Levenshtein

Returns a new instance of Levenshtein.



13
14
15
16
 
# File 'lib/inci_score/levenshtein.rb', line 13

def initialize(s, t)
  @s = s.downcase.unpack("U*")
  @t = t.downcase.unpack("U*")
end

Instance Method Details

#call ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# 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