検索エンジンはいかにして動くのか?

第5回 転置索引の実装

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

転置リストの実装

転置リストは,各単語におけるポスティングリストの集まりであり,これらは通常辞書とは別の領域(ファイル)に保存されます。

そこでは,各リストは隣りあって格納され,辞書がそのリストへの(オフセットなどの)位置情報を保持しているという構造となります図4)⁠

図4 転置リストの実装

図4 転置リストの実装

ポスティングリストは各単語ごとに数100バイト~数Mバイト,大規模な場合は数10Mバイト~数100Mバイトにもなります。よって,通常ポスティングリストはディスク上に格納され,パフォーマンスの観点から,リストはディスクの連続した領域に格納されることが多いようです※3)⁠こうすれば,ポスティングリストの取り出しが,1回のシークと1回の連続ディスク読み取りで行うことができるからです。

※3
例外はたくさんあります。たとえば,リストがファイルシステムを通して格納される場合,ファイルシステムが連続した領域を確保せずに領域を複数に分断する可能性があります。また,今後の連載で説明予定の動的な索引構築においては,リストの分断を許すことで索引構築のパフォーマンスを向上させることがあります。

ポスティングリストの物理的な格納方法

前回説明しましたが,単語レベルのポスティングリストは,文書ID(DocID)と文書におけるオフセットのリスト(off1, off2 ...)からなります。また,各文書における出現数(オフセットの数)も保持されます※4)⁠ポスティングリストのこれらの情報は全て数値で表現されているので,ディスクなどに格納する場合は,多くの場合,整数のバイナリ表現としてそのまま格納します。

たとえば,各ポスティングを

DocID,freq,off1,off2,off3

のように格納する場合(','は区切れを示すために便宜的に書いています)⁠前回作成した"search"に対するポスティングリスト(D1:3,D2:2)は,以下のような整数列として表現されます。

1,1,3,2,1,2

この各整数をそのまま4バイトのバイナリで保存するとすると,このポスティングリストは24バイト(4バイト×6)のバイナリ列となります。

※4
オフセットの数は,通常TF(Term Freqency)と言われます。本連載ではランキングなどについてはあまり触れない予定ですが,TFはリストの参照時に利用されるだけでなく,ランキングの要素としても用いられます。

ポスティングリストの圧縮

転置リストを構成する各ポスティングリストは,検索したい文書数が増えるほど長くなります。よって,中規模以上の文書におけるポスティングリストでは,その取得におけるディスクI/Oが検索処理において非常に大きな比重を占めてしまいます。

この問題に対処するために,通常ポスティングリストは圧縮して格納され,ディスクI/Oの削減を図ります。圧縮手法にもよりますが,ポスティングリストを圧縮することにより,索引構築と検索の両方でディスクI/Oの削減による高速化が見込めます。

詳しい圧縮手法については今後の連載で説明する予定ですが,ポスティングリストは整数列となるため,整数列に向いた圧縮手法が用いられます。

まとめ

若干駆け足でしたが,転置索引の実装を辞書と転置リストに分けて説明しました。辞書は順序をもった木構造などの構造となり,転置リストは整数列のバイナリ表現となります。これらの構造は用途やユースケースによって異なりますが,基本的の部分は変わりません。

参考文献
[1]
Ubiquitous B-Tree, Douglas Comer, ACM Computing Surveys (CSUR),1979
[2]
Inverted files for text search engines, Justin Zobel, Alistair Moffat, ACM Computing Surveys (CSUR), 2006

著者プロフィール

山田浩之(やまだひろゆき)

日本IBM株式会社を経て,ヤフー株式会社等で検索エンジンの開発に従事。現在は大学院でデータベース・情報検索の研究を行う。また,オープンソースで全文検索エンジンLuxやデータベースマネージャLux IOの開発を行っている。

コメント

コメントの記入