検索エンジンを作る

第19回 転置インデックスの実装

この記事を読むのに必要な時間:およそ 2 分

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と出現位置の情報を保持しています。

表4 FINDSPOTの転置インデックスのブロック

レコード位置 内容(8バイト)
0 ブロックサイズ
1 見出し語
2 データ1(文書ID:出現位置)
3 データ2(文書ID:出現位置)
4 データ3(文書ID:出現位置)
5
 :
 :
 :
データ4(文書ID:出現位置)
 :
 :
 :

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

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

表5 各見出し語についてのブロック情報

見出し語 ブロック位置 ブロックサイズ
今日 32768 64
日は 32832 64
は良
 :
 :
 :
32896
 :
 :
 :
64
 :
 :
 :

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

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

著者プロフィール

工藤智行(くどうともゆき)

有限会社サイパック取締役社長。システム構築・管理のコンサルティング,ローカライゼーション,文書処理や障害者向けソフトウェアを中心とするプログラミングを長年手がける。 近著『UNIXプログラミングの道具箱』『システム管理現場の鉄則FreeBSD編』等

URLhttp://www.cypac.co.jp/

著書