本連載の第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と呼ぶしくみを通じて実現しているということです。

FINDSPOTの転置インデックス構造

FINDSPOTの転置インデックスを設計する際には、いくつかの前提条件について吟味する必要がありました。

まずは扱うデータの分量です。FINDSPOTで扱うデータ量は平均500字程度の文書で100万件というのが当初の目標値でした。トータルの文字数は、500字×100万件＝5億字となります。2文字単位のバイグラムの個数は5億個、1文字単位のモノグラムが5億個で、合わせるとデータの個数は10億個（1G個）となります。さらに、FINDSPOTでは文書IDを4バイト（32ビット）, 出現位置を4バイト（32ビット）で表現しているので、データ量は10億個×8バイト＝8Gバイトになります。

8Gバイトのデータ量は、残念ながら現時点では1台のマシンのメモリ上で処理するのは難しい数字です。あと10年くらい経って、128Gバイト程度のメモリを搭載したサーバが当たり前になったら随分と状況は変わると予想できますが、少なくとも現時点ではハードディスク上で処理しなければならないデータ量です。

FINDSPOTではハードディスク上のファイルに転置インデックスの情報を記録し、これを読み出すことで検索を行っています。読み出す対象がハードディスクであるというのが、性能を引き出すのに考慮しなければならない大きなポイントです。

FINDSPOTの転置インデックスは論理的には表3と同様の情報を保持しています。1つのインデックスファイルの内部を複数のブロックに区分けし、各ブロックに特定の見出し語に対する文書IDと出現位置の情報を記録する設計としています。見出し語について次のようなブロックを使って、文書IDと出現位置の情報を保持しています。

ブロックの内部は8バイト単位のレコードが複数個格納されています。最初のレコードには、そのブロックのサイズ情報が格納されています。ブロックサイズは2の倍数値に限っており、最少のブロックサイズは32バイト（4レコード分）です。次のレコードには見出し語が格納されます。見出し語はUTF-16（2バイト）で格納するので、2文字のバイグラムの場合には4バイト分が使われます。以降のレコードにはデータが格納されます。データの内部は4バイトの文書IDと4バイトの出現位置の情報となります。使用されていないブロックサイズ以外のレコードは常に0クリアされます。

特定の見出し語の情報を検索するには、見出し語に相当するブロックの内容をファイルから読み出せば、文書IDと出現位置の情報が取得できます。この操作を高速に行うには、見出し語に対するブロック位置とブロックサイズの情報を知らなければなりません。

FINDSPOTは起動時に、エラーチェックを兼ねてインデックスファイルの全体を走査し、表5のような各見出し語についてのブロック情報をメモリ内に保持します。この情報は見出し語をキーとするAVLによる辞書構造で管理しています。特定の見出し語についての検索を行う場合には、まずこの辞書を調べて（AVL内を2分検索するので非常に高速⁠）⁠、見出し語に関する転置インデックスファイル内のブロック位置とブロックサイズを特定します。次に、インデックスファイルを開き、ブロック位置にシークを行い、ブロックサイズ分だけファイルの内容を読み込めば検索が完了するというしくみです。

以上が、FINDSPOTの転置インデックスの基本構造です。とてもシンプルなデータ構造ですが、次回は、ここに至った経緯や、インデックス情報の動的な追加方法などについて説明したいと思います。