検索についていろいろウェブから拾ってきてまとめたメモ
検索についていろいろウェブから拾ってきてまとめたメモ
転置索引において，単語と文書の対応付けの情報をポスティング（またはポインタ）と呼びます。
各単語におけるポスティングの列のことをポスティングリストと呼びます。
http://gihyo.jp/dev/serial/01/search-engine/0004
転置索引は大きく分けて2つの部分から構成されています。
文書に出現する単語のリストである「辞書」と，
その辞書にある各単語がどの文書に出現するかを表したポスティングリストの集合の「転置リスト」からなります（図1）。
辞書は単語だけでなく，その単語に対応するポスティングリストの位置情報を含んでいます。
よって，辞書を探索することで，該当する単語のポスティングリストを取り出すことが可能となります。
ブーリアン検索
論理演算子（ブーリアンオペレータ）のAND，OR，NOTを使って適合する文書を探し出す
検索エンジンでは，ブーリアン検索により検索を行い，
その結果を何らかの基準（スコア，日付など）で並び換え，その結果をユーザに提示することが多い
文書に単語が出現したか否かという情報
⇒ 文書レベルのポスティングリスト（Document-level inverted list）
文書レベルの情報に加えて，
単語が文書中のどこに出現するか(先頭から何単語目か)という情報を含んだポスティングリスト
⇒ 単語レベルのポスティングリスト（Word-level inverted list）といい，
各ポスティングをDocID:offset1,offset2... のように表現します。
フレーズ検索
単語レベルの転置リストを使うことで，"search engine" というフレーズが検索可能となります。
"search"と"engine"が隣り合って出現しているかをチェックすることによりフレーズの存在の有無を確認します。
http://gihyo.jp/dev/serial/01/search-engine/0005
B+木
B+木はB木から派生したデータ構造
全てのレコードは木の葉ノード（leaf node）に格納され，
内部ノード（internal node）にはキーのみが格納される木構造
B+木は，各ノードをページと呼ばれる単位で管理し，
通常はそれをファイルシステムのブロックサイズの定数倍にします。
大規模な辞書をブロックデバイス上で扱う場合は，B+木を利用することで効率的に管理することができます。
http://gihyo.jp/dev/serial/01/search-engine/0005?page=2
転置リストは，各単語におけるポスティングリストの集まり
これらは通常辞書とは別の領域（ファイル）に保存されます。
各リストは隣りあって格納され，辞書がそのリストへの（オフセットなどの）位置情報を保持しているという構造
辞書：メモリ or ディスク上
ポスティングリスト：ディスク上
ポスティングリストの圧縮
転置リストを構成する各ポスティングリストは，検索したい文書数が増えるほど長くなります。
よって，中規模以上の文書におけるポスティングリストでは，
その取得におけるディスクI/Oが検索処理において非常に大きな比重を占めてしまいます。
この問題に対処するために，通常ポスティングリストは圧縮して格納され，ディスクI/Oの削減を図ります。
ポスティングリストは整数列となるため，整数列に向いた圧縮手法が用いられます。
http://gihyo.jp/dev/serial/01/search-engine/0006
文を単語や文字の並びに分割する方法
日本語のように単語が空白で区切られていない文を単語に分割するには，大きく分けて以下の2つの方法があります
１．形態素解析による分割
２．N-gram（q-gram）による分割
１．形態素解析による分割
形態素解析（Morphological Analysis）とは，
文を言語で意味を持つ最小単位の"形態素"の列に分割し，それぞれの品詞を判別すること
２．N-gram（q-gram）よる分割
N-gramとは文字のN文字の部分列のことを指し，Nには2や3などの数値が入ります
N-gramによる分割とは，文を単語の境界とは関係なくN文字ずつに分割することを言います。
「全文検索エンジン」を2-gram（bi-gram）で分割した場合は，
「全文」「文検」「検索」「索エ」「エン」「ンジ」「ジン」となります。
■形態素解析による転置索引の利点と欠点
利点は，文に対して辞書に登録するターム数が少なくなることから，
N-gramに比べて辞書，転置リストのサイズが小さくなり，また構築処理，検索処理も速くなります。
欠点は，検索漏れが生じてしまうことになります。
検索漏れとは，実際にクエリが文に含まれているにもかかわらず，見つけられないことを言います。
■N-gramによる転置索引の利点と欠点
利点は，形態素解析の場合と異なり，検索漏れが発生しないことです。
これは，N-gramではすべての文字部分列をタームとして登録するため，
検索キーワードが文章に含まれていれば必ず見つけることができます。
欠点としては，上記のことから，辞書のサイズ，転置リストのサイズが大きくなってしまい，
構築処理・検索処理が形態素解析の場合と比べて少しだけ遅くなってしまいます。
日本語文書における転置索引の実装
現代の検索エンジンは，文の分割方法に依存しないように設計されることが多い
http://gihyo.jp/dev/serial/01/search-engine/0007
ディスクベースの構築方法
多くの場合，転置索引は実メモリよりも大きくなります
ディスクベースの構築方法
今回はSort-based InversionとMerge-based Inversionと呼ばれる2つの方法
■構築方法の種類
転置索引の構築には，大きく分けて以下の2種類の構築方法があります。
静的な構築方法（offline index construction, offline approarch）
動的な構築方法（online index construction, online approarch）
Web上のニュースやブログなどの場合，新しい記事は古い記事よりも重要度が高い
そのような場合には動的な構築方法が選ばれます。
http://gihyo.jp/dev/serial/01/search-engine/0008
検索の流れ
１．転置索引における一般的な検索処理の流れは，以下のようになります。
２．クエリ中の各タームのポスティングリストを取得
３．ブーリアン（Boolean）検索によりマッチした文書IDの取得
４．マッチした各文書とクエリの適合度計算またはソート属性値の取得
５．適合度 または 属性値により並び換え
６．上位k件（通常10件～100件）を返す
関連度によるランキング
文検索では，関連度を計算して並び変える場合が多くあります
代表的な関連度指標には，コサイン類似度（cosine similarity）やOkapi BM25などがあります。
