パソコンのための文書の索引＝「転置インデックス」
パソコンが文書の索引を作るのも、基本的な考え方は人間と同じです。「じゃあ、パソコンが文書やキーワードの表をどうやって扱っているの？」―――パソコンは人間と違って、紙の上に表を書けません。メモリーに載せた情報しか扱えないのです。それでは、パソコンがメモリー上で索引を扱う仕組みを覗いてみましょう。
先ほどの2つの表で表現されている情報を分解していくと、「文書名の列」「キーワードの列」「文書名とキーワードの関連」の3つの要素に分かれます。
これらの3つの要素をうまくメモリーの上に載せてあげれば、文書の索引がパソコンで扱えることになります。「文書名の列」「キーワードの列」は、いずれも「文字列の列」です。実は、パソコンは「文字列の列」を扱うのがあまり得意ではありません。なぜならば、文字列の長さ（バイト数）は決まっていないからです。たとえば、もし文字列の長さがすべて6文字（6バイト）と分かっていれば、メモリーの番地を計算することで「表の上から4番目のキーワードは、（4番目-1）×6バイト＝18バイト目にある」ということがすぐに分かります。
しかし実際には、「文書名」「キーワード」の長さは一定ではありませんので、メモリーの番地は、「n-1番目×文字数」では計算できません。各文字列のおしりに、文字列どうしの区切りが分かるように特別な記号をつけてあげる必要もあります。下の図のように文字列の最後に特殊な文字（ここではNULL文字と呼ぶことにしましょう）を入れておけば、単にずらっと並べた文字列の列からでも「15番目の文字列」を取り出せますが、いちいち先頭から探していく必要があり、後ろの文字列になるほど時間がかかってしまいます。
そこで、ひとつ工夫をしてみましょう。下の図を見てください。
メモリーを「文字列本体を格納するエリア（0番地～）」と「番地を格納するエリア（1000番地～）」に分けて使っています。「4番目のキーワード」を取り出すには、まず「番地を格納するエリア」で4番目のキーワードに対応する番地（1000番地＋（4番目－1）＝1012番地）を計算し、1012番地に格納されている番地「0018」を使って文字列本体「google」を取り出せばいいのです。
では、「文書名とキーワードの関連」はどうやって表すのでしょうか？ 「文字列」と「文字列」の関係づけをメモリー上に表現するのは、「文字列の列」よりももっと大変そうです。そこで、下の図のように「文書名」と「キーワード」を番号（ID)に置き換えてみましょう。
たとえば、文書名「はじめに.txt」を「0」、「第3章.txt」を「3」に置き換えます。同様に、キーワード「Google」を「1」、「Yahoo!」を「2」で置き換えます。その結果、メモリー上には「文書名とキーワードの関連」が下の図のように表現できます。
この図が、1ページ目に出てきた「文書ごとにまとめた表」に完全に対応していることが分かるでしょうか。同様に、同じく1ページ目の「キーワードごとにまとめた表」をメモリー上で表現したのが下の図です。
「パソコン」を含む文書（ファイル）を調べるには、上のメモリー表現の図が使えます。「パソコン」のキーワードIDが「2」だとすると、キーワードIDが2のメモリーのエリアから、「10」を取り出し、番地「10」に格納されている番号の列「0」「2」「-1」を取り出します。
※列の終わりには特別な番号「-1」が格納されていて、他のキーワードに対応する番号の列と区別できるようになっています。
こうして、番号の列に対応する文書の列「第1章.txt」「第3章.txt」を検索結果として取得できます。
このように、「キーワードごとにまとめた表」をメモリー上に表現することで、すばやく文書を検索できます。肝心な点は、「文書ごとにまとめた表」を、「キーワードごとにまとめた表」に変換していることです。文書とキーワードの関係をひっくり返して索引を作ることから、上の図の索引のことを「転置インデックス」と呼びます。
