Aho Corasick法は、複数の文字列を高速に検索するアルゴリズムです。簡単に言えば クヌース-モリス-プラット法(Wikipedia) と トライ木(Wikipedia) を合わせたようなアルゴリズムで、KMP法ではマッチに失敗した時の位置を表の形で保持しますが、AhoCorasick法ではこれを「failure link」としてトライ木の上に構築します。なお、この木を利用したこのアルゴリズムは決定性有限オートマトンとして機能します。
failure linkの指す先は、マッチに失敗した文字列の、先頭の一文字を削った時にマッチする位置に相当します。先頭の一文字を削ってもマッチする位置が無いなら二文字、三文字、と削っていった位置に相当し、何文字削ってもマッチしない場合はルートを指すことになります。検索する際はトライ木同様にルートから一文字ずつノードを辿っていくのですが、辿るノードが無い場合は、failure linkを辿った先のノードに対して同じことを再帰的に行います。辿るべきノードが無い場合はルートを辿ることとなります。failure linkを用いて次のマッチ可能な位置を辿ることにより、バックトラックを抑止して高速な検索が可能になります。
AhoCrasick木の構築方法は、まずトライ木を普通に構築し、ルート直下のノードのfailure linkはルートを指すようにします。次に幅優先探索の順で、各ノードのfailure linkを、自ノードの親のfailure linkの指すノードに対して、上記の方法で自ノードが表す文字列を辿ったノードとします。つまり、文字列から最後の一文字を削り、さらに最初の何文字かを削った位置までノードを辿り、そこで最後の一文字をまた足した位置に、failure linkをセットします。なお、この方法では動的な検索文字列の追加には対応出来ません。
さて、Rubyによるコードを以下に示します。Rubyならではの簡潔な記述ですが、本質的に言語に依存する部分は無いので用意に他の言語でも実装出来ると思いす。なお、この実装では、ルートノードのfailure link,親はnilに設定しているので、他の言語で実装する時は、適宜ダミーのノードを指すようにするなりルート自身を指すようにするなりして下さい。
class AhoCorasickTree
def initialize(*strs)
@root = Node.new(nil)
@currentnode = @root
strs.each{|str|insert str}
reflesh
end
def reflesh
queue = Array.new
# BFS to first depth
@root.each do |c1,n1|
n1.failure = @root
n1.each{|c2,n2|queue.push [c2,n2]}
end
# BFS
while !queue.empty? do
char, node = queue.shift
node.each{|c,n|queue.push [c,n]}
node.failure = node.parent.failure.find char
node.matches.concat node.failure.matches
end
end
def insert(str)
node = @root
str.each_char do |c|
node = node.get(c) || node.insert(c)
end
node.matches.concat [str]
end
def apply(char)
(@currentnode = @currentnode.find char).matches
end
class Node
def initialize(parent)
@children = Hash.new
@parent = parent
@failure = nil
@matches = Array.new
end
attr_accessor :failure, :matches;
attr_reader :parent;
def insert(char)
@children[char.to_sym] = Node.new(self)
end
def each(&block)
if block
@children.each &block
else
Enumrator.new(self)
end
end
def get(char)
@children[char.to_sym]
end
def find(char)
@children[char.to_sym] || (failure ? failure.find(char) : self)
end
end
end
使用方法は以下のようになります。なお、termをunionした正規表現で検索する方が高速なので、何の役にも立ちません。
require 'aho_corasick'
terms = %w!hoge fuga piyo foo bar!
tree = AhoCorasickTree.new(*terms)
str = ARGF.read
str.each_char do |char|
matches = tree.apply char
puts matches unless matches.empty?
end