はじめに

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

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

転置索引とは

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

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

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

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

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

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

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

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

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

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

対応付けの単位

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

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

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