第4回　転置索引の詳細

前回は転置索引の概要を説明しました。今回は転置索引をもう少し詳しく見ていきます。

転置索引＝辞書＋転置リスト

転置索引は大きく分けて2つの部分から構成されています。文書に出現する単語のリストである「辞書」と、その辞書にある各単語がどの文書に出現するかを表したポスティングリストの集合の「転置リスト」からなります（図1⁠）⁠。ポスティングリストやポスティングに関しては前回簡単に説明しましたが、図を見て再度確認してください[1]⁠。

辞書は単語だけでなく、その単語に対応するポスティングリストの位置情報を含んでいます。よって、辞書を探索することで、該当する単語のポスティングリストを取り出すことが可能となります。

一方、ポスティングリストは、どの文書に出現するかを表すのに最低でも文書のID（数値）が必要となります。書籍の場合は、文書はページなのでページ番号が文書IDとなります。（⁠書籍の索引は、単語とページ番号のリストの対応付けを行う）

文書にどうやってIDを付与するかは、現段階では出現した順に1から振っていくことにしましょう。前回作成した転置索引（第3回の表4）を見ると、文書1をD1と表現していました。これは文書IDが1であるということを示しています。これら辞書と転置リストを実際どのようなデータ構造で格納し、どう表現するかは、次回に説明したいと思います。

リスト1　転置索引の例（第3回の表4の後の例を再掲)

engine: D1
Google: D2
I: D1,D2
in: D2
keywords: D2
like: D1
search: D1,D2

ブーリアン検索

前回作成した転置索引（リスト1）を見ると、「⁠search」というキーワードが文書1（D1）と文書2（D2）に含まれていることがわかります。また、同様に「engine」というキーワードは文書1（D1）に含まれていることもわかります。よって、「⁠search」と「engine」の両方のキーワードが含まれる文書は文書1（D1）であるということになります。

このように検索する方法を、「⁠ブーリアン検索（Boolean Retrieval⁠）⁠」といいます。「⁠ブーリアン」と付くのは、以下のように論理演算子（ブーリアンオペレータ）のAND、OR、NOTを使って適合する文書を探し出すからです。

AND：両方とも含む（論理積）
OR：どちらか一方を含む（論理和）
NOT：含まない（否定）

上の例では、両方とも含む場合を検索してるので "search AND "engine" を検索したことになります（⁠「⁠search」か「engine」の少なくともどちらか一方を含む文書がほしい場合は、"search OR engine" となります⁠）⁠。

"search AND engine" に該当する文書を探し出すためには、"search" に対応するポスティングリストと、"engine" に対応するポスティングリストの両方を取り出し、各ポスティングリストの共通部分を探すことにより可能となります。

現在の主流となる検索エンジンは、このような検索方法がベースとなっています[2]⁠。また、どう検索を行うかという仕組みのことを検索モデルと呼び、ブーリアン検索を行う仕組みはブーリアンモデルと呼ばれます。

文書レベルと単語レベルのポスティングリスト

今まで見てきたリスト1のようなポスティングリストは、文書に単語が出現したか否かという情報しか持っていませんでした。このようなポスティングリストを、文書レベルのポスティングリスト（Document-level inverted list）といいます。

文書レベルの情報に加えて、単語が文書中のどこに出現するか(先頭から何単語目か)という情報を含んだポスティングリストのことを、単語レベルのポスティングリスト（Word-level inverted list）といい、各ポスティングをDocID:offset1,offset2... のように表現します。

たとえば、前回の例で使用した2つの文章の場合、

文書1(D1): I like search engines.
文書2(D2): I search keywords in Google.

単語"search"に対応するポスティングリストは、

search: D1:3,D2:2

のようになります（文書1(D1)の先頭から3つ目と、文書2(D2)の先頭から2つ目に出現するため⁠）⁠。よって、各キーワードにおける単語レベルのポスティングリストはリスト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"が同じ文書にあるということしかわかりませんでした。これだと、結果の文書が「検索エンジン」（⁠search engine）に関して言及しているかは確かではありません。たとえば、"I search for gas station because the car engine doesn't start." という文書も、"search AND engine" でマッチしてしまいます。

そこで単語レベルの転置リストを使うことで、"search engine" というフレーズが検索可能となります。（⁠※3）文書レベルでの場合と同様に"search"と"engine"で辞書を検索し、それぞれのポスティングリストを取得します。そして、それらに対して、"search"と"engine"が隣り合って出現しているかをチェックすることによりフレーズの存在の有無を確認します。上の例だと、"search"と"engine"は両方とも文書1に出現していて、"search"が3単語目、"engine"が4単語目に出現しているので、"search engine"というフレーズが文書1に出現していることがわかります。（⁠※4）

まとめ

転置索引の構成と転置リストの内部構成について見てきました。これらの知識は今後も読み進める上でも非常に重要となるので、ぜひ覚えてください。次回は、転置索引の実装について説明していきます。

参考文献: [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