Sha256: 0cd76f1fbcf1b901c96b8e7d1233e29307f2504574c1d1c7d68e4b76bec5818a
Contents?: true
Size: 1.74 KB
Versions: 11
Compression:
Stored size: 1.74 KB
Contents
module Vladlev
class Levenshtein
def self.distance(str1, str2, maximum_allowable_distance = 9999)
shortest_string = (str1.size > str2.size) ? str1 : str2
longest_string = (str1.size > str2.size) ? str2 : str1
broke_max = false
if longest_string == shortest_string
return 0
elsif longest_string.size - shortest_string.size > maximum_allowable_distance
return shortest_string.size
elsif longest_string.size == 0 || shortest_string.size == 0
return shortest_string.size
end
calculation_grid = Array.new(longest_string.size)
working_grid = Array.new(longest_string.size)
longest_string.size.times { |position| calculation_grid[position] = position }
(1...shortest_string.size).each do |i|
row_minimum = working_grid[0] = calculation_grid[0] + 1
(1...longest_string.size).each do |j|
cost = (longest_string[j - 1] == shortest_string[i - 1]) ? 0 : 1
working_grid[j] = [calculation_grid[j] + 1, working_grid[j - 1] + 1, calculation_grid[j - 1] + cost].min
row_minimum = (working_grid[j] < row_minimum) ? working_grid[j] : row_minimum
end
if row_minimum > maximum_allowable_distance
broke_max = true
break
end
temp_grid = working_grid
working_grid = calculation_grid
calculation_grid = temp_grid
end
return broke_max ? shortest_string.size : calculation_grid[longest_string.size - 1]
end
def self.normalized_distance(str1, str2, maximum_allowable_distance = 9999)
longest_string_length = (str1 > str2) ? str1.length : str2.length
return 0 if longest_string_length == 0
distance / longest_string_length
end
end
end
Version data entries
11 entries across 11 versions & 1 rubygems