複数検索の話
お金は大事と言いつつ、もっと保険に入ってねと、保険のおばちゃんに圧倒されて複数の保険に入らされたかのごとくｗ、複数文字列検索の要求が結構有ったりします。
世の中は理不尽だらけです。
前回した検索の話は、検索文字列がひとつだった場合。
これが複数文字列を同時検索するとなると、また話が違って来ます。
どういうことかといえば、
「小説家になろう」
「アルファポリス」
「ハーメルン」
「カクヨム」
という4つの文字列を一回で検索するのが、複数検索です。
何に使うかといえば、この4つ中から最初に出てきた場所を見つけたいとか、いっぺんに置換したいとかの時ですね。
特に複数置換のときに威力を発揮します。
例えば、
「東京都心」を「東京都新宿」
「京都」を「京都府」
と変換したい時、以下の文字列をうっかり「京都」から先に置換してしまうと
「東京都心と京都都心を比べると」->「東京都府心と京都府都心を比べると」
のように、ワケワカメなことになってしまいますし「東京都心」はマッチしなくなります。
逆に「東京都心」「京都」の順で置換すると、
「東京都府新宿と京都府都心を比べると」となり、これもまたおかしなことに。
複数文字列置換機能があれば、最長一致で「東京都心」が「東京都新宿」に変換され、1度変換された文字列は変換の対象外となり、次の「京都」が「京都府」無事変換されることになります。
まあ元々のAliceBuilderにはそんな機能はないのですがｗ
ですが、巨大ファイルを扱うからにはここはぜひとも入れたい機能。
巨大ファイルの主なものってDBのCSVファイルとかでしょうから、DBからではできないような変換が主な使い方になるでしょうし。
というわけで、少し検討してみましょう。
さて、前回ゴリ押ししたので、今回もゴリ押しすればいいよね！
はいしゅーりゅー。
って、わけには行きませんよね。
ここまで読んでいただいた方に申し訳なさすぎます。
てことでもう少し考察します。
複数の文字列を前回と同じ方法、つまりサムサブ法ｗ で検索すると、検索文字列の文字列数分だけサムサブ値が必要ですし、対象文字列の方にも4つのサムサブ値を作成維持していかないといけないことになります。
検索文字列がもっとたくさんなら、もっとたくさんの値の保持と維持管理が必要になるわけで、よくある会社の組織名変更（内情は何も変わっていないｗ）とか、でかい会社だと何十という項目を置換しなければなりません。
しかも似たような名称でｗ
もちろんサムサブ値が増えれば比較する回数も増えますし、サムサブ値を、検索文字列数分作らなければなりません。
もし同じ文字数の検索文字列があれば、ある程度まとめられるでしょうが、最近の無駄に長いｗ 組織名だと文字列長が一致するケースも少なくなることでしょう。
ではどうするか？
世の中にはAho-Corasick法やらFAST法やらあるらしいですが、やはり計算量が多い。
というかめんどくさいので実装したくないｗ
他人が何考えているかなんてわかりっこないからね！（暴論ｗ）
というわけで、車輪の再発明になるかもしれないけど、自分なりの工夫をしてみる。
まず、複数文字列を検索する際に何が問題になるか考えてみましょう。
これが不明だと何をしていいかさえわかりませんからね。
当然ゴリ押しだと、その検索文字列の数だけゴリゴリしないといけない点にあります。
1文字目でアンマッチしたとしても、20個も検索文字列があれば、20回の比較が必要で、文字列数が増えれば当然それだけ比較回数が増えますし、途中までマッチするような場合はさらに比較回数が増えるわけです。
最悪は検索文字列数×文字数と対象文字列数との比較なので、もう大変なことにｗ
ゴリ押し法（正式名ナイーブ法？）はO（n×m）らしいですが、ｎは固定でもm（検索文字数）が増えれば倍々ゲームで増えていくわけですから、当然計算量も増えるわけです。
「ぼくのかんがえたさいきょうのけんさくほう」サムサブ法ｗでもサムにヒットする確率が文字列数が増えるに比例して大きくなっていくわけですから、速度低下は免れません。
ならばどうするか？
逆に考えるんだ。
検索文字列がたくさんあろうと、対象文字列は一つしか無い。
つまり対象文字列から検索文字列を探せばいいのです。
ん？
どゆこと？
例えば検索文字列を木構造化してしまいます。
トップノードにまず最初の検索文字の1文字目を登録。その後次の検索文字列の1文字目のコードがそれより大きいか小さいかで、左右に検索文字を振り分けていく。
たとえば128より小さい文字コードは左に、128以上の文字コードは右へ登録といった具合。
そこにすでに登録した文字があれば、その文字コードより小さいものは左に、大きければ右へと進んで、空いたノードがあればそこへ登録。
なければ同じようにして先に進みます。
最初の文字コードが極端に小さかったりすると、全部右に来るんだけどね！
この辺はリバランスして木構造の平衡を保つ必要があるんだけど、詳細を書くには余白が狭すぎるので省きますｗ
まあこんな感じで検索文字列を木構造のデータベースに登録し、対象文字列の文字を木構造から探していきます。
それを一番下まで探繰り返しノードがなくなれば試合終了です。登録されていないことがわかるので、対象文字列の開始位置を一つずらします。
登録されていれば、そこに検索文字列本体やサムサブ値を登録しておいて、あとは検索文字列が一つのときと同じことをすればいいわけです。
これは2分探索とかいって検索文字を高速に探すやり方ですが、
あれれ～おかし～ぞー。
検索文字列全部の頭文字が同じものだと結局探せていないのと同じことじゃ？
仕方がないので、この最後のノードに更に2文字目以降のノードを同じようにぶら下げていきます。
これで完璧だぜ！
ん？
2文字目以降も同じようにしたら、全部検索したのと同じことにならね？
うん、1文字目があったら2文字目のノード、2文字目があったら3文字目のノードといって、最後までマッチしたら、同一ってことだし、登録がなければ検索が失敗したと同義です。
検索文字列を探すだけで検索できるという。
まあ考え方はAho-Corasick法とかと同じだけど、ノードがあっちに繋がったりこっちに繋がったりで面臭いんじゃー。
下ーに～下ーに～でいいじゃん。
確かにノードを再利用できるとメモリー効率いいし、同じ要素があるとかわかっていいけどさー。
しかしコンピュータ的にはメモリー効率を無視したほうが効率がいいときもあります。
例えば全角第1バイトの判定処理。
win32apiにはIsDBCSLeadByte()関数が用意されていたりするんですが、マクロで書くとこんな感じ。
#define IsDBCSLeadByte(c) ((((c)>=0x81)&&((c)<=0x9f))||(((c)>=0xe0)&&((c)<=0xfc)))
まあ、普通ですね。
全角第1文字の範囲を調べているだけ。
しかしこのマクロ。
比較で4回、&&||で2回の演算を行っていて、いかにも無駄です。
ここで登場するのが頼もしいあの人。
そう金色のHashクンの出番ですｗ
Hash値が十分バラバラなら、とても効率のいいあいつです。
原理は簡単。
予め256個の文字コードテーブルに全角1文字目かそうでないか、1か0を入れておくだけ。
こうすればIsDBCSLeadByte[c]という風に配列にアクセスするだけで判定が可能です。
計算はテーブルの先頭アドレスと、そこへのオフセットであるcとの足し算だけ。
あとは真偽判定すれば終わり。
Hash値計算なんかしなくても、値さえあればHashれる。
そこにしびれる！ あこがれるう！
ってことで、割とこんな単純なHashというかテーブルを使って、前もって出した計算値を取得するなんてことをしてたりします。
著作「ジョブズ～」でも足し算をテーブルを使って実現しています。
これも一種のHashですね。
今回の複数検索についても、この単純Hashを使っていきます。
といってもどう使うかですが、さっきはバランスの取れる中間値でデータを左右に振り分けていましたが、分岐がたくさんあるとその分、深く潜らないと目当ての検索文字にたどり着けません。
木のバランスが取れていれば、1度のチェックで検索対象は半分になっていくので、最大8回チェックすれば1バイト目にチェックしたい文字が登録されているかわかります。
しかし8回もチェックするのはあまりに無駄です。
そう。
先程の全角1バイト目チェックのように256バイトのテーブルを作り、文字コードをHash値とした配列に、次の文字があればまた256バイトテーブルにつながるリンクを入れて、なければ終わりマークを入れるだけのカンタンなお仕事です。
文字コードは全角だろうと半角だろうと、最初は1バイトですからねぇ。
256バイトあれば重複もなく完全ハッシュが可能なのです。
検索文字列の1文字でも違う部分があれば、そこでリンクは分かれますから、終わりマークは必ず一つの文字列に対してくっつくはずです。
2分木みたいに大きさを比較してなんてやらなくていい。
その分メモリー使用量は増えますがｗ、文字コードが分かれば次のノードがすぐ見つかります。
6文字の検索文字列が有ったとしたら、6回の配列アクセスでその文字列が登録されているかわかるのです。
つまり、対象文字列一つに対して1回の検索で終了ですから、O（n×m）のmは検索文字列長の検索平均値に収束するでしょう。
mの値が検索文字列を追加すればそれに比例して増えることを考えれば、文字列長の平均値は早々増えないですからねぇ。
同じ文字列長であれば、極端に類似する文字列でも入れないと平均値はいつまでも変わらない君でいてくれますｗ
いくら追加しても、計算量は変わりません。
千個登録しようが100万個登録しようが、計算量は同じ。
これは一つの検索文字列をナイーブ法で検索したのと同じことになりますが、検索するたびに違う文字列になるのでサムサブ法もBM法その他アルゴリズムも使えず、愚直にゴリゴリするしかありませんが。
素直にAho-Corasick法やらFAST法を使えって？
自分不器用なので。
ということで検索の話はここまでです。
