はじめに

前回までは、検索エンジンの概要を見てきました。今回からは、全文検索の中核となる索引構造について見ていきます。

第1回の復習になりますが、全文検索には主に2種類の方法がありました。検索したいデータに対して前処理をせず、検索時に文書を走査するgrep型と、あらかじめ索引を作っておいて検索時にその索引を利用する索引型です。今回から数回にわたり、索引型において最も普及している転置索引という索引構造について解説していきます。

転置索引とは

さて、転置索引とは何なのでしょうか？

身近な所で例にあげると、書籍（専門書など）の巻末にある索引は、本における転置索引といえます。巻末には通常、キーワード（単語）とそのキーワードが出てくるページが記載されています。キーワードはアイウエオ順やアルファベット順に並べられているので、探したいキーワードを簡単に見つけることができ、そのキーワードがどのページで言及されているかが一発でわかります。この本の索引がまさに転置索引であり、見つけたいキーワードを索引から探す処理が検索処理そのものなのです。

次に疑問になりそうなポイントは「転置」という言葉だと思います。何が転置するのでしょうか？

たとえば、ある書籍のページとそこに書かれている内容が、以下のようになっていたとします。

ページ1（P1）: この連載では検索エンジンについて解説します。
ページ2（P2）: 転置索引は検索エンジンの重要な要素です。

表1は、この書籍のページとそのページに出てくる（メインとなる）キーワードの関係を表にしたものです。

この表は左から右にしか見られないと思ってください。つまりこの表からは、ページ1には「連載」や「検索」などの単語が出てきて、ページ2には同様に「検索」や「転置」などの単語が出てきていると読み取ることしかできません。

ではこのとき、たとえば「検索」という単語がどのページにあるかを読み取りたい場合は、どうすればいいでしょうか？ この表は左から右にしか読み取れないので、表をひっくり返す必要があります。つまり、表1を表2のように書き換えます（同時に、単語をあいうえお順に並び換えています⁠）⁠。

表は左から右に読み取るので、こうすれば「検索」という単語はページ1とページ2の両方に出てきているということがわかります。また、表2は本の索引と同じ構造していることがわかると思います。先に紹介したように、これが転置索引です。つまり、この表をひっくり返す書き換え操作のことを転置と呼ぶのです（高校の数学で行列を習っていれば、転置行列における転置と全く同じ操作なので、わかりやすいと思います⁠）⁠。

「転置索引を構築する」とは、このような表の書き換え行うことになります。ちなみに、転置索引のことを英語ではInverted Indexと呼びます。

対応付けの単位

先ほど、書籍における転置索引の例を説明しました。本では、ページという単位でアクセスするので、単語とページの対応付けを行いました。では、その他の場合は何を単位として単語との対応付けを行えばいいでしょうか？

Web上のHTMLページの場合、1つのHTMLページをアクセス単位とするのが良さそうです。また、メールの場合は、1本のメールがアクセス単位となりそうです。このように、検索対象ごとにアクセス単位は変わります。

転置索引では、このアクセス単位のことを「文書（Document⁠）⁠」と言及している場合が多いです。つまり転置索引は、文書に出現する単語と文書の対応付けを行う表であると言えます。

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

転置索引の概念はわかったと思います。しかし、実際の転置索引では、単語が文書に出現する情報を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を転置したもの（表4）と転置索引は以下のようになります。

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

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

転置索引における語句

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

まとめ

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