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

第11回 転置索引の圧縮

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

はじめに

第2回で,索引は多くの場合圧縮されていることに言及しました。また第7回では,索引構築時にどの部分で索引を圧縮すればよいかを疑似コードを用いて説明しました。今回は,転置索引の具体的な圧縮方法について説明していきます。

圧縮の目的

中規模から大規模な索引の場合,転置リストは非常に長くなり,検索時にはディスクからの大量のデータの読み取りが行われます。転置索引(を用いた検索エンジン)では,これによる検索処理時間の増加を防ぐために,転置リストを圧縮しディスクからの読み込み時間の短縮を図ります。

この場合,圧縮された転置リストをディスクから読み込みさらに復元処理を行う必要がありますが,通常は次のようになります。

圧縮転置リストのディスクからの読み込み時間+復元処理時間 < 非圧縮転置リストのディスクからの読み込み処理

これは,近年のCPUとディスクの速度差が大きいため,主にCPUにおける処理である復元処理が高速に行えることによるものです。よって,圧縮というと容量を節約の意図で使うことが多いと思いますが,転置索引では"高速化"が主な目的となります。

転置索引の圧縮

転置索引は辞書と転置リストからなるため,転置索引の圧縮にも「辞書の圧縮」「転置リストの圧縮」がそれぞれあります。

辞書の圧縮

辞書はタームのリストであるため,辞書の圧縮ではこのタームのリストをどうやって少ない情報で表現するかということになります。

たとえば,タームを辞書順に並べたとき,共通の接頭辞を持つタームの連続が出現する場合がありますが,その共通部分を重複して保存しないようにすれば容量の節約が図れます。しかし,通常の辞書のサイズは転置リストのサイズと比べて非常に小さいため,辞書の圧縮による転置索引全体への貢献は非常に小さいものとなります。このため,本連載では辞書の圧縮方法は扱わず,参考文献[3]にその説明を譲りたいと思います※1)⁠

※1)
参考文献[3]は書籍ですが,Web上でPDF版が公開されていますのでそちらを参照ください。しかし,[3]で紹介されているいくつかの方法は,B+木など木構造の実装にも使われている方法であるため,通常はB+木の使用がお薦めです。

転置リストの圧縮

転置リストは文書ID,文書内のターム出現頻度(TF)⁠文書内オフセットなどからなる整数の列となります。よって,転置リストの圧縮とは,この整数列を少ない情報で表現することになります。

この整数列ですが,ランダムに整数が並んでいるわけではなく,文書IDや文書内オフセットは通常は昇順に並んでいますし,TFも通常は小さい整数となります。たとえば,文書IDが昇順に並んでいる場合,文書IDの整数をそのまま表現するよりも,1つ前の文書IDとの差分を取った方が数値としては小さい値として表現できます。また,TFのようにあらかじめ小さい数が来ることがわかっている場合は,小さい数をより小さい情報量で表現できる方法により,小さい領域で保存可能かもしれません。

このように,転置リストの圧縮では予め得られる情報に基づき圧縮を実現します。

転置リストの圧縮

ここでは,転置リストの具体的な圧縮方法を説明していきます.

通常,"整数"というと32ビット整数や16ビット整数などの固定長表現が考えられます。転置リストにおける整数列においてもこのような固定長表現の利用が考えられますが,10や100を表現するのに32ビットも使うというのは少し(かなり?)無駄な気がします。また,せっかく文書IDの差分などにより小さい数値で表現できても,固定長で表現する場合は意味がなくなってしまいます。よって,転置リストにおいては可変長符号による整数表現が使われます。

以下に,転置リストで使われるいくつかの可変長符号化方法を紹介します。

unary符号

unary符号は最もシンプルであり,整数値x(> 0)をx-1個の"1"ビットと末尾の"0"ビットで表現する符号化方法です。

たとえば,x=10の場合は "1111111110" となります。

gamma符号,delta符号

gamma符号は,整数値x(> 0)を2e + d(e = log2x, 0 ≤ d < 2eで表現し,e+1をunary符号で,dをeビットバイナリ符号で表現する符号化方法です。

たとえば,x=10の場合,log210 = 3となるため,3+1=4をunary表現すると"1110",10-23=2を3ビットバイナリで表現すると"010"となるため,それらを足した"1110" + "010" = "1110010" となります。

delta符号は,gamma符号でunaryで符号化する部分をgamma符号で置き換えたものとなります。

variable-byte符号(byte-aligned符号)

variable-byte符号は,その名の通り"複数のバイト"で符号化する方法となります。各バイトの下位7ビットを使って数値を表現し,その整数が次のバイトも含むかどうかを最上位ビット(1かどうか)で表す符号化方法です。つまり,1バイトでは27ビット,2バイトでは214ビット,3バイトでは221ビットまで表現できることになります。

たとえば,x=10の場合,x < 27 なので1バイトで表現できるので,"10001010" となります。

x=1030の場合は,x < 211なので2バイトで表現でき,
"00000100:10000110" となります。

delta符号,gamma符号などはビットレベルで符号化するため,高い圧縮率が達成できますが,その分ビット操作により復号が若干遅くなるという欠点もあります。一方variable-byte符号はバイトレベルで符号化するため,圧縮率はそれほど高くはありませんが,復号は高速に行えます。

また,これらの符号化方法は,パラメータなしの符号化方法(Parameterless Codes)と呼ばれています。なぜなら,対象とする整数列の特性に関係なく整数を符号化するからです。しかし,全体の文書数と各ポスティングリストに含まれる文書数(DF)がわかる場合※2)⁠各文書IDの数値をある程度見積もることができ,そのポスティングリストの特性に応じて符号化を適応させることが可能となります。

次に,そのような符号化手法であるgolomn符号,rice符号を紹介します。

golomn符号,rice符号

golomn符号は,パラメータm(≥ 1)を用いて,整数値x(> 0)を,b*q+r+1(0 ≤ r < b)で表現し,q+1をunary符号,rを以下に従って符号化する方法です。

e = log2b(切り上げ)⁠g = 2e - bとし,0 ≤ r < gの場合はrをe-1ビットのバイナリ符号で,g≤ r < bの場合はr+gをe ビットのバイナリ符号で表します。

たとえば,x=10の場合,10 = 5・1 + 4 + 1 (q=1,r=4)となり,

  • e = log25 ≒ 3
    g=2e - b= 23 - 5 = 3 (< r)

となるため,q+1(2)のunary符号 + r(4)+g(3)のe(3)ビットバイナリ符号で"10:111" となります。

golomu符号はm=1の時はunary符号となり,m=2k(k=1,2,3...)の時はrice符号と呼ばれます。

※2)
統計値としてこれらの値をもっている場合となります。

著者プロフィール

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

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

コメント

コメントの記入