Class: Matchers::ACAutomaton

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

Overview

An AC automaton. Based on www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf.

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(patterns) ⇒ ACAutomaton

Returns a new instance of ACAutomaton.



143
144
145
146
147
 
# File 'lib/matcher.rb', line 143

def initialize(patterns)
  @nodes = []
  @patterns = patterns || []
  build(@patterns)
end

Instance Attribute Details

#nodes ⇒ Object (readonly)

Nodes are managed in an array. The indices are



141
142
143
 
# File 'lib/matcher.rb', line 141

def nodes
  @nodes
end

#patterns ⇒ Object (readonly)

Nodes are managed in an array. The indices are



141
142
143
 
# File 'lib/matcher.rb', line 141

def patterns
  @patterns
end

Instance Method Details

#build(patterns) ⇒ Object 



158
159
160
161
 
# File 'lib/matcher.rb', line 158

def build(patterns)
  build_goto(patterns)
  build_failure
end

#build_failure ⇒ Object 



182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
 
# File 'lib/matcher.rb', line 182

def build_failure
  queue = [0]
  until queue.empty?
    n = queue.shift
    node = @nodes[n]
    @nodes[n].goto.each do |c, next_node|
      queue.push(next_node)

      next if n.zero?

      failure = node.failure
      failure = @nodes[failure].failure while @nodes[failure].g(c).nil?
      @nodes[next_node].failure = @nodes[failure].g(c)
      @nodes[next_node].out.concat(@nodes[@nodes[next_node].failure].out)
    end
  end
end

#build_goto(patterns) ⇒ Object 



163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
# File 'lib/matcher.rb', line 163

def build_goto(patterns)
  root = new_node
  patterns.each_with_index do |pattern, i|
    q = root
    pattern.chars.each do |char|
      next_q = @nodes[q].goto[char]
      if next_q
        q = next_q
      else
        new_q = new_node
        @nodes[q].goto[char] = new_q
        q = new_q
      end
    end

    @nodes[q].out.push(i)
  end
end

#find(text) ⇒ Object 



200
201
202
203
204
205
206
 
# File 'lib/matcher.rb', line 200

def find(text)
  return [] if text.nil? || text == ''

  find_id(text).map do |id|
    @patterns[id]
  end
end

#find_id(text) ⇒ Object

Finds and retuns matched pattens’ indices.



209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/matcher.rb', line 209

def find_id(text)
  return [] if text.nil? || text == ''

  q = 0
  result = []
  text.chars.each_with_index do |c, _i|
    loop do
      node = @nodes[q]
      if (to_go_next = node.goto[c])
        q = to_go_next
        break
      end
      break if q.zero?

      q = node.failure
    end

    out = @nodes[q].out
    result.concat(out) unless out.empty?
  end

  result
end

#matches?(text) ⇒ Boolean

Returns true if the text matches any pattern, otherwise false.

Returns:

  • (Boolean) 


234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
 
# File 'lib/matcher.rb', line 234

def matches?(text)
  return false if text.nil?

  q = 0
  text.chars.each do |c|
    loop do
      node = @nodes[q]
      if (to_go_next = node.goto[c])
        q = to_go_next
        break
      end
      break if q.zero?

      q = node.failure
    end

    out = @nodes[q].out

    return true unless out.empty?
  end

  false
end

#new_node ⇒ Object

Creates a new node and returns the id. This method is not thread safe.



151
152
153
154
155
156
 
# File 'lib/matcher.rb', line 151

def new_node
  id = @nodes.size
  node = Node.new(id: id)
  @nodes.push(node)
  id
end