Class: StringMetric::Levenshtein::TrieRadixTree

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

Class Method Summary collapse

Class Method Details

.distance(from, node, options = {}) ⇒ Object 



6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
# File 'lib/string_metric/levenshtein/trie_radix_tree.rb', line 6

def self.distance(from, node, options = {})

  @max_distance      = options[:max_distance]      || 0
  @insertion_cost    = options[:insertion_cost]    || 1
  @deletion_cost     = options[:deletion_cost]     || 1
  @substitution_cost = options[:substitution_cost] || 1

  results = {}
  word = from.codepoints
  currentRow = (0..word.length).to_a

  node.children.keys.each do |letter|
    searchRecursive(node.children[letter], letter, word, currentRow, results)
  end

  results
end

.searchRecursive(node, letter, word, previousRow, results) ⇒ Object 



24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/string_metric/levenshtein/trie_radix_tree.rb', line 24

def self.searchRecursive(node, letter, word, previousRow, results)
  columns = word.length + 1
  currentRow = [previousRow[0] + 1]

  (1...columns).each do |column|
    insertCost = currentRow[column - 1] + @insertion_cost
    deleteCost = previousRow[column] + @deletion_cost
    cost = (word[column - 1] == letter) ? 0 : @substitution_cost
    replaceCost = previousRow[column - 1] + cost

    currentRow << [insertCost, deleteCost, replaceCost].min
  end

  if currentRow.last <= @max_distance && !node.word.nil?
    results[node.word] = currentRow.last
  end

  if currentRow.min <= @max_distance
    node.children.keys.each do |letter|
      searchRecursive(node.children[letter], letter, word, currentRow, results)
    end
  end
end