検索エンジンを作る

第12回近接検索機能

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

近接検索の利用価値

「ある文字列"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の演算が存在し、ひとまずこれを用いることで対応できるので、除外フラグ専用の検索式は設けないこととしました。

このようにしてできあがったのが、表1に示した近接演算子の仕様です。

表1 近接演算子の仕様
検索式意味
"A" ADJ "B" A,Bの順で文字列が出現し、その距離がデフォルト値以下である文書を検索
"A" ADJ<n> "B" A,Bの順で文字列が出現し、その距離がn字値以下である文書を検索
"A" ADJ<n, m> "B" A,Bの順で文字列が出現し、その距離がn字以上m字以下である文書を検索
"A" ADJEQ<n> "B" A,Bの順で文字列が出現し、その距離がn字である文書を検索
"A" ADJNE<n> "B" A,Bの順で文字列が出現し、その距離がn字でない文書を検索
"A" ADJLT<n> "B" A,Bの順で文字列が出現し、その距離がn字より小さい文書を検索
"A" ADJLE<n> "B" A,Bの順で文字列が出現し、その距離がn字以下の文書を検索
"A" ADJGT<n> "B" A,Bの順で文字列が出現し、その距離がn字より大きい文書を検索
"A" ADJGE<n> "B" A,Bの順で文字列が出現し、その距離がn字以上の文書を検索
"A" NEAR "B" 順序を問わずA,Bの文字列が出現し、その距離がデフォルト値以下である文書を検索
"A" NEAR<n> "B" 順序を問わずA,Bの文字列が出現し、その距離がn字値以下である文書を検索
"A" NEAR<n, m> "B" 順序を問わずA,Bの文字列が出現し、その距離がn字以上m字以下である文書を検索
"A" NEAREQ<n> "B" 順序を問わずA,Bの文字列が出現し、その距離がn字である文書を検索
"A" NEARNE<n> "B" 順序を問わずA,Bの文字列が出現し、その距離がn字でない文書を検索
"A" NEARLT<n> "B" 順序を問わずA,Bの文字列が出現し、その距離がn字より小さい文書を検索
"A" NEARLE<n> "B" 順序を問わずA,Bの文字列が出現し、その距離がn字以下の文書を検索
"A" NEARGT<n> "B" 順序を問わずA,Bの文字列が出現し、その距離がn字より大きい文書を検索
"A" NEARGE<n> "B" 順序を問わずA,Bの文字列が出現し、その距離がn字以上の文書を検索

"文字列"は全文検索対象のフィールドのいずれかに文字列の値が含まれることを示し、n, mには整数値を指定します。ADJという演算子が出てきますが、これはADJACENTという英単語(近接した、直前のという意)の略です。

ADJは左右の語は指定された順に現れるという条件で、NEARは順不同という違いがあります。また、近接演算子を次のように、1つの検索式で複数回用いることもできます。

"A" ADJ "B" ADJ "C" ADJ "D"

この場合は、"A"の後に"B"、その後に"C"、その後に"D"という文字列が現れるという条件での検索となります。

近接演算子の左右には文字列、もしくは近接演算子で構成される()のブロックしか記述できません。つまり、次のような検索式は記述できません。

"A" ADJ ( "B" AND "C" )

近接演算子による検索式の例

では、実際の近接演算子による検索式を見ていきましょう。

「福田首相」⁠福田 首相」⁠福田康夫首相」⁠福田 康夫首相」⁠福田 康夫 首相」といったバリエーションに全て合致するような近接検索は、4文字以内に"福田"と"首相"の文字列が順に存在すれば良いので次のようになります。

"福田" ADJ "首相"

このように、人名を検索する場合などに近接演算子は力を発揮します。ほかにも製品名、病名、化学物質名などの検索にも訳に立ちそうです。

"福田"と"首相"の文字列が近接しているという条件に加え、文中に「靖国神社参拝」を含む記事を探す場合にはつぎのように括弧が必要です。

( "福田" ADJ "首相" ) AND 靖国神社参拝

括弧がないと、パーサの構造上

"福田" ADJ ( "首相" AND 靖国神社参拝 )

として指定されたことになり、近接演算子の左右には文字列もしくは、近接演算子で構成される()のブロックしか記述できないという制約にひっかかってしまいます。

おすすめ記事

記事・ニュース一覧