Blog

Home
Blog
Compressed Permuterm Index: キーワード辞書検索のための多機能＆省メモリなデータ構造

2012.11.06

Compressed Permuterm Index: キーワード辞書検索のための多機能＆省メモリなデータ構造

Tag

# データ構造

# ライブラリ

# 解説

Shirou Maruyama

リサーチャーResearcher

はじめましてこんにちわ。
4月からPFIで働いているまるまる（丸山）です。最近のマイブームはスダチです。
リサーチブログの更新が再開されたので、私も流れに乗って初ブログを書いてみようと思います。

今回は社内の情報検索輪講で少し話題にあがったCompressed Permuterm Indexを紹介したいと思います。

Paolo Ferragina and Rossano Venturini.
“The compressed permuterm index”, ACM Transactions on Algorithms 7(1): 10 (2010). [pdf]

~~これを実装したので以下のgoogle codeに晒してみることにします。~~

~~http://code.google.com/p/cpi00/~~

修正BSDライセンスです。ソースコードは好きにしてもらって構いませんが、完成度はまだまだなので研究目的で使うことをお勧めします。使い方は下の方に書いてます。

[11/6 追記]
Compressed Permuterm Indexには特許が取られているようです。
コードの公開を一時停止しました。

[11/10 追記]
アルゴリズムの作者からOSS公開の許可を頂きました。
研究・非営利目的でのみ使用できます。使用方法は下記をご参照くださいませ。

http://code.google.com/p/cpi00/

cpi00は「しーぴーあいまるまる」と発音してください。名前は5秒で考えました。

で、これはいったいなんでしょか？

キーワード辞書$D = \{p_1, p_2, \dots, p_m\}$が与えられた時に、これを高速に検索ができる圧縮索引構造です。いわゆるSelf-indexというやつで、検索の際には元のキーワード辞書は不要です。しかも索引サイズは元の辞書サイズよりも小さくなります。
基本的な検索機能として以下の操作をサポートしています。

$Membership(p)$ :
キーワード$p$が辞書$D $に登録されていれば真、そうでなければ偽を返す。
$Rank(p)$ :
キーワード$p$が辞書$D$に登録されているならば、辞書式順序での順位を報告。
$Select(i)$ :
辞書式順で$i$番目のキーワードを報告。
$PrefixSearch(\alpha)$ :
辞書$D $の中で文字列$\alpha $を接頭辞として持つキーワードを全て報告。
$SuffixSearch(\beta)$ :
辞書$D $の中で文字列$\beta $を接尾辞として持つキーワードを全て報告。
$PrefixSuffixSearch(\alpha, \beta)$ :
辞書$D $の中で$\alpha $を接頭辞に持ち、かつ、$\beta $を接尾辞として持つキーワードを全て報告。
$SubstringSearch(\gamma)$ :
辞書$D $の中で文字列$\gamma $を部分文字列として持つキーワードを全て報告。

ここでのキーワード$p$の接頭辞、接尾辞、部分文字列とは、$p = \alpha\gamma\beta$と3つに分解されると考えた時に、文字列$\alpha$を接頭辞、$\beta$を接尾辞、$\gamma$を部分文字列といいます。$p$の長さを$k$とすると$\alpha, \beta, \gamma$の長さは、それぞれ0から$k$の間で可変とします。なので部分文字列は接頭辞にも接尾辞にもなりえます。上で定義されたほとんどの操作は$O$(クエリ長+ヒットしたキーワードの合計長) くらいの計算時間で答えを返してくれます。

背景

キーワード辞書を検索するためのデータ構造としてハッシュ表やトライ構造（簡潔木、ダブル配列）がよく使われてきました。しかし、ハッシュ表ではクエリと完全一致するキーワードが辞書の中に存在するか否かしか判定できません。一方で、トライ構造では$PrefixSearch$をサポートすることができますが、$SuffixSearch, PrefixSuffixSearch, SubstringSearch$のような検索は効率良くできません。転置索引でのキーワードリスト検索、辞典のタイトル検索等では部分一致検索をサポートする必要が多く、今回のデータ構造はとても有用だろうと思います。

プログラムの使い方

ここで実装したプログラムの簡単な使い方を説明します。
説明のために次のようなキーワードリストkeyword.txtがあるとします。

// keyword.txtの中身
レッドブル
ユンケル
活参
レッドワイン
焼酎
ユンブル
活ブル
焼酎お湯割り
焼酎ブル割り
ブルのワイン割り

現実には存在しない飲み物が含まれていますが、気にしないでください。
文字コードはASCIIかUTF-8を想定しています。それ以外での動作保証はありません。

コンパイル方法

特別な依存ライブラリはありません。以下のコマンドを入力してください。
$ ./waf configure
$ ./waf build

サンプルプログラム

サンプルとして対話型プログラムcpi00を用意しています。
キーリストを格納したファイル”keyword.txt”に対する索引”keyword.idx”を作る場合には以下のように行います。
$ ./build/src/cpi00 -k keyword.txt -i keyword.idx
index time: 0.000102043 sec
index size: 6465 bytes

索引に登録されているキーリストを見るためには-i “索引名”と-sをオプションで渡します。
実行すると全てのキーが昇順にソートされた状態で出力されます。
$ ./build/src/cpi00 -i keyword.idx -s
1 :ブルのワイン割り
2 :ユンケル
3 :ユンブル
4 :レッドブル
5 :レッドワイン
6 :活ブル
7 :活参
8 :焼酎
9 :焼酎お湯割り
10 :焼酎ブル割り

-i “索引名”のみを指定すると対話型の検索が始まります。例としてSubstringSearch(“ブル”)をやってみましょう。以下のようにmodeで”ss”、queryで”ブル”を入力します。
$ ./build/src/cpi00 -i keyword.idx
read:10 keys
mode > ss
query > ブル
mode:SubstringSearch
substring = ブル
ユンブル
レッドブル
活ブル
ブルのワイン割り
焼酎ブル割り
#hits = 5

このように部分文字列として”ブル”を持つ全てのキーワードが表示されます。
その他にも以下のようにmodeを変化させることで様々なクエリを投げることができます。
“mb” (Membership), “rk” (Rank), “sl” (Select), “pf” (PrefixSearch),
“sf” (SuffixSearch), “ps” (PrefixSuffixSearch).

APIの使い方

ここでは簡単にcpi00のAPIの使い方の例を示します。ただし、今後の修正でAPIが大幅に変更する可能性があります。いまのAPIはひどい、ダメだ、こう直せという感想をお待ちしております。
APIを利用する場合は、次のようにsrc/以下にあるCompPermIdx.hppをインクルードしてください。

...
#include "CompPermIdx.hpp"
...
// string型のキーワードリストを用意する。この時点ではソートされていなくて良い。
vector<string> keys;
keys.push_back("hop");
keys.push_back("hope");
keys.push_back("hit");
keys.push_back("hat");

// 索引を作成する
CompPermIdx cpi1;
cpi1.Build(keys);

// 元のキーワードリストが不要なら削除する。
vector<string>().swap(keys);

// 索引をディスクに書き出す。
fstream ofs("test.idx");
cpi1.Write(ofs);

// 索引を初期化する。
cpi1.Clear();

// 索引をディスクから読み込む。
CompPermIdx cpi2;
fstream ifs("test.idx");
cpi2.Read(ifs);

// 検索クエリを投げる
string query1 = "ho";
string query2 = "e";
vector p_ret, ps_ret; // 検索結果キーリストを保持する配列
cpi2.PrefixSearch(query1, ret);
cpi2.PrefixSuffixSearch(query1, query2, ps_ret);
...

詳しくは”CompPermIdx.hpp”を参照してください。

性能評価

ここでは簡単な実験結果をお見せします。
テストデータとして長さ10から20のランダム文字列からなるキーリストを作成しました。キーの総数は9,793,065件。ファイルサイズは151,781,376バイトです。測定環境はMacOS X 10.7.5, Intel Core i5 1.7GHz, 4GB RAMです。

索引構築時間

100.273秒

索引サイズ

138,462,101バイト
ランダム文字列なので元々圧縮しにくいデータなのですが、それでも元ファイルサイズよりも小さくなります。

Membershipクエリの計測時間

以下は元のキーワードをキーとしてランダムにクエリを1万回投げた結果です。
0.15091秒
RankクエリはMembershipの計算時間とほとんど変わらないので割愛します。

Selectクエリの計測時間

[1, キーワード数]の範囲の整数をランダムに1万回投げた結果です。
0.164428秒

PrefixSearchクエリの計測時間

以下は元キーワードからランダムに選び出し、その接頭辞5文字をクエリとして1万回投げた結果です。
0.211133秒
しかし、PrefixSearchの検索時間はヒットしたキーワードの合計長に依存します。このケースでは合計で10,166件のヒットが得られました。これでは1回の検索でほとんど1件のヒットしかしていません。そこで、ヒット数を増やすためにランダムに選んだキーワードの接頭辞3文字を1万回投げた結果を次に示します。
8.29948秒
この時の総ヒット件数は538,153でした。このように検索時間はヒットしたキーワード数に大きく依存することがわかります。SuffixSearch, PrefixSuffixSearch, SubstringSearchについても同様の結果が得られるので実験は割愛します。

技術解説

Compressed Permuterm Indexのコアアイデアを解説したいと思います。少しややこしい話もあるので中身に興味のない方はすっ飛ばしてもらって構いません。

この解説のためにFM-indexのBackward Searchを理解する必要があるのでかなりざっくりと説明します。前回の徳永さんの素晴らしい解説記事でLF Mappingを理解しておくと原理まで分かるのではないかと思います。ここから配列の添字は0から始まるものとして説明していきます。
例として次のような文字列Sの検索を考えます。

S = abraca$

ここで末尾の記号’$’は文字列中には現れない特別な記号で、アルファベット集合が全順序を持つ時に、どんな記号よりも順序の小さいものとします。
この文字列を循環シフトさせた文字列（つまり、”abraca$”, “a$abrac”, “ca$abra”, .. )全てを辞書式順序で整列させた行列を作ります。以下に例を示します。

F aaaaaaL
$ abrac a
a $abra c
a braca $
a ca$ab r
b raca$ a
c a$abr a
r aca$a b

ここで一番左の列をF, 一番右の列をLとして注目していきます。LはBurrow-Wheeler（BW）変換された文字列に対応し、L以外を忘れてしまっても元の文字列に逆変換することができます（徳永記事を参照）。
検索を行う際には、さらにCという配列とocc(ch, i, j)という関数を用意します。C[ch]は記号chよりも小さな記号の総数です。この例ではC[‘$’] = 0, C[‘a’] = 1、C[‘b’] = 1 + 3 = 4、C[‘c’] = 1 + 3 + 1 = 5、C[‘r’] = 1 + 3 + 1 + 1 = 6となります。occ(ch, i, j)関数はBW文字列Lの区間L[i, j]に記号chが何回出現するかを返す関数です。この関数はBW文字列をウェーブレット木などのデータ構造で表すことで効率良く計算できます。これらを使って高速に文字列検索を行うことが可能です。

ここでクエリ文字列Q = “aca”を検索することを考えます。この検索はクエリ文字列を末尾から先頭へ逆方向に見ていきます。まず、一番後ろの文字がQ[2] = ‘a’なので行列の中で”a”を接頭辞として持つ行の区間は[C[a], C[b] – 1] = [1, 3]と知ることができます。次に”ca”を接頭辞として持つ行の区間、最後に”aca”を接頭辞として持つ行の区間を求め、最終的なパターンの出現回数を求めることができます。これは範囲を表す2つの変数begとendを用意し、次の計算でこの2変数を更新していくことで実現できます。

beg = C[Q[i]] + occ(Q[i], 0, beg – 1).
end = C[Q[i]] + occ(Q[i], 0, end) – 1.

ここでiは現在見ているクエリ文字の位置とします。では検索の流れを追って行きましょう。
i = 2の場合は、begとendに初期値を設定するだけです。Q[2] = ‘a’なので”a”に対応する区間[1, 3]からbeg = 1, end = 3とします。次にi = 1の場合を考えましょう。次の計算でbegとendを更新します。

beg = C[‘c’] + occ(‘c’, 0, 1 – 1) = 5 + 0 = 5.
end = C[‘c’] + occ(‘c’, 0, 3) – 1 = 5 + 1 – 1 = 5.

これで区間[5, 5]が得られました。実際に”ca”は行列の5行目の接頭辞となっていることを確認してみてください。この例では文字列中に”ca”が1度しか現れませんが、もしもk回現れるのならば長さkの区間が得られます。最後にi = 0の場合を考えましょう。begとendを更新します。

beg = C[‘a’] + occ(‘a’, 0, 5 – 1) = 1 + 2 = 3.
end = C[‘a’] + occ(‘a’, 0, 5) – 1 = 1 + 3 – 1 = 3.

これで区間[3, 3]が得られました。行列の3行目を見ると確かに”aca”が接頭辞となっていることがわかります。これで文字列中に”aca”というパターンが1回出現することがわかりました。このような検索方法をBackward searchと呼びます。Backward searchでは配列CとL上で計算されるoccしか必要ありません。このアイデアに基づく圧縮索引構造はFM-indexと呼ばれています。何でこの検索方法が成り立つのか原理が気になって仕方がない人は徳永記事を合わせて読みましょう。

さてさて、ここから本題のCompressed Permuterm Indexの話に入りましょう。
例として以下のようなキーワードリストがあるとします。

hat
hip
hope
hot

この4つのキーワードを次のように連結した文字列Sを作ります。

S = $hat$hip$hope$hot$#

ここで各キーワードは辞書式順序で昇順に連結されているとします。また、’$’と’#’はキーワード中に現れない特別な記号とし、’$’はどんな記号よりも順序が小さく、’#’は逆にどんな記号よりも大きな順序を持つ記号とします。
SはさらにBW変換されます。以下にSを循環シフトさせた文字列を辞書式ソートした例を示します。

F aaaaaaaaaaaaaaaaaaL
$ hat$hip$hope$hot$ #
$ hip$hope$hot$#$ha t
$ hope$hot$#$hat$hi p
$ hot$#$hat$hip$hop e
$ #$hat$hip$hope$ho t
a t$hip$hope$hot$#$ h
e $hot$#$hat$hip$ho p
h at$hip$hope$hot$# $
h ip$hope$hot$#$hat $
h ope$hot$#$hat$hip $
h ot$#$hat$hip$hope $
i p$hope$hot$#$hat$ h
o pe$hot$#$hat$hip$ h
o t$#$hat$hip$hope$ h
p $hope$hot$#$hat$h i
p e$hot$#$hat$hip$h o
t $hip$hope$hot$#$h a
t $#$hat$hip$hope$h o
# $hat$hip$hope$hot $

$PrefixSearch(\alpha)$と$SuffixSearch(\beta)$の場合は話は簡単で、Backward searchの原理を利用して$\$\alpha$と$\beta\$$を検索するだけです。それでは、$PrefixSuffixSearch(\alpha, \beta)$の検索はどのようにすれば良いでしょうか？このために$\beta\$\alpha$の検索を行います。もしも、

S’ = $hat$hat$hip$hip$hope$hope$hot$hot$#

のように各キーワードを2回出現させた連結文字列上で$\beta\$\alpha$の検索を行えば接頭辞$\alpha$と接尾辞$\beta$を持つキーワードを容易に見つけることができます。しかし、この方法では文字列長は2倍となってしまい領域効率がよくありません。また、重複した検索結果を避けるための工夫も必要となってしまうのでエレガントではありません。
そこでF[i]=’$’となる先頭の数行に着目します。

F aaaaaaaaaaaaaaaaaaL
$ hat$hip$hope$hot$ #
$ hip$hope$hot$#$ha t
$ hope$hot$#$hat$hi p
$ hot$#$hat$hip$hop e

F[i]に対応する’$’は、辞書式順でi番目のキーワードの先頭にくっついている’$’です。ここで着目しなければならないのはi番目のキーワードの先頭にくっつく’$’はF[i]に現れ、その終端にくっつく’$’はF[i+1]として現れることです。これは辞書式ソートの原理から明らかです。ということは’$’から始める接頭辞の位置iにたどり着いた時に、わざと1つ下にずれてLF Mappingを続ければ、ある1つのキーワード文字列$\upsilon $に対して$\dots \$ \upsilon \$ \upsilon\$ $のように循環したキーワード文字列の検索が可能になります。実際に$\beta\$\alpha$を検索する場合を考えます。まず$\$\alpha$を終端から検索して$に対応する区間[beg, end]にたどり着いたとします。この時に[beg+1, end+1]と範囲を1つ下にずらしてBackward searchを続けることで$\beta\$\alpha$の検索が可能となります。
その他の操作についてもアイデアはとても単純です。興味ある方は元論文を読んでみてください。

実装メモ

圧縮データ構造に興味のある方々のために実装メモを残しておきます。
圧縮率よりも検索速度を重視して設計しました。LF Mappingでのocc関数計算のためにハフマン型ウェーブレット木を利用しています。最近流行りのウェーブレット行列を使う手もあるのですが、文字コードを1バイト単位（つまりアルファベットサイズは256以下）として処理しているので、ポインタベースのウェーブレット木を利用したほうが良いです。ハフマン型ウェーブレット木は出現頻度の高い文字に対するクエリを高速に計算でき、0次エントロピーオーダーと同等の圧縮率を実現できます。ウェーブレット木では各ノードのビット列に対するRank操作が必要なのですが、これは岡野原さん謹製のBitVectorを使わせてもらっています。検索速度よりも圧縮率を重視したい場合には、BitVectorを圧縮したり、Compression Boostingのテクニック（以下の論文参照）を使うことでさらに圧縮できるでしょう。

Veli Mäkinen and Gonzalo Navarro.
“Implicit Compression Boosting with Applications to Self-Indexing”, Proc. SPIRE’07 214-226, 2007.

Juha Kärkkäinen and Simon J. Puglisi.
“Fixed Block Compression Boosting in FM-Indexes”, Proc. SPIRE’11, 174-184, 2011.