検索エンジンを作る

第20回 転置インデックスの実装(その2)

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

前回は,FINDSPOTの転置インデックスの構造について説明しました,今回はこの構造に至った経緯などについて解説します。

ブロックの拡張問題

前回,転置インデックスのブロックは次のような構造になっていることを説明しました。

表1 FINDSPOTの転置インデックスのブロック構造

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

このブロックには,ブロックサイズがいっぱいになるまで(空きレコートが存在する間)は,データを詰め込むことができますが,ブロックが溢れてしまって,これ以上データが格納できない場合にどうするかという課題があります。

転置インデックスの作成当初は対象とする文書数が少ないので,転置インデックスに登録するデータ量は少ないのですが,だんだん登録する文書数が増えていくと,転置インデックスに登録しなければならないデータ量も大きくなっていきます。必然的に,特定のN-gramに関する転置インデックスのレコードが溢れることになり,この時にどのように対処すべきかという問題が発生するのです。

FINDSPOTの初期の実装

FINDSPOTの初期の実装では,ブロックが溢れたら,続きのデータを格納するために新たに別のブロックを作成する方式を採っていました。この時,続きのデータ用のブロック位置に関する情報は,ブロックの第2番目のレコードに格納していました。

表2 初期のFINDSPOTの転置インデックスのブロック構造

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

最初に作成するブロックは16レコード分です。この時,ブロックサイズ,見だし語,次のブロック位置のために3レコードを消費するので,都合13レコード分がデータ用に利用できます。このブロックには13個分のデータを書き込めますが,次に14個目のデータを同じN-gramに関して書き込む必要が生じたら,新たなブロックを作成して,14個目のデータを書き込むという寸法です。新たなブロックの転置インデックス内の位置は,元のブロックの第2レコードに書き込むことで,検索の際には,このチェーンを辿って次のブロックを参照できます。

また,ブロックのサイズに関しては,最初は16レコード分のブロックサイズ(128バイト)とし,続きのデータ用のブロックは5個ごとにサイズを倍に拡張するというアルゴリズムを使用していました。次の表は,このブロック拡張によって,トータルで何個のデータが格納できるかを示したものです。

表3 ブロック数とデータ数の関係

ブロック数 レコードサイズ 格納できるデータ数
11613
21626
31639
41652
51665
63294
732123
832152
932181
1032210
1164271
1264332
1364393
1464454
1564515
16128640
17128765
18128890
191281015
201281140
212561393
222561646
232561899
242562152
252562405
265122914
275123423
285123932
295124441
305124950
3110245971
3210246992
3310248013
3410249034
35102410055
36204812100
37204814145
38204816190
39204818235
40204820280
41409624373
42409628466
43409632559
44409636652
45409640745
46819248934
47819257123
48819265312
49819273501
50819281690
51819289879
52819298068
538192106257

この表によると,1000個のデータを格納するには19個のブロック,1万個のデータを格納するには35個のブロック,10万個のデータを格納するには53個のブロックが必要になることがわかります(表中色のついた箇所)。

このブロック数を拡張する方法は,使用されていない空きレコードが少ない(最大でも最後に作成したブロックの空きレコード分)ことや,データを追記する際の処理が軽くて済むというメリットがあります。実際に使用してみたところ,転置インデックスの作成スピードは十分でしたが,検索性能に関してはもうひとつ満足のいくものではありませんでした。

著者プロフィール

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

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

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

著書

コメント

コメントの記入