class RBAhoCorasick::NFA

Attributes

initial_state[R]
states_by_state_id[R]

Public Class Methods

new() click to toggle source
# File lib/rbahocorasick/nfa.rb, line 10
def initialize
  @least_unused_state_id = 0
  @states_by_state_id = []
  @initial_state = create_state
end

Public Instance Methods

add(key, value = nil) click to toggle source

Add a pair of key and value

# File lib/rbahocorasick/nfa.rb, line 17
def add(key, value = nil)
  @finalized and raise 'finalized'
  state = @initial_state
  key.each_byte do |byte|
    next_state = state[byte]
    unless next_state
      next_state = state[byte] = create_state
    end
    state = next_state
  end
  state.add(key, value)
end
finalize() click to toggle source

Finalize the state machine

# File lib/rbahocorasick/nfa.rb, line 31
def finalize
  @finalized and raise 'finalize twice'
  @finalized = true
  queue = []
  (0..255).each do |byte|
    if @initial_state[byte]
      next_state = @initial_state[byte]
      next_state.default = @initial_state
      queue << next_state
    else
      @initial_state[byte] = @initial_state
    end
  end

  while queue.length > 0
    r = queue.shift
    (0..255).each do |byte|
      if s = r[byte]
        queue << s
        state = r.default
        state = state.default until state[byte]
        s.default = state[byte]
        s.data.concat(s.default.data)
      end
    end
  end
end
match(data, length = nil) { |match_data| ... } click to toggle source

Match the data

# File lib/rbahocorasick/nfa.rb, line 60
def match(data, length = nil)
  finalize unless @finalized
  length ||= data.length
  matches = [] unless block_given?
  offset = 0
  state = @initial_state
  data.each_byte do |byte|
    break if offset >= length
    offset += 1
    state = state.default until state[byte]
    state = state[byte]
    if state.data.length > 0
      state.data.each do |state_data|
        match_data = RBAhoCorasick::MatchData.new(state_data.key,
          state_data.value, offset - state_data.key.length)
        if block_given?
          yield match_data
        else
          matches << match_data
        end
      end
    end
  end
  return matches unless block_given?
end

Private Instance Methods

create_state() click to toggle source
# File lib/rbahocorasick/nfa.rb, line 88
def create_state
  state = RBAhoCorasick::State.new(@least_unused_state_id)
  @least_unused_state_id += 1
  @states_by_state_id[state.state_id] = state
  state
end