文字列検索アルゴリズムのAho Corasick法をRubyで適当に実装してみる - grafi-note

Ruby, AlgorithmAho Corasick法は、複数の文字列を高速に検索するアルゴリズムです。簡単に言えばwikipedia:クヌース-モリス-プラット法とwikipedia:トライ木を合わせたようなアルゴリズムで、KMP法ではマッチに失敗した時の位置を表の形で保持しますが、AhoCorasick法ではこれを「failure link」としてトライ木の上に構築します。なお、この木を利用したこのアルゴリズムは決定性有限オートマトンとして機能します。failure linkの指す先は、マッチに失敗した文字列の、先頭の一文字を削った時にマッチする位置に相当します。先頭の一文字を削ってもマッチする位置が無いなら二文字、三文字、と削っていった位置に相当し、何文字削ってもマッチしない場合はルートを指すことになります。検索する際はトライ木同様にルートから一文字ずつノードを辿っていくのですが、