検索エンジンを作る

第12回 近接検索機能

この記事を読むのに必要な時間:およそ 2 分

今回は,ある文字列の近くに別の文字列が存在するという条件の全文検索機能について取り上げます。

近接検索の利用価値

「ある文字列"A"の近くに特定の文字列"B"が存在する」という条件の全文検索を考えてみます。まずは,AND演算子を使って検索することを検討してみましょう。

"A" AND "B"

このようなAND演算子を使った全文検索では,文中のどこかに"A"と"B"という文字列が存在しさえすれば,結果に含まれてしまいます。この方法では,"A"と"B"の出現位置が接近しているという条件がまったく反映できません。「近く」という条件は,単純なAND検索では表現できないのです。

では,「近く」という条件にはどのような利点があるでしょうか。100ページ近くある長い文書の頭と終わりに"A"と"B"の文字列が出現している文書と,1段落の中に"A"と"B"の文字列の出現している文書とでは,どちらが"A"と"B"の両方の概念について言及している文書かを考えてみると,後者の方が可能性は高そうです。つまり、複数の文字列が「近く」に存在する条件による検索は,AND条件を使うよりも利用価値があるのです。

DIALOGというオンライン情報検索システムがあります。18年くらい前に大学の図書館で,何度かDIALOGの端末から論文を検索して,アメリカから論文を取り寄せた経験があります。筆者にとっては本格的な情報検索システムとの最初の出会いでした。この時には世の中にはものすごい検索システムがあるのだなとつくづく感心したものです。今では情報検索というとすっかりあたりまえになってしまいましたが,18年前の筆者にとっては大きな衝撃でした。話を元に戻しますが,DIALOGには「近く」という条件を表現する機能があり,DIALOGに詳しい人の話によると,かなり頻繁に使われる機能ということです。

Z39.50を参考に

FINDSPOTの商用化段階の開発を行っていた時に,客先からぜひとも「近く」という条件での検索機能を実現して欲しいという要請がありました。そこで,どのような機能を実現したら良いかと調べていくと,Z39.50というISO 23950の情報検索規格に突き当たりました。こちらの日本語訳はJIS X 0806というJIS規格にもなっています。この中に近接検索の機能が定義されていました

WAISという検索システムではZ39.50のプロトコルを使って情報の検索を行っています。

この規格には,距離(distance),関係(relation),単位(unit),順序(ordered),除外(exclusion)についてそれぞれ次のように指定できることが要請されています。

距離
2つのオペランドの位置を表す順序の差
関係
未満,以下,等しい,以上,より大
単位
文字,語,文,段落,節,章,文書,要素,部分要素,要素型,バイト,私的に定義された単位
順序フラグ
これがセットされた場合,"右方"近接だけとなる
除外フラグ
これがセットされると,演算にNOTが適用される

FINDSPOTの近接検索機能

FINDSPOTの近接検索機能を設計する際には,Z39.50を参考にして,この近接検索機能をできるだけ多く実装するのが,ひとつの目標となりました。

FINDSPOTでは,文書中のバイグラムの出現位置(文頭からのオフセット)を,インデックスの中に記録しています。単位については,この出現位置情報を利用することで,文字単位による近接検索を実現することにしました。その他の距離単位に関しては,語単位,文単位,文節単位などを実現するとなると,日本語の場合には形態素解析の機能が必要になったり,このような単位の出現位置をインデックス中に含める必要があります。文字単位以外の距離指定については,FINDSPOTの構造に大きく手を入れる必要があるため,機能の実現は見送ることにしました。

距離については,毎回距離の数値を指定しなければならないのは結構煩雑に思えたので,距離の数値を指定しない場合にはデフォルト値(規定値)を用いることにしました。デフォルト値は,FINDSPOTの設定ファイルで指定する仕様としました。

除外フラグについては,すでにNOTの演算が存在し,ひとまずこれを用いることで対応できるので,除外フラグ専用の検索式は設けないこととしました。

著者プロフィール

工藤智行(くどうともゆき)

有限会社サイパック取締役社長。システム構築・管理のコンサルティング,ローカライゼーション,文書処理や障害者向けソフトウェアを中心とするプログラミングを長年手がける。 近著『UNIXプログラミングの道具箱』『システム管理現場の鉄則FreeBSD編』等

URLhttp://www.cypac.co.jp/

著書

コメント

コメントの記入