簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜
前回までで簡潔ビットベクトルというデータ構造を実装した。簡潔ビットベクトルとは普通のビット列に少しの追加データを持たせることでrank/selectという2つの操作が可能にしたもの。そしてrank/selectとはそれぞれ以下の操作のこと。
rank(x) : x番目のビット以前(xの位置を含む)の立っているビットの数 select(i): i番目に立っているビットの位置
今回は簡潔ビットベクトルを利用して転置インデックスを効率的に実装してみる。
前回までの記事：
簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei
apple 1, 3 orange 1, 2, 4, 6
のように各単語に対してその単語が出現する文書IDを列挙したもの。これを単純に実装するとデータサイズが大きくなってしまうので通常は文書ID列を符号化して持たせる。
最も単純な符号はunary(ユナリィ)符号とよばれるもので、これは数値nを「n個の1の後に0をくっつけたもの」として表現する。具体的には
unary binary 0 0 0000 1 10 0001 2 110 0010 3 1110 0011 4 11110 0100 5 111110 0101 6 1111110 0110 7 11111110 0111
という感じ。通常のbinary(バイナリ)が固定サイズ(この記事ではとりうる値の最大が7であると仮定して4bit割り当てた)なのに対してunaryはサイズが数値によって異なる。これによって0、1、2などの小さな値ではunaryのほうがbinaryよりもデータサイズを節約できる。
unary符号を採用すると小さな値のほうがデータサイズが小さくなるので、文書IDの数値もできるだけ小さな値にしたい。これを実現するために文書IDを差分値で持たせるという工夫をする。つまり
apple 1, 3 orange 1, 2, 4, 6
を
apple 1, 2 orange 1, 1, 2, 2
のようにする。こうすると固定サイズのbinaryでは(4bit * 6 = )24bit必要。これに対してunaryではそれぞれ数値+1のぶんのbitが必要なので(2 + 3 + 2 + 2 + 3 + 3 = )15bitとなりbinaryに比べてデータサイズが小さくできる。
さて無事インデックスができたので検索をすることを考える。クエリとして「apple AND orange」というAND検索が行われたとする。このときまず出現する文書数の少ないappleで転置インデックスを検索すると「1,2」という差分ID列が得られる。この差分ID列は順番に足しあわせていくことで元の文書ID列「1,3」が得られる。orangeに対してはすべてのIDをチェックしなくてもappleの出現する文書ID「1,3」があるかどうかだけをチェックすればよい。
さて、ここで問題が発生する。unaryによってデータサイズが小さくできたのはいいのだが文書IDを差分で持たせることにしたので、差分を足しあわせないと元の文書IDがわからなくなってしまっている。よって文書ID「1,3」があるかどうかをそのままではチェックできない。
ここで簡潔ビットベクトルのselectという操作を活用する。まずunaryによって表現されたビット列を見てみると
orange 元のID列 1, 2, 4, 6 差分ID列 1, 1, 2, 2 ビット列 1010110110
となっている。ここで元のID列を引数としてselect()を計算してみる。
select(1) = 0 [1]0 10 110 110 select(2) = 2 10 [1]0 110 110 select(4) = 5 10 10 1[1]0 110 select(6) = 8 10 10 110 1[1]0
select()の返した位置のbitはカッコをつけた。カッコの位置を注意深く見ると右隣に必ず0が来ることがわかる。つまりselect(ID)を計算して帰ってきたビットベクトルの位置の右隣のbitを調べて0ならそのIDがあるということがわかる。
また特定のIDより小さいのIDがいくつあるかも簡潔データ構造なら簡単に計算できる。例えばorangeを含むID3より小さいの文書がいくつあるかを計算したいとする。これにはselect(ID) が返したビットベクトルの位置までに何回0が出現したかを数えればよい。
select(3) = 4 10 10 [1]10 110
↑を見ればわかるように、ID3に対応するbitは3つめのunaryに含まれる。これはID3はID2より大きいので2つめのunaryには含まれないが、ID4以下なので3つめのunaryに含まれる、ということ。
そして各unary毎に1つずつ0が含まれているので、0の個数を数えればID3以下のunary(=文書)の数がわかる。0の個数を数えるにはrank()を使う。rank(x)でx番目までの1の出現回数がわかるのでx + 1 - rank(x)で0の出現回数がわかる。これをrank0と名付ける。
rank0(x) = x + 1 - rank(x)
このrank0とselectを併用すればID3より小さいの文書数がわかる。
rank0(select(3)) = rank0(4) = 4 + 1 - rank(4) = 4 + 1 - 3 = 2
よってorangeの出現するID3より小さいの文書は2つであることがわかる。
unaryは転置インデックス以外でもCompressed Suffix ArrayやLOUDSなどで利用される。これらの用途では今回紹介した以外の機能も必要になるが、それらもrank/selectを活用することで実現できる。次回はLOUDSまわりの話をする予定。
