転置インデックス

転置インデックスは、語、文字列断片などの検索語から、その語を含む文書IDや行IDの一覧であるポスティングリストを引けるようにした索引です。全文検索や情報検索の基本構造です。

■ 試験で押さえるポイント

• 通常の順方向表現が文書→含まれる語であるのに対し、転置索引は語→文書集合へ向きを逆転します。語の出現位置や頻度も保持すればフレーズ検索とランキングに使えます。

• 問合せ語A AND Bは両ポスティングリストの共通部分、A OR Bは和集合、A NOT Bは差集合として高速に求められます。

• 作成時には文書をトークン化し、大文字小文字、活用形、ストップワードなどを正規化します。日本語では形態素解析又はn-gram方式の選択が検索結果へ影響します。

• 文書追加・削除時はポスティングリストを更新するため、即時更新と索引統合のコストがあります。B-treeの前方一致だけでは任意位置の全文語検索を効率化しにくい点が用途差です。

■ 選択肢での判断ポイント

検索語から文書一覧を引く構造、全文検索、AND/ORの集合演算が手掛かりです。文書ごとに語一覧を持つ順方向索引と向きを取り違えません。

例: 『DB』→{文書1,3,8}、『索引』→{文書2,3,8}なら、『DB AND 索引』は共通部分{文書3,8}として求められます。