RubyでAC法を用いた文字列探索を行うサンプル

普通、Rubyで文字列探索といえば正規表現だと思うのですが、若干特殊なケースに遭遇した際の解決方法としてAho-Corasick法というアルゴリズムを用いた探索というのを使ったので、経緯とかちょっとまとめてみます。

前提知識的なもの（読み飛ばしてもok)

準備

当初自分でAC法のアルゴリズムを実装しようと思ってやってみたんですけど、普通にしんどかったのでライブラリ使いました。先人の皆様の努力に感謝致します。

$ gem install aho_corasick_matcher

参考: https://github.com/altmetric/aho_corasick_matcher

どんなケースに有用か

サンプルコードを見てもらったほうが早い。

ac_sample.rb

require 'aho_corasick_matcher'

# 正規表現のunionだとorでの探索になるので最長は返ってこない
reg = Regexp.union(/cheese/,/burger/,/cheeseburger/)
p 'cheeseburger'.scan(reg)

# AC法を用いると全部返ってくる
matcher = AhoCorasickMatcher.new(['cheese', 'burger', 'cheeseburger'])
p matcher.match('cheeseburger')

実行結果

["cheese", "burger"]
["cheese", "cheeseburger", "burger"]

余談

調べてみるとAC法は高速！みたいな記事がよくでてきますが、少なくともRubyでは正規表現のほうが早いです（やってることが違うから当前）。上記のような特殊なケースだったり、登場する回数をお手軽に調べたいとかっていう時にはこのライブラリを使うほうがラクだなと思います。

さらに余談

goでも作ってる方がいますね
https://github.com/cloudflare/ahocorasick