よーく考えよう。検索は大事だよ～
この前でも書きましたが、巨大ファイルを取り扱う上で重要となるのは検索でしょう。
巨大なデータの中から目的のものを見つけ出すのは容易ではありません。
ソートでもされていれば探せないこともないでしょうが、そうでなければ何億行何兆行もの中から探し出すのは、不可能とは言いませんが、ウォーリーを探せより困難な行為でしょう。
コンピュータにできることならコンピュータにやらせるべき。
まあ、完全に信用するのもあれなんですが。
イギリスでの大量誤認逮捕事件とか。
ともあれ検索です。
どうするかといえば、これはもう、最高効率と名高いBM法で決まりでしょう！
とはならないのが検索の世界ｗ
BM法のことはちょっと検索すれば出てきますので、ここでは詳しく説明しませんが、要は後ろから比較していって、一致しない場合は検索文字の前方にその文字があれば、そこまでの文字数分を検索スキップ、全く無かったら検索文字分全スキップするという方法です。
元の文章が検索文字の一番うしろの文字と一致せず、他の検索文字とも一致しないのであれば、1文字ずつずらして比較していっても、一致するはずがないですからね。
検索文字にその文字がないことがわかっていれば、その分スキップする、あるのであればそこまでスキップするというのは理にかなっています。
しかし一見うまくいきそうなこの方法。
アルファベットと数字や一般的な記号。つまり1バイト文字圏ならいいのですが、SJISなどの日本語やらUTF-8とかの複数文字の組み合わせで別の文字として扱うコード体系ではうまくいきません。
例えば全角2バイト目なんかは、普通にアルファベットだったりするので、そんなところから比較したりすると、思わぬところでマッチするからですね。
なのでスキップするときに、そこが全角第2バイトだったら、もう一個進めるとかしてこの文字境界をあわせてあげる必要があります。
また、「＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊%＊＊=」のような文字列を「*%**=」の検索文字列で探そうとすると、＊は後ろから常に2番目にあるから、スキップできる文字は%が出てくるまで常に１文字。
これでは頭から検索するのとたいして変わりません。
いえ、複雑な処理をする分手間がかかっているので、かえって遅くなるでしょう。
また、検索文字列が1文字の時とか検索文字列が短いときは、同じく複雑なことをしている分効率が落ちます。
何文字目になんの文字があるか調べるにも時間がかかりますからねぇ。似たような文字列パターンで似たような検索文字列を検索すると、スキップできる文字数が少なく、最悪のケースだとゴリ押しで検索したときと同じ検索回数になるという欠点を抱えています。
その他、英大文字小文字を区別しないで比較するとかになると、[C|c]の両方が検索文字にないか確認する必要があったりと、なかなか面倒な処理が必要になります。
さらに複数の検索文字列で検索する場合、それぞれの検索文字列長が違ったりしたら、一律にここが最後と決められません。
検索文字列が多数あれば、どこまで比較するかの長さもまちまちになりますからね。
もちろん正規表現検索なんてことになると長さが不定なので、やるとしても一部の固定文字だけとなるでしょう。
まあ、正規表現はライブラリを使うので、工夫の余地はないのですがｗ
あとはハード的な問題になるのですが、現在のCPUはキャッシュメモリというものがあり、この範囲にプログラムやデータが収まると、高速に処理することができたりします。
プログラムが大きくなると当然、このキャッシュメモリに収まらなくなり、速度が落ちます。
その他インテルのCPUには文字列検索命令みたいなのがあったりして、アルゴリズムを工夫するより、CPUでゴリ押ししたほうが早いケースもあったりします。
さらにCPUの最適化技術の中に先読みという機能があり、連続したアドレスのメモリーを操作する場合、先にキャッシュメモリーに読み込んでおいて高速化する技術ですが、検索位置をスキップすれば当然先読みが外れる可能性が高くなります。
この辺はCPU依存なのでどうやれば早くなるとは一概に言えませんが、短い文字列あるいは単調な文字列の場合、BM法はゴリ押し検索よりものすごく効率が落ちることになります。
つまりいい時と悪い時の差が激しいのです。
他の方法としては、対象文字列を適当に分割して別スレッドで検索するのもいいかもしれません。
最近のCPUだと32スレッドとかスレッド数がとんでもないことになっているので、スレッド起動のオーバーヘッドを無視すれば、32倍速で動くわけですから、アルゴリズムで工夫するのが馬鹿らしくなってしまいますね。
このようにBM法はアルゴリズム的には優れていると言われているものの、使われるシーンは限定的であるとも言えます。
なので状況に応じて最も効率のいいアルゴリズムを使うように、いくつか検索ルーチンを用意するのがいいでしょう。
場合によってはアセンブラで書いてみたり、スレッド分割するのもいいかもしれません。
もっとも、趣味レベルですので、実際ここまではやりませんけどw
ちゃぶだいひっくりかえしー！
んなもんやってられっかー！
どうせ正規表現使ったら、こんな工夫は全部パー。
スレッド分割くらいしかできることがない。
というわけで、もうCPUゴリ押しでゴリ押しますｗ
とはいえちょっとくらいなら工夫が有ってもいいかなとかは思いますが。
ということで目をつけたのはローリングハッシュ法。
ハッシュをころころしちゃう検索法です。
ハッシュといえばmd5とか有名ですが、大きなデータだろうと数バイトのデータに変換して、それを比較して同等かチェックするものですね。
もちろん何Mバイトあろうが数バイトに圧縮しちゃうので、場合によっては別のデータであっても同じ値になるケースが出てきますが、十分バラバラであれば、同じキャッシュ値になることは稀であると言えます。
念のため、もう一度ちゃんと比較する必要はありますが。
しかしBM法と同じく、判定が複雑になると、それはそれなりに時間がかかります。
特にローリングハッシュ法ではハッシュ計算するのに各桁に掛け算が必要だったりして、これが意外とコストが掛かったりします。
例えば検索文字列3文字で、対象文字列が[123]という3文字の時、ローリングハッシュ法でHash化すると、
[1]*10^2 + [2]*10^1 + [3]*10^0 = 123となり次の数字が4だとすると前回結果に係数をかけて新たに4を足してローリングさせます。その後1番最初に追加した[1]*係数を引き算します。
[123]*10^1 + [4] - [1]*10^3 = 234みたいな感じでHash値がローリングします。
今はわかりやすいように10のべき乗を使用しましたが、ここはオーバーフローしない程度ならまあ適当な数字でいいでしょう。
なんでこんな計算をするかというと、データが前後しただけとかの時に値が同じにならないためですね。この係数の掛け算を行わないで、ただ加算しただけだと[1]+[2]と[2]+[1]でおなじ[3]になってしまいます。
しかし、例にある10のべき乗については予め計算した定数にしておけるのですが、前回のHash値に係数をかけたり、不要になった分の値を差し引きする時に乗算が必要になります。
最近のCPUは乗算と加算減算とではかかる時間がほぼ同じらしいのですが、演算が増えれば当然処理に時間がかかります。
こういうアルゴリズムを考え、論文なんかを書く人は、比較回数については検討していても、計算コストを考慮していない場合が多いようです。
確かに比較回数が半分になれば、当然計算回数も半分になりますが、一回の計算時間が2倍になれば、せっかく回数を減らしたのが全てパーです。
そして、文字列比較ってものすごく単純なルーチンで、極端なことを言えば
if (*src++ == *dest++)
をぶん回すだけですからねぇ。
これを置き換えるとしたら、あっという間に数倍の処理時間がかかるようになるのもわかろうというものです。
ある程度検索文字列が長く、検索文字列や対象文字列がバラバラのの文字なら、比較コストも元が取れるのですが、いつもいつも長い文字列で検索するとは限りません。
実装する場合は計算回数だけではなく計算コストも考慮に入れないと、思ったほど早くならず、逆に遅くなった、ということもあり得るわけです。
実際にローリングハッシュ法を普通に使った場合と、係数の掛け算をなくして、単に足し算引き算だけにしたほうとで比べた時、単純な足し算のほうが検索時間が倍くらい早かったとかあります。
もちろん文字列の並び方や検索文字列の長さによって有利不利が変わってくるでしょうが、検索文字列はともかく、検索される方の文字列は事前に並び方のパターンを把握するすべはありません。
ならば、十分早い方法なら、1種類を実装すれば実用上は問題ないのではないかと思うのです。
どうせそのうちCPUが早くなっていくだろうしｗ
なんという他力本願（誤用）
というわけで、今回はローリングハッシュ法の単純版でまず振り分けして、あとはゴリ押し検索を行う方式で行きたいと思います。
足して引く方法なので、自分では勝手にサムサブ（SumSub[tract]）法なんて言ってますけどｗ
寒々しい命名だと自画自賛ｗ
ああ、今日は冷えるなぁ。
