[ トップページ ]

« ブログのアクセスはふえたが,だれも検索しないのはなぜ? | メイン | Ads by Dasyn.com »

ハッキング

候補しぼりこみ率の改善

これまで,カタカナ語やひらがな語の一部の検索にはかなり検索時間がかかっていた. たとえば 「アイドル」 の検索には検索サーバ側で 16 秒くらいかかっていた. その原因はこれらの語の 2 グラム・インデクスがいずれも候補がおおくて,事典項目のしぼりこみがゆるくなっていたためだ. それを改善する方法をくふうしてくみこんだので,「アイドル」 などは 14 秒くらいまでは改善されたが,総合的には比較的わずかな改善にとどまった.

「アイドル」 の候補しぼりこみには,「アイ」,「イド」,「ドル」 という 3 つの 2 グラム・インデクスを使用する. このうちのいずれかの出現箇所がかぎられていれば,候補を十分にしぼりこむことができる. ところが,いずれも出現がおおいので,しぼれない. そのため,候補を逐次検索するのに時間がかかってしまう.

これまでの方法ではひとつの項目のどこかに 「アイ」,「イド」,「ドル」 というつづりがあらわれれば,すべて候補とみなしていた. そのため,項目内のはなれた 3 つの位置にこれらがあらわれていれば,候補とみなしていた. あたらしいアルゴリズムでは,これらがちかくの段落にあらわれるばあいにかぎって候補としている. (N グラムの全文検索アルゴリズムにおいては,さらに段落内の位置までインデクス内にもつが,メモリ量はさらにふえる.)

ほんとうは同一の段落にあらわれるときだけ候補としたかったが,すべての段落の情報を (ビット・ベクタとして) 表現すると可変長になって処理速度がかえっておちてしまう. この方法もためしたが,これまでの方法で 2 秒で検索できる 「漱石」 の検索に 400 秒かかるようになってしまったので断念した. 段落情報を 32 bit にとどめるために,段落数がおおいときは,ちかくの段落をくべつしないようにした.

この方法で,これまで候補しぼりこみに約 0.8 秒,「アイドル」 の逐次検索に約 9 秒かかっていたのが,それぞれ 1.2 秒,6.6 秒となった. 候補数でいうと,これまで 393 万だったのが,243 万まで減少した. 予想していたほどはへらなかったので,検索時間も劇的には短縮されていないが,一応,効果はあった (へらない原因のひとつは結果数がおおい (約 12 万個) ことであり,これは表示するページを分割しなければ解決しない). そのかわり,インデクスがしめるメモリ量は約 2.4 GB から約 4.5 GB に増加した. それでも,なんとか 10 GB のメモリのなかにおさまっている. メモリを増設しないかぎりはこれが限界だ.

キーワード:

トラックバック

このエントリーのトラックバックURL:
http://www.kanadas.com/mt/mt-tb.cgi/4385

コメントを投稿


メインページアーカイブページも見てください.

Powered by
Movable Type 3.36