検索エンジンはいかにして動くのか?
第4回 転置索引の詳細
前回は転置索引の概要を説明しました。今回は転置索引をもう少し詳しく見ていきます。
転置索引=辞書+転置リスト
転置索引は大きく分けて2つの部分から構成されています。文書に出現する単語のリストである
辞書は単語だけでなく,
一方,
文書にどうやってIDを付与するかは,
リスト1 転置索引の例
engine: D1
Google: D2
I: D1,D2
in: D2
keywords: D2
like: D1
search: D1,D2
- ※1)
- 本によっては,
ポスティングやポスティングリスト, 転置リストなどの使い方が異なるかもしれませんが, 本連載では多くの論文や書籍での使い方に習って図1のように呼ぶことにします。
ブーリアン検索
前回作成した転置索引
このように検索する方法を,
- AND:両方とも含む
(論理積) - OR:どちらか一方を含む
(論理和) - NOT:含まない
(否定)
上の例では,
"search AND engine" に該当する文書を探し出すためには,
現在の主流となる検索エンジンは,
- ※2)
- 検索エンジンでは,
ブーリアン検索により検索を行い, その結果を何らかの基準 (スコア, 日付など) で並び換え, その結果をユーザに提示することが多いと思います。
文書レベルと単語レベルのポスティングリスト
今まで見てきたリスト1のようなポスティングリストは,
文書レベルの情報に加えて,DocID:offset1,offset2...
のように表現します。
たとえば,
文書1(D1): I like search engines.
文書2(D2): I search keywords in Google.
単語"search"に対応するポスティングリストは,
search: D1:3,D2:2
のようになります
リスト2 単語レベルで作成したポスティングリスト
engine: D1:4
Google: D2:5
I: D1:1,D2:1
in: D2:4
keywords: D2:3
like: D1:2
search: D1:3,D2:2
このような単語の位置情報は,
フレーズ検索
文書レベルの転置リストでは"search"と"engine"が同じ文書にあるということしかわかりませんでした。これだと,
そこで単語レベルの転置リストを使うことで,
- ※3)
- 文書レベルの転置リストであっても,
各単語を検索した後に, "search engine"というフレーズを元文書から探索すれば, フレーズを検索することは可能となります。しかし, この方法は通常は効率的ではありません。 - ※4)
- 念のためですが,
フレーズ検索とブーリアン検索は同列ではありませんのご注意ください。ブーリアンモデルにおけるひとつの検索方法にフレーズ検索があるということで, たとえば, "search engine" AND "google"のようなブーリアン検索では"search engine"はフレーズ検索する必要であるということです。
まとめ
転置索引の構成と転置リストの内部構成について見てきました。これらの知識は今後も読み進める上でも非常に重要となるので,
- 参考文献
- [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
この記事に関連する書籍
-
検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏
まいにち使っている検索エンジンがどうやって動いているか,知っていますか? 本書では,小さな検索エンジンを作りながら,ソースコードレベルで検索エンジンのしくみ...