検索エンジンを作る

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

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

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

転置インデックス

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

表1 転置インデックスから得られる文書IDと出現位置の集合

文書ID 出現位置
10 2034
11 178
15 449
15
 :
 :
 :
689
 :
 :
 :

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

表2 SQLによるインデックス表現

見出し語 文書ID 出現位置
今日 1 0
日は 1 1
は良 1 2
良い 1 3
い天 1 4
天気
 :
 :
 :
1
 :
 :
 :
5
 :
 :
 :

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

リスト

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

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

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

表3 転置インデックス

見出し語 文書ID 出現位置
今日 1 0
今日 3 238
今日 43 79
今日 55 91
今日 81 125
今日 90 23
日は 1 1
日は 3 239
日は 22 85
日は 38 23
日は
 :
 :
 :
47
 :
 :
 :
144
 :
 :
 :

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

著者プロフィール

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

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

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

著書

コメント

コメントの記入