読者です 読者をやめる 読者になる 読者になる

AhoCorasickを実装してみたんだす

AhoCorasick Python python

今更ながら「大規模サービス技術者入門」を読み返したんだす。

AhoCorasickのこと今までアホコラシックて読んでたけど、
正しくはエイホコラシック(Wikipedia調べ)だそうなんだす。

ソースコード -> pyahocorasick

failure linkを作るところを理解するのに時間がかかった。
トライ木を構築した後、根から順繰りに次ぎのノードを見てって、最長接尾辞を決定するところ。
再帰でつくってみた。

最終的にこんな感じでテスト。

参考

Aho Corasick 法 - naoyaのはてなダイアリ