検索エンジンはいかにして動くのか?

第3回 転置索引とは何か?

この記事を読むのに必要な時間:およそ 2 分

転置索引の実際の表現方法

転置索引の概念はわかったと思います。しかし,実際の転置索引では,単語が文書に出現する情報を0/1で表現するわけではありません。多くの文書を扱う場合,転置索引は非常に大きくなり,表にした場合にほとんどのマスは0になる(疎な表になる)ので,以下のようなより空間効率の良い形式で表現します。

先に挙げた表の例で,本の索引と違うと思った方もおられるかと思いますが,このように実際は本の索引と同様の表現形式で表します。以下に先ほどの例における(正式な)転置索引を示します。

エンジン: P1,P2
解説: P1
検索: P1,P2
索引: P2
転置: P2
連載: P1

なお,表を実際に0/1で表現する場合もあり,その形式はビットマップ(bitmap)と呼ばれており転置索引とは区別されます。しかし,空間効率が悪く大規模な索引に向かないため,現在はあまり使われていません。

転置索引を作ってみる

今度は以下の英語の文書に対して,実際に転置索引を作ってみましょう。

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

まず,前回と同様に文書→単語の関係を表にします(表3⁠⁠。

表3

 IlikesearchengineskeywordsinGoogle
D11111000
D21010111

そして,表3を転置したもの(表4)と転置索引は以下のようになります。

表4

 D1D2
engines10
Google01
I11
in01
keywords01
like10
search11
engine: D1
Google: D2
I: D1,D2
in: D2
keywords: D2
like: D1
search: D1,D2

これで,上の文書における転置索引が完成しました。書籍での例とは異なり,文書で出現した単語すべてに対して対応付けを行ったので,この索引により文書に出現するいかなる単語でも検索できます。

なお、実際に文書から転置索引を構築する場合は、上記のようにいったんビットマップを構築することはしませんのでご注意ください。説明の都合上このようなステップとなりました。実際の構築方法は後の回で紹介したいと思います。

転置索引における語句

転置索引において,単語と文書の対応付けの情報をポスティング(またはポインタ)と呼びます。英語ではposting(pointer⁠⁠,複数ある場合はpostings(pointers)となります。また,各単語におけるポスティングの列のことをポスティングリストと呼びます。今後の説明でこれらの語句を使いますので,ぜひ覚えてください。

まとめ

今回は,全文検索エンジンにおける転置索引という索引構造について解説しました。論理的にではありますが,その構築方法と構造は理解できたと思います。次回は,この転置索引についてもう少し深く見ていきます。

著者プロフィール

山田浩之(やまだひろゆき)

日本IBM株式会社を経て,ヤフー株式会社等で検索エンジンの開発に従事。現在は大学院でデータベース・情報検索の研究を行う。また,オープンソースで全文検索エンジンLuxやデータベースマネージャLux IOの開発を行っている。