検索エンジン自作入門 – 検索エンジンはいかにして動くのか（３）

辞書の実装

辞書（もくじ）は素早く検索したいため、ハッシュや木構造などのデータ構造を用いて、一次記憶装置に格納します。

転置リストの実装

転置リスト（ポスティングリスト）は辞書に比べて、大きいデータ量になるため、二次記憶装置に格納します。
この転置リストには前回のエントリーで触れた単語の位置情報の他にも単語の出現数（TF：Term Frequency）も格納され、検索結果のランキング処理などに用いられます。
例えば、「文書ID_A:出現数:位置情報1:位置情報2:位置情報3:…位置情報x,文書ID_x…」となり、以下のようになります。

他にも必要であれば日付などの情報を持たせたりします。

ブーリアン検索

検索キーワードの全てが含む検索方法のことをAND検索などと呼びますが、この論理演算子（ANDやORやNOT）を用いた検索のことをブーリアン検索と呼びます。
また、論理演算子のことをブーリアンオペーレータ、ブーリアン検索を行う検索モデルのことをブーリアンモデルと呼びます。

転置インデックス用いた検索処理の流れ

転置インデックス用いたAND検索の処理は、次のような流れになります。

1. ポスティングの比較回数をできるだけ少なくするために「検索キーワード」を「ポスティングリスト」にある「ポスティング」の件数の「昇順」に並び替えます。
   例えば、検索キーワードが「search engine」の場合は、「engine search 」に並び替えます。

   engine	P1:4	件数
   Google	P2:5	1件
   I	P1:1,P2:1	2件
   in	P2:4	1件
   keyword	P2:3	1件
   like	P1:2	1件
   search	P1:3,P2:2	2件

2. 「検索キーワード」を１件取り出して、その「ポスティングリスト（１）」を取得します。
   例えば、検索キーワードが「engine search」の場合は、「engine」のポスティングリストを取得します。

   engine

   P1:4

3. （※）その次の「検索キーワード」を１件取り出して、その「ポスティングリスト（２）」を取得する
   例えば、検索キーワードが「engine search」の場合は、「search」のポスティングリストを取得します。

   search

   P1:3,P2:2

4. 「ポスティングリスト（１）」と「ポスティングリスト（２）」の両方にポスティングが含むポスティングリストを新しく作成します。
   このとき、新しく作成したポスティングリストは「ポスティングリスト（１）」へ格納します。

   P1:3,P1:4

5. 他にも「検索キーワード」がある場合は（※）の処理へ戻ります。
6. 作成した「ポスティングリスト（１）」のデータをランキング処理やソート処理にかけます。
7. 「ポスティングリスト（１）」を検索結果として表示します。

I like search engines.

関連度の計算方法

ウェブ検索において、検索結果のランキング処理やソート処理には、コサイン類似度やOkapi BM25などが用いられます。

ベクトルのなす角 – Wikipedia
Okapi BM25 – Wikipedia

情報検索における検索

全文検索の学術分野においては、検索キーワードが含んでいない文章だとしても、キーワードとの関連度が高い場合には、その文章を検索結果に表示することがあります。
その際に検索処理のコストを抑えるため、指定のキーワードが１つだけは含む文章に絞り込んでいたりします。