migemoの高速化[サーベイ編]

　migemoが重い。というか、sで検索しようとすると[Regular expression too big]とかエラーがでる。
　migemoが正規表現を返す必要があるのかというと、実のところ、ほとんどない。マルチキーワード検索を簡単に実装するために正規表現を返しているだけといってよい。
　そこで、高速化のための手法を考えてみる。要するに、効率の良いマルチキーワード検索を実装すれば良いのだ。単なる文字列と文字列の照合であれば、KMP法とかBM法とかいった方法があることは私も知っている。しかし、検索したい文字列が複数の場合にどうすればいいのかは知らない。それを考えてみたい。
　しばらく考え、Trieにキーワードを登録して、テキストから文字を取り出してTrieを探索しマッチするかどうかを確認してゆけばよいのではないか、という事に思い当たった。探索に失敗したときにどこまで文字列を飛ばせるのか、というのは、考えてみないとわからないけれど。文字列を飛ばすことを考えないとしても、単純にキーワード毎に検索してその結果をマージするよりはだいぶ速くなるはずだ。
　ここまで考えた後、この問題ははてなキーワードの抽出と同じ問題である事に気づいた。ここに気づけば、はてなキーワードを高速に付与とかAC法とかRubyでTST+AC法 (ruby-pytst)といったページの事を思い出して検索するのはあまり難しくない。
　はてなキーワードを高速に付与によると、AC法のキモは検索したいパターンをTrieに入れて探索を行うことらしい。つまり、私が考えたアイデアと基本は一緒だ。ただ、どこまでスキップするかとかそういう情報も入れてあるそうなので、全体としては私が考えた事より高度である。
　RubyでTST+AC法 (ruby-pytst)によると、ruby-pytstではTrieとしてはTernary Search Trie（TST）というものを使っているようだ。ちょっと調べてみた限りでは、TSTのTrieとしてのメリットがよくわからない。DoubleArrayに勝るところはないように思える。（まぁ、DoubleArrayには実装がかなりめんどくさいという大きなデメリットがあるのだけれど…。）
　さらに、AC法で検索して、複数パターンの文字列照合におけるマッチングマシンの動的構成法という論文を見付けた。この論文自体は読めなかった（大学にいけばあると思うので、また今度図書館に行ったときにでも読んでみようと思う）のだが、BM法をマルチパターンに拡張した方法としてFAST法，MBM法等が既に提案され，AC法より高速である事が示されているという事がわかった。それにしても、この論文の発表された年度を見ると、もう既に10年近くも前である。随分と前の問題を調べてたんだなぁ…。
　ここまでいろいろ調べてみたが、Emacsの正規表現検索コードはおそらくCで書かれており、扱う問題自体を変えるとはいえ、elispで探索速度を上げようかなり無謀な試みなのではないかと気づいた。というか、そもそも正規表現検索の方が遅いという保証もない。
　というわけでmigemoの高速化[実装編]が書かれる予定はありません。