検索エンジンを作る

第8回検索と論理式

これまでFINDSPOTのN-gramによる検索機能のしくみについて解説してきました。今回から検索式というテーマに移ります。

検索式のコンセプト

検索式とは、検索エンジンに対して全文検索の問い合わせを行うための問い合わせ文です。SQLであればselect文に相当するものと考えてください。検索エンジンの検索式はSQLのように標準的なものがないため、それぞれの検索エンジンに固有の検索式の形式があります。FINDSPOTでも独自の検索式を用いています。

FINDSPOTの検索式を設計する上で考慮したのは、なるべくシンプルに検索要求が表現できるという点です。また、検索式を解析するパーサが高速に処理できるようにというのも特に考慮した点です。検索式の構文は、エンドユーザが検索エンジンに触れる入り口ともいえます。半角文字、全角文字をあまり区別せず使えた方が、利用者の負担は少なくなります。後述する検索式の予約語である、空白文字、"(ダブルクオート), AND, NOT, ORなどは半角文字だけではなく、全角文字でも処理できるようにするといった工夫も施しています。

では、検索機能の紹介を兼ねながら、FINDSPOTの検索式とその実現方法について説明していきましょう。

文字列

文字列検索は、全文検索エンジンにとっては何と言っても一番の柱です。FINDSPOTで文字列を検索するには、検索エンジンに対して、単に文字列を指定します。文字列に空白文字を含んでいる場合や、後述する演算子などの予約語を文字列として検索するには"(ダブルクオート)で囲みます。ダブルクオートを文字列中に含める場合には、\"のように\(バックスラッシュ)を前につけます。また、バックスラッシュを文字列中に入れる場合には\\のようにします。

例:

文字列検索は、これまでに解説してきたようにN-gramの方式を用いて実現しています。

AND条件

全文検索では、単一の文字列だけではなかなか目的の情報に辿り着けません。そこで複数の文字列を指定して、それらの文字列を全て含む文書を検索することが多いことと思います。FINDSPOTで複数の文字列をすべて含む文書を探す場合には、空白記号で区切って文字列を複数指定します。

例:

この時、文字列を区切った空白記号は論理的にとらえると論理積の条件を指定したことになります。FINDSPOTでは、論理積の条件をANDという演算子を用いて明示することもできます。上記の例でANDの演算子を明示すると次のようになります。

例:

FINDSPOTでは空白記号は暗黙にANDの演算子を指定したものとして扱っていますので、AND演算子を指定した場合も、省略した場合も検索結果は同じになります。

では、ANDの左右に指定された文字列を両方含む結果を得るには、どのようにしたら良いでしょうか。FINDSPOTでは検索結果を文書集合として扱っています。AND条件はこの文書集合どうしの論理積の集合演算として実現しています。

たとえば「織田信長 AND 豊臣秀吉」という検索式を考えてみましょう。まず、⁠織田信長」という文字列を検索して検索結果である文書集合を得ます。次に、⁠豊臣秀吉」という文字列を検索して検索結果である文書集合を得ます。そして、2つの文書集合どうしを比較して、両方に存在する文書を探して、結果である文書集合を求めます。これが、FINDSPOTでのAND演算子の実現方法です。

⁠織田信長 AND 豊臣秀吉 AND 徳川家康」のようにAND条件が複数指定された場合には、始めに「豊臣秀吉 AND 徳川家康」の答えである文書集合を求めて、次に織田信長の検索結果の文書集合との間で、再度ANDの集合演算を行います。

文書集合

ここで「文書集合」という概念が出てきました。文書集合はFINDSPOTのしくみを理解するのに欠かせない概念なので、もう少し詳しく解説しましょう。

FINDSPOTの全文検索インデックスの中には、連載第5回で解説したように、文書IDとN-gramの文字列素の文中での出現位置情報が入っています。

N-gramによる文字列の検索結果として、文書IDと、文字列の文中での出現位置が得られます。同じ文書中に検索文字列が複数箇所に出現することがあるので、検索結果は文書ごとにいったん次のように集計を行います。

  • 文書ID
  • 文中での出現位置(複数出現した場合には一番文頭に近い位置)
  • 文中での出現回数
  • 検索結果のソート用のキー情報(複数)

これが1つの文書に対する検索結果です。この情報をFINDSPOTでは「ヒットユニット」という名前で呼んでいます。文中での出現位置の情報をヒットユニットに入れているのは、検索結果の一覧を表示する際に、文書中のヒットした箇所の近傍を表示するためです。また、文中での出現回数や、ソート用のキー情報は、検索結果を表示する際の表示順を決定するのに用います。

文書集合はヒットユニットを複数集めたものになっています。文書集合は別の文書集合との間で、AND(論理積)の集合演算ができる他、OR(論理和)、NOT(否定)などの集合演算ができるしくみになっています。

非常に複雑な検索式で検索を行う場合には、検索式の部分部分の文書集合が大きいと、それだけ検索エンジンにかかる負荷が大きくなり、検索時間もかかってしまいます。検索式のチューニングを行う場合には、この文書集合の大きさに着目して、文書集合がなるべく小さくなるように検索式を工夫すると効率の良い検索が行えます。

検索式の最適化は大きなテーマなので、別の機会に詳しく解説したいと思います。

おすすめ記事

記事・ニュース一覧