はじめに

前回は、メモリとディスクを使って転置索引を効率的に構築する方法について説明しました。今回は、具体的な検索処理について見ていきます。

検索の流れ

転置索引における一般的な検索処理の流れは、以下のようになります。

1. クエリ中の各タームのポスティングリストを取得
2. ブーリアン（Boolean）検索によりマッチした文書IDの取得
3. マッチした各文書とクエリの適合度計算またはソート属性値の取得
4. 適合度 または 属性値により並び換え
5. 上位k件（通常10件～100件）を返す

これを疑似コードとして書くと、リスト1のようになります。

 1: sort Q by the length of each term's posting list
 2: t = shift Query
 3: posting_list = FetchList(term)
 4: for all t ∈ Q do
 5:   t = shift Query
 6:   posting_list = Intersect(posting_list,t)
 7: end for
 8: array = NewArray()
 9: for all Di ∈ DocIDs(posting_list) do
10:   arrayi =CalcRelevancy(Q,Di) or GetAttribute(Di)
11: end for
12: HeapSortK(array)
13: Identify the k greatest arrayi values and return the corresponding documents.

説明のため、各タームがANDで接続されたブーリアンクエリ（T_1 AND T_2 AND ... T_N）クエリであることを想定しています。

1行目では、クエリ中のタームに対応するポスティングリストの長さの昇順にソートしています。これは、論理積集合を取る場合はリストが短い方から処理していく方が比較回数や使用するメモリ量が少なくなるという理由からです。

2～3行目では、クエリの最初のタームを取り出し、そのタームに対応する（最も短い）ポスティングリストを取得しています。

4～7行目では、残りのタームとの論理積集合を取り、すべてのタームを含むようにポスティングリストを絞り込んでいきます。

8～11行目では、最終的に求められたポスティングリストの各文書とクエリとの関連性を求め配列に格納しています（または、日付などの属性で結果を並び換える場合は、各文書ごとに属性値を求めます⁠）⁠。

12～13行目では、関連度や属性値の順に並び替えをし、上位K件を返しています[1]⁠。

現在の検索エンジンは、基本的にはこのようなアルゴリズムで検索処理をしています。また、今回はANDクエリでの疑似コードを示しましたが、他のブーリアンオペレータの場合も同様の処理となります[2]⁠。

関連度によるランキング

全文検索では、関連度を計算して並び変える場合が多くあります（属性値で並び変える場合もそれ以上に多いかもしれませんが⁠）⁠。では、文書とクエリの関連度とはいったいどのようにして求めるのでしょうか？ ここでは、関連度計算に使われる統計値と、代表的な関連度指標を簡単に紹介したいと思います。

まず、関連度計算には主に以下のような統計値が使われます。

代表的な関連度指標には、コサイン類似度（cosine similarity）やOkapi BM25などがあります。具体的な計算式や詳細はここでは省略しますが、上記の値を組み合わせて、関連度を計算します[3]⁠。

コサイン類似度は、文書とクエリをタームを次元としたベクトル空間にマップし、文書ベクトルとクエリベクトルの成す角度により、文書とクエリの関連度（類似度）を求めます（成す角度が小さければ関連度が高い⁠）⁠。またOkapi BM25は、文書がクエリに対して適合かどうかは確率的に決定されるという統計的な原理に基づき、文書とクエリの関連度を求めます。

検索時にこれらを計算するには、索引の構築時に上記の統計値を計算し保持しておく必要があります。実装にはさまざまな方法が考えられますが、たとえばf_d,tはポスティングリストの中に埋め込んでおき[4]⁠、f_tやF_tは辞書と一緒に保存しておくといった方法が考えられます（f_q,tは検索時に検索でき、その他の値は構築時にカウントし、別の領域に保存しておきます⁠）⁠。

情報検索とは

話が若干唐突に感じるかもしれませんが、関連度の話に触れたので、情報検索について簡単に説明しておこうと思います。

“全文検索⁠”や“⁠検索エンジン⁠”は、学術的には情報検索という分野の技術やシステムとなります。Wikipediaによると"情報検索"とは、

情報検索とは、コンピュータを用いて大量のデータ群から目的に合致したものを取り出すこと

となります。 つまり、大量のデータ群（文書）から目的（クエリ）に合致した結果を取り出すことを言い、検索エンジンが行うべきタスクそのものとなります。

本来、情報検索においては目的に合致した文書であれば良く、クエリを必ずしも含んでいる必要はないと考えられています。つまり、クエリを含んでいようがいまいが、クエリと文書との関連度を求め、その関連度が高い順に結果を提示してあげれば良いのです（ユーザは自分が指定したクエリに関連した文書であれば良いという意味です⁠）⁠。この処理を疑似コードで表すと、リスト2のようになります（関連度はコサイン類似度の例となります⁠）⁠。

 1: Calculate term vector wq,t for each query term t in Query
 2: for all d ∈ Documents do
 3:   Sd ← 0
 4:   for all t ∈ Query do
 5:     Calculate document vector wd,t
 6:     Sd ← Sd ＋ wq,t ・ wd,t
 7:   end for
 8:   Wd =CalcDocumentLength(d)
 9:   Sd ← Sd/Wd
10: end for
11: Identify the k greatest Sd values and return the corresponding documents.

この方法でも全く問題ありませんが、この方法では全文書とクエリとの関連度を求めるため、対象とする文書が増えるに従い検索処理コストが増大してしまいます。

よって、クエリ中のタームを1つでも含む文書だけを対象とし、関連度を計算することにより、検索処理コストを小さくしてあげることができます。 ここで、タームを含むかどうかを判定するために索引が使われます。この処理を疑似コードで表すとリスト3のようになります（同様に関連度はコサイン類似度の例となります⁠）⁠。

 1: Allocate an accumulator Ad for each document d and set Ad ← 0
 2: for all t ∈ Query do
 3:   Calculate term vector wq,t
 4:   list = FetchList(t)
 5:   for all (d,fd,t) ∈ list do
 6:     Calculate document vector wd,t
 7:     Ad ← Ad ＋ wq,t ・ wd,t
 8:   end for
 9: end for
10: Wd =Length(d)
11: Ad ← Ad/Wd for each Ad
12: Identify the k greatest Ad values and return the corresponding documents.

リスト3の検索アルゴリズムに対して、すべてのクエリを含む文書のみを対象としたアルゴリズムが、一番最初に紹介したリスト1になります。

このように、検索と一言で言っても、さまざまなアルゴリズムが考えられます。これらのアルゴリズムは、対象とする文書の性質やシステムの仕様により選択されます。通常は、リスト3やリスト1に示した検索アルゴリズムが使われることが多く、現在のGoogleやYahoo!などのWeb検索エンジンでは、リスト3に示した検索アルゴリズムをベースにしていると想像できますし[5]⁠、一般的なWebサービスにおける検索ではリスト1のアルゴリズムが使われていることが多いと思います。

検索エンジンを開発する際は、これらのことにも配慮する（使い分けられるようにするなどの）必要があります。

まとめ

今回は、転置索引における検索処理について説明しました。検索処理が非常にシンプルなアルゴリズムであることが理解できたかと思います。 また、検索結果を提示する際の基準となる関連度について簡単に触れました。関連度により、より柔軟にクエリの意図に合致する検索結果を返すことができます。

参考文献

[1] Inverted files for text search engines, Justin Zobel, Alistair Moffat, ACM Computing Surveys (CSUR), 2006

[2] Introduction to Information Retrieval, C. D. Manning, P. Raghavan, H. Schutze , Cambridge University Press, 2008