Class: Matchers::Trie

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(patterns) ⇒ Trie

Returns a new instance of Trie.



23
24
25
26
27
28
29
30
 
# File 'lib/aho_corasick.rb', line 23

def initialize(patterns)
  @root = Node.new
  @root.children.default = @root
  patterns.each do |pattern|
    insert(pattern)
  end
  build
end

Instance Attribute Details

#root ⇒ Object (readonly)

Returns the value of attribute root.



22
23
24
 
# File 'lib/aho_corasick.rb', line 22

def root
  @root
end

Instance Method Details

#build ⇒ Object 



49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/aho_corasick.rb', line 49

def build
  # Update failure on each node.
  # Search longest matching suffix (which becomes failure) by BFS. In case no matching suffix, root becomes failure.
  q = new_queue
  until q.empty?
    cur_node = q.pop
    cur_node.children.each do |char, child|
      q.push(child)
      detect_node = cur_node.failure || @root
      while detect_node.children[char].nil?
        detect_node = detect_node.failure
      end
      child.failure = detect_node.children[char]
    end
  end
end

#insert(pattern = '') ⇒ Object 



32
33
34
35
36
37
38
 
# File 'lib/aho_corasick.rb', line 32

def insert(pattern = '')
  current_node = @root
  pattern.split('').each_with_index do |char, i|
    current_node = current_node.insert(char)
    current_node.output = pattern if i == pattern.length - 1
  end
end

#new_queue ⇒ Object 



40
41
42
43
44
45
46
47
 
# File 'lib/aho_corasick.rb', line 40

def new_queue
  q = Queue.new
  @root.children.values.each do |child|
    q.push(child)
    child.failure = @root # set root on root's children's failure
  end
  q
end