もうちょっと検索ばなし

その他

QuickSearchで短いtextを検索すると、前処理があるのでどうしても力任せ検索に負けてしまいます。じゃあ、どのくらいの長さのtextやpatternなら力任せ検索より早いのか？ってあたりを調べてみたけど…、う〜ん簡単にはわかんないですね。
textの長さを20文字程度、30文字程度、50、100、200、300文字程度と用意して、patternもいろいろでやってみました。だいたい200、300文字だと力任せに勝つことが増えてくるかなってくらい。もっと短いtextでも早いときは早いし、逆にtextの先頭あたりにpatternが見つかる場合なら力任せが絶対勝つし。
遅いといっても1.5倍程度なので、50万回まわして30ms程度遅いだけ。どうでもいいっちゃ〜どうでもいい差なので、もうこれ以上調べるのはやめときました。いくら調べたところで結局、特定のケースのいくつかを調べたことにしかならないし。
ある程度長いtextの検索が多そうならQuickSearchを使い、短いtextを検索する場合が多そうなら使わないってことでいいと思います。
id:siokoshou:20060324の実装はstaticメソッドにしたけど、同じpatternでたくさんのtextを検索するなら、patternとスキップテーブルをフィールドに持ち、一度だけ初期化するようなクラスにすればかなり高速化できそうです。それから、スキップテーブルをint[256]からbyte[256]にしたらかなり高速化できました。

EXACT STRING MATCHING ALGORITHMS(以下ESMAJ)に載ってたほかの検索もいろいろ試してみたので、大雑把な結果だけ書いておきます。ESMAJのCコードをC#にして調べたので、ESMAJのCコードそのものの性能を測ったわけではありません。その点はご注意を。

  • BMH(Horspool algorithm)
    • QuickSearchよりわずかに遅い。けど、ほとんど一緒。
  • Smith algorithm
    • BMHとQuickSearchを混ぜたもの。QuickSearchの2倍くらいの実行時間になった。・⌒ヾ(*´_｀)
  • Shift Or
    • めちゃくちゃ遅かった。力任せの10倍以上遅くなったりするので、移植失敗したのかもしれない…
  • Karp-Rabin algorithm
    • RubyのString indexで使っているのがこれ。参照:google:Karp-Rabin。コードは http://www.ruby-lang.org/cgi-bin/cvsweb.cgi/ruby/re.c?rev=1.149;content-type=text%2Fx-cvsweb-markup を rb_memsearch で検索すると見つかります。ESMAJのコードを元に改良したもの。
    • RubyのコードはESMAJのコードの欠点を修正してあるのでRubyのコードをC#に移植して試してみたところ、まつもとさんのおっしゃるとおりtextが短い場合の性能がよいです。ただし、力任せ検索に勝つことはほとんどありませんでした。Cなら勝つんでしょう。検索の結果見つからない場合は力任せよりかなり遅くなりました。

Karp-Rabinを移植するとき、C#のシフト演算でuncheckedいるよね〜？と思って調べてみたら、「シフト演算ではオーバーフローが発生することはなく、checked コンテキストと unchecked コンテキストで同じ結果になります。」だそうで。知らなかった。

Shift OrとKarp-Rabinの結果がひっかかるけど、でもそろそろ飽きてきたので検索ネタはそろそろ打ち止めかもかもかも。