キーワードマッチのアルゴリズム

Trieによるキーワードマッチ

雪助のキーワードマッチのアルゴリズムは、IMEなどでよく使われるTrieというアルゴリズムで実装されています。

実装内容は下記の記事を参照してください。

使われているTrieMBというクラスは、githubにも登録されています。よければお使いください。

Trieを使ってマッチさせていますが、さらにマッチ方法を3種類サポートしています。これはPOST_MATCH_LONGESTというconfig.inc.phpの値によって決定されます。

ソースコード中では、TKeyword.class.phpのmatchAllがPOST_MATCH_LONGESTが0の場合、matchLongestが1の場合、matchLongest2が2の場合に相当し、デフォルトではmatchLongest2になっています。

それぞれ、「こん」と「んにちは」がキーワード登録されている場合に「こんにちは」をマッチさせた場合の挙動として、以下のような違いがあります。

速度的には0が最速で、1と2はあまり違いがありません。

アルゴリズムとしては現状のままでいいと思うのですが、毎回データベースから全キーワードを取得してTrieデータベースを再構築しているめ、このTrieデータベース構築が非常に遅いという問題があります。特に、キーワード数が1万件を超える場合に投稿時の速度低下が顕著になります。

対策としては、本来TKeyword.class.phpはWebプログラムではなく、バックグラウンドのデーモンプロセスとして動作させたいのですが、開発者が専用サーバを持たない環境であるため難儀しています。べき論としてはC言語で書いて、PHPとはソケット通信で行うべきかと思います。

当面の対策として、TrieMBを丸ごとシリアライズしたものを保存してそれを読み込めば多少早くなるかも、という予想を立てていますので、開発に余裕が出たらパフォーマンス検証をした上で、その方向で対応するかもしれません。

ただこの程度の対策では、はてなキーワードのような30万超、Wikipediaのような100万超のキーワードには対応しきれないので（メモリを4GBくらい使ってしまいます）、大規模な運用を想定されている方はご注意ください。