Class: Komainu::CalculatesLevenshteinDistance
- Inherits:
-
Object
- Object
- Komainu::CalculatesLevenshteinDistance
- Defined in:
- lib/komainu/calculates_levenshtein_distance.rb
Instance Method Summary collapse
-
#initialize(words) ⇒ CalculatesLevenshteinDistance
constructor
A new instance of CalculatesLevenshteinDistance.
- #search(word, maximum_distance) ⇒ Object
- #search_recursive(node, letter, word, previous_row, results, maximum_distance) ⇒ Object
Constructor Details
#initialize(words) ⇒ CalculatesLevenshteinDistance
Returns a new instance of CalculatesLevenshteinDistance.
5 6 7 8 9 10 |
# File 'lib/komainu/calculates_levenshtein_distance.rb', line 5 def initialize(words) @trie = TrieNode.new words.each do |word| @trie.insert(word) end end |
Instance Method Details
#search(word, maximum_distance) ⇒ Object
12 13 14 15 16 17 18 19 |
# File 'lib/komainu/calculates_levenshtein_distance.rb', line 12 def search word, maximum_distance current_row = (0..word.length).to_a results = {} @trie.children.keys.each do |letter| search_recursive(@trie.children[letter], letter, word, current_row, results, maximum_distance) end results end |
#search_recursive(node, letter, word, previous_row, results, maximum_distance) ⇒ Object
21 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/komainu/calculates_levenshtein_distance.rb', line 21 def search_recursive node, letter, word, previous_row, results, maximum_distance columns = word.length + 1 current_row = [previous_row.first + 1] (1...columns).each do |column| insert_cost = current_row[column - 1] + 1 delete_cost = previous_row[column] + 1 if word[column - 1] != letter[0] replace_cost = previous_row[column - 1] + 1 else replace_cost = previous_row[column - 1] end current_row << [insert_cost, delete_cost, replace_cost].min end if current_row.last <= maximum_distance && node.word results[node.word] = current_row.last end if current_row.min <= maximum_distance node.children.keys.each do |letter| search_recursive(node.children[letter], letter, word, current_row, results, maximum_distance) end end end |