本連載の第5回でN-gramのしくみを解説しました。この中で転置インデックスは，特定の文字列素（FINDSPOTの場合には2文字と1文字）に対して，文書IDとその文字列素の文中での出現位置情報のペアが記録されたものだというところまで説明しました。今回はそのFINDSPOTでの実装方法に関して説明します。

転置インデックス

転置インデックスは特定の見出し語に対して，次のような文書IDと出現位置の集合情報を得るのが目的です。

連載の第2回で紹介したように，文書IDと出現位置を得るのにSQLデータベースのテーブルを使用することもできます。

上記の表2のようなテーブルを作っておき，特定の見出し語に対して，次のようなSQL文を実行すれば，目的の見出し語に対する文書IDと出現位置の集合が得られます。

select 文書ID, 出現位置 from index_table where 見出し語="今日";

ところが，この方法は論理的には正しいものの，検索エンジンのインデックスとして使用するには実行スピードが極めて遅いため，まったく実用になりません。

実用的な検索スピードを実現するには，特定の見出し語に対して表1のような文書IDと出現位置の集合が高速に得られなければなりません。このためには，あらかじめ特定の見出し語に対する文書IDと出現位置のペア集合が集計された上で管理されている必要があります。

先ほどの表2のデータが文書ID順だったのに対して，表3は見出し語順になっています。文書IDと見出し語のデータの並び順がひっくり返っているために，転置インデックスに「転置」という語が付けられます。転置インデックスの形式であれば見出し語ごとに求めるべきデータが固まっているので，求めるべき文書IDと出現位置の集合が高速に得られます。Googleでは複数台のマシンを使った分散処理で表2の形式から表3の形式にデータを変換しており，この操作をMapReduceと呼ぶしくみを通じて実現しているということです。