「Introduction to Information Retrieval」[1]の第一章[2008-01-12-1]
の転置インデックスまわりの用語と検索手順などの解説です。
ちょっと前に書いた
『ウェブ検索を「本の索引」で説明する試み』[2007-06-17-6]
という記事の続きでもあります。
「転置インデックスによる検索システムを作ってみよう！」
[2007-11-26-5]もご参考に。
§
転置インデックス (inverted index または inverted file) は、
dictionary と postings の二つの部分から構成されます。
dictionary は索引語 (term) の集合です。
term が登場する文書の ID を posting と呼びます。
ある term の posting のリストが postings list (または inverted list)、
postings list の集合が postings と呼ばれています[1]
（posting と postings がちょっとややこしいのですが、
IIR[1]の記述に従いました）。
これらの関係を図に示しました。
MIR[2]では、dictionary を vocabulary、
postings を occurrences と呼ばれています。
特に「正しい」名称はないのでしょうね。
一般的な実装では、dictionary をメモリ展開し、
postings を外部ファイルとすることで、効率化が図られています。
この転置インデックスをベースに、
AND, OR, NOT のオペレータを用いたブーリアン検索 (boolean retrieval)
について解説します。
「恵比寿 AND ビール」は「恵比寿」と「ビール」の
両方を含む文書を検索するクエリーです。
処理は、まず「恵比寿」「ビール」の postings list を取り出して
それぞれの先頭にポインタを置き、
ポインタが指す posting 同士を比較しながらポインタを進め（posting
が小さい側のポインタを進めることを繰り返す）、
一致した posting だけを取り出す、というものです。
例では、1, 47, 209 が取り出せます。
「恵比寿 OR ビール」は「恵比寿」か「ビール」のどちらかまたは両方が
含まれている文書を検索するクエリーです。
それぞれの postings list を posting を重複しないようにマージすることで
適合する文書を取り出します。
「恵比寿 AND NOT スイーツ」は「恵比寿」を含むが「スイーツ」は含まない
文書を検索するクエリーです。
これもAND検索と同様にそれぞれのポインタが指す posting 同士を
比較しながらポインタ進めます。このとき「スイーツ」の posting に
一致しない「恵比寿」の posting のみを取り出します。
例では、1, 2, 47, 209 が取り出せます。
なお、これらの処置を効率的に行うために、転置インデックス構築時には、
各 postings list の posting は ID 順に格納しておくことが望まれます。
参考文献：
[1] Christopher D. Manning, Prabhakar Raghavan and Hinrich Schu"tze:
Introduction to Information Retrieval, Cambridge University Press, 2008.
(http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html)
[2] Ricardo Baeza-Yates, Berthier Ribeiro-Neto:
Modern Information Retrieval, Addison Wesley, 1999.
（間違いや補足などありましたら下記フォームからご連絡頂けると幸いです）
の転置インデックスまわりの用語と検索手順などの解説です。
ちょっと前に書いた
『ウェブ検索を「本の索引」で説明する試み』[2007-06-17-6]
という記事の続きでもあります。
「転置インデックスによる検索システムを作ってみよう！」
[2007-11-26-5]もご参考に。
§
転置インデックス (inverted index または inverted file) は、
dictionary と postings の二つの部分から構成されます。
dictionary は索引語 (term) の集合です。
term が登場する文書の ID を posting と呼びます。
ある term の posting のリストが postings list (または inverted list)、
postings list の集合が postings と呼ばれています[1]
（posting と postings がちょっとややこしいのですが、
IIR[1]の記述に従いました）。
これらの関係を図に示しました。
MIR[2]では、dictionary を vocabulary、
postings を occurrences と呼ばれています。
特に「正しい」名称はないのでしょうね。
一般的な実装では、dictionary をメモリ展開し、
postings を外部ファイルとすることで、効率化が図られています。
この転置インデックスをベースに、
AND, OR, NOT のオペレータを用いたブーリアン検索 (boolean retrieval)
について解説します。
「恵比寿 AND ビール」は「恵比寿」と「ビール」の
両方を含む文書を検索するクエリーです。
処理は、まず「恵比寿」「ビール」の postings list を取り出して
それぞれの先頭にポインタを置き、
ポインタが指す posting 同士を比較しながらポインタを進め（posting
が小さい側のポインタを進めることを繰り返す）、
一致した posting だけを取り出す、というものです。
例では、1, 47, 209 が取り出せます。
「恵比寿 OR ビール」は「恵比寿」か「ビール」のどちらかまたは両方が
含まれている文書を検索するクエリーです。
それぞれの postings list を posting を重複しないようにマージすることで
適合する文書を取り出します。
「恵比寿 AND NOT スイーツ」は「恵比寿」を含むが「スイーツ」は含まない
文書を検索するクエリーです。
これもAND検索と同様にそれぞれのポインタが指す posting 同士を
比較しながらポインタ進めます。このとき「スイーツ」の posting に
一致しない「恵比寿」の posting のみを取り出します。
例では、1, 2, 47, 209 が取り出せます。
なお、これらの処置を効率的に行うために、転置インデックス構築時には、
各 postings list の posting は ID 順に格納しておくことが望まれます。
参考文献：
[1] Christopher D. Manning, Prabhakar Raghavan and Hinrich Schu"tze:
Introduction to Information Retrieval, Cambridge University Press, 2008.
(http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html)
[2] Ricardo Baeza-Yates, Berthier Ribeiro-Neto:
Modern Information Retrieval, Addison Wesley, 1999.
（間違いや補足などありましたら下記フォームからご連絡頂けると幸いです）