Class: InciScore::Levenshtein

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(s, t) ⇒ Levenshtein

Returns a new instance of Levenshtein.



17
18
19
20
 
# File 'lib/inci_score/levenshtein.rb', line 17

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

Instance Attribute Details

#s ⇒ Object (readonly)

Returns the value of attribute s.



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

def s
  @s
end

#t ⇒ Object (readonly)

Returns the value of attribute t.



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

def t
  @t
end

Instance Method Details

#call ⇒ Object 



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/inci_score/levenshtein.rb', line 22

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