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

高速な文字列マッチング

NLP

最近は、簡潔データ構造を中心に調べたりしていたけど、文字列マッチングを考えた場合、別のアプローチもあります。そう、grepのような逐次文字列検索ですね。以下の解説がおもしろいです。

http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJMagazineCPM.pdf

CSAとかFM-Indexに隠れてしまっていますが、実はかなり強力です。特に、クエリが固定で、テキストが頻繁に変更されるようなケースでは有効です。中でも使いやすのは、Aho-Corasick法(AC法)ですね。複数のパターンを同時に検索することができます。KMPを拡張した方法です。

AC法については、日本語だと

情報検索アルゴリズム

情報検索アルゴリズム

が詳しいですね(以下、検索本)。あと、英語だと、Navarro神の

Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences

Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences

がよくまとまっています。また、こちらは、Advanced AC法(Fail遷移を削除したACオートマトンを作成する)についての記述があります。
AC法については、はてなのキーワードリンクでも使われています。

さて、実際の実装ですが、ダブル配列を使うといい感じです。例えば、以下の論文なんかは、うまくダブル配列に融合させています。

http://www.anlp.jp/proceedings/annual_meeting/2007/pdf_dir/B4-9.pdf

さすが、ダブル配列の本家の研究室だけあります。

ダブル配列の実際の実装では、キーワードの追加が遅いというのが厄介ですが、その点は、以下の論文で提案されている未使用要素のリストを使うといい感じに解消できます。

http://ci.nii.ac.jp/els/110002725995.pdf?id=ART0003014471&type=pdf&lang=jp&host=cinii&order_no=&ppv_type=0&lang_sw=&no=1374762521&cp=

これで、検索速度と空間効率がいい感じになります。

ダブル配列でAC法が実装できるということは、LOUDSでも実装できるということです。その場合、空間効率は良くなりますが、検索速度は劣化します。

最後に、AC法の動的更新をする場合ですが、それについては「検索本」で紹介されています。また、以下のような論文もあるようです。

http://db-event.jpn.org/deim2012/proceedings/final-pdf/f11-5.pdf

文字列マッチングは、古典的ですが、

FM-Index作成時間 + (キーワード検索時間 * キーワード数) > 逐次文字列検索時間

という関係ならば、FM-Indexよりも逐次文字列検索の方が優れています。例えば、検索するキーワード数が多い時とかですね。

検索技術は奥が深いですね。