class Levenstein
Public Class Methods
closest_match(needle, haystack)
click to toggle source
# File lib/abtion_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)
click to toggle source
# File lib/abtion_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