Class: Levenstein

Inherits:
Object
  • Object
show all
Defined in:
lib/citizen_code_scripts/levenstein.rb

Class Method Summary collapse

Class Method Details

.closest_match(needle, haystack) ⇒ Object 



26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/citizen_code_scripts/levenstein.rb', line 26

def self.closest_match(needle, haystack)
  min_distance = haystack.map(&:size).max
  results = nil
  haystack.each do |value|
    distance = edit_distance(needle, value)
    if distance < min_distance
      min_distance = distance
      results = [value]
    elsif distance == min_distance
      results << value
    end
  end
  results
end

.edit_distance(s, t) ⇒ Object 



2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
# File 'lib/citizen_code_scripts/levenstein.rb', line 2

def self.edit_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