Class: Komainu::Levenshtein

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

Instance Method Summary collapse

Constructor Details

#initialize(words) ⇒ Levenshtein

Returns a new instance of Levenshtein.



5
6
7
8
9
10
 
# File 'lib/komainu/levenshtein.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/levenshtein.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/levenshtein.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