東京大学大学院情報理工学系 コンピュータ科学専攻修士1年 (辻井研) 岡野原 大輔 hillbig@is.s.u-tokyo.ac.jp 現実的な圧縮付全文索引 東京大学大学院情報理工学系 コンピュータ科学専攻修士1年 (辻井研) 岡野原　大輔 hillbig@is.s.u-tokyo.ac.jp

発表の流れ 背景 既存技術 圧縮付全文索引技術 転置ファイル Suffix Arrays / Suffix Trees Static Dictionary 圧縮付全文索引技術 CSA CST IIWT

発表の流れ 背景 既存技術 圧縮付全文索引技術 転置ファイル Suffix Arrays / Suffix Trees Static Dictionary 圧縮付全文索引技術 CSA CST IIWT

背景 膨大な情報を現実的なリソースで 処理可能な索引が必要 膨大な量のテキスト情報を解析したい！ これらのデータから有用な情報を抽出したい！ Webデータ 80億ページ >1PB MEDLINE（医学系論文集） >50GB 解析済ゲノム情報 >800G base 特許文書/対訳コーパス/チャット・掲示板ログ　・・ これらのデータから有用な情報を抽出したい！ 自然言語処理/機械学習を適用したい 単語やパタンがどこに出現しているか索引付けが必要 G@ogleのように大量の計算クラスタは使えない. 　膨大な情報を現実的なリソースで 　処理可能な索引が必要

圧縮付全文索引とは 全文索引 圧縮付全文索引 検索対象テキストT[1…N]に前もって索引付けを行うことで、単語の出現位置をo(N)で求める 例　転置ファイル・Suffix Arrays 圧縮付全文索引 処理速度を少し犠牲にし(e.g. O(log2N)) 、索引のサイズを1/5から1/20に小さくしたもの 現在のPC　(Mem 4GB)で20GB程度まで索引付可能。計算サーバー(Mem 16GB)で80GBぐらいまでは実証済み

発表の流れ 背景 既存技術 圧縮付全文索引技術 転置ファイル Suffix Arrays / Suffix Trees Static Dictionary 圧縮付全文索引技術 CSA CST IIWT

転置ファイル 各単語やパタン毎に出現位置を記録する 転置ファイルを効率良く保存する方法として 整数符号法が使われている 本の索引と同じ 文書番号を保存する場合もある 「book」 <102,187,298,…> 「boot」 <609,1029> … 転置ファイルを効率良く保存する方法として 整数符号法が使われている

転置ファイルの保存 出現位置の差分リストを作り、それを整数符号で保存 整数符号化の例 「book」　<102, 187-102 ,298-187 ,…> 　=<102,85,111,…> 整数符号化の例　 σ、γ符号　　　　　　　　　　　 [Elias 1975]　 golomb符号 　　　　　　　　　 [Golomb 1969] rice 符号 [Rice 1979] Interpolative符号 　　　　　 [Moffat 2000] Recursive Integer Code [Moffat 2005]

Suffix Arrays [Manber 1989] 長さNの文字列T[1…N] が与えられた時、 Si= T[i…N] をTのsuffix（接尾辞)と呼ぶ。 Siを辞書式順序でソートした時のSuffix番号配列をSuffix Arraysと呼ぶ。 任意の部分列P[1…M]をO(MlogN)で検索できる S1 abraca$ S2 braca$ S3 raca$ S4 aca$ S5 ca$ S6 a$ S7 $ S7 $ S6 a$ S4 aca$ S1 abraca$ S2 braca$ S5 ca$ S3 raca$ 7 6 4 1 2 5 3 Suffix Arrays ソート

Suffix Arraysによる検索例 T=abracadabra$ P=bra 計算量は クエリー長M テキスト長Nの時 O(MlogN) Hgt配列を一緒に 使うことで O(M+logN) 11 $ 10 a$ 7 abra$ 0 abracadabra$ 3 acadabra$ 5 adabra$ 8 bra$ 1 bracadabra$ 4 cadabra$ 6 dabra$ 9 ra$ 2 racadabra$ bra > adabra$ bra = bra$ bra < cadabra$

Suffix Arraysの構築，その他 線形時間構築アルゴリズムがいくつか存在 [Ko 03] [Karkkainen 03] [Kim 03] 実際のデータで一番速いのはO(logN)のもの[Mamada 2003] [Mori 2005] [Maniscalco 2005] 近似マッチングも可能。制約付き正規表現を処理できる [Huynh 05] テキスト先頭への追加、削除も可能 ただしデータ構造は複雑になる

Suffix Trees [Weiner 1973] Suffixから構成されるTrie木を全ての節点が二つ以上の子を持つように枝を縮退させた木 葉がSuffix Arraysに対応する 各節点は頭1文字を削った節点へのLink (Suffix Link)を持つ。 $ 元データ abracadabra a ra bra bra $ d c d c d c c $ $ c 11 10 7 3 5 8 1 4 6 9 2 suffix arrays

Static Dictionary [Munro 1996] [Pagh 2001] bit配列 B[1…N]が与えられた時、o(N)領域の補助データを使って、次の操作を定数時間でサポートするデータ構造 rank1(B,i) B[1…i]中の1の数を返す select1(B,i) B[1…i]中のi番目の1の位置を返す rank0(B,i) select0(B,i)も同様に定義 圧縮索引の様々な場面で使われる

Static Dictionary の例 B = {0,0,1,1,0,0,1,1,0,1,0} rank1(B,1) = 0 select1(B,1) = 3 select1(B,3) = 7 rank0(B,2) = 2

Static Dictionaryの実装 実は、論文に書かれている方法では領域量、計算量ともにオーバーヘッドが大きすぎて不可能 現実的な実装方法[Gonzalez 2005] rank(i) はi/64単位でテーブルでもっておき、i mod 64の1の数はpopCountで求める (add 6回 shift, & 12回) selectはrankを用いて二分探索して求める rank0(B,i) = i- rank1(B,i)

64bit中の1の数を数える (C) unsigned long long popCount(unsinged long long x){ x = ((x & 0xAAAAAAAAAAAAAAAA) >>1 ) + ( x & 0x5555555555555555 ); x = ((x & 0xCCCCCCCCCCCCCCCC) >>2 ) + ( x & 0x3333333333333333 ); x = ((x & 0xF0F0F0F0F0F0F0F0) >>4 ) + ( x & 0x0F0F0F0F0F0F0F0F ); x = ((x & 0xFF00FF00FF00FF00) >>8 ) + ( x & 0x00FF00FF00FF00FF ); x = ((x & 0xFFFF0000FFFF0000) >>16) + ( x & 0x0000FFFF0000FFFF ); x = ((x & 0xFFFFFFFF00000000) >>32) + ( x & 0x00000000FFFFFFFF ); return x; }

発表の流れ 背景 既存技術 圧縮付全文索引技術 転置ファイル Suffix Arrays / Suffix Trees Static Dictionary 圧縮付全文索引技術 CSA CST IIWT

圧縮全文索引 圧縮付全文索引を紹介する。 Compressed Suffix Arrays (CSA) Vertical Code Compressed Suffix Trees (CST) Parenthesis Tree (括弧木) Inverted file Indexing with Wavelet Tree (IIWT) Wavelet Tree

Compressed Suffix Arrays (CSA) [Grossi 2001,2003][Sadakane 2003] CSAはO(NH0)bitで索引を保存可能。 H0はテキストの0次エントロピー 英文ではH0=2.5～4bit 従来のSAではNlogN bit必要 (4N Byte) 1GBのデータをSAを使って解析するには4GB必要なのに対しCSAは200MB～500MB 検索時に元テキストは必要無い 任意の部分列を復元することもできる

CSAの概要 SAはそのまま保存すると4N(8N)byte SAは1からNまでのPermutationなので圧縮も難しい SAの代わりにΨを保存する。 Ψ[i] = SA-1 [SA[i] + 1]　ただしΨ[0]=SA-1[0] SA[j]=i の時　SA-1[i] = j SAは一定間隔おきに保存。SA[i]を求める時はΨを使って、SAが保存されているところまで移動。 SA[i]= SA[Ψ[i]]-1 = SA[Ψ2[i]]-2 .. = SA[Ψn[i]]-n もし、 SA[Ψn[i]] = p なら SA[i] = p-n

Ψの性質 先頭文字が同じSuffixの間ではΨ[i]は単調増加 「現在i番目にあるSuffixの次の文字から始まるSuffixの順位」 Ψ[i] = SA-1[SA[i] + 1] 「現在i番目にあるSuffixの次の文字から始まるSuffixの順位」 定理 T[SA[i]] = T[SA[j]], i<j　ならばΨ[i] < Ψ[j] SAではSuffixが辞書式順序に並んでいる。もし、二つのSuffix Si、Sjの1文字目が同じなら、2文字目以降で順位が決定しているはず。 この時、Si+1< Sj+1 。つまり SA-1[SA[i]+1] < SA-1[SA[j]+1]　(Ψ[i] < Ψ[j]) 先頭文字が同じSuffixの間ではΨ[i]は単調増加

i 0 1 2 3 4 5 6 7 8 9 10 11 SA 11 10 7 0 3 5 8 1 4 6 9 2 Ψ 3 0 6 7 8 9 10 11 5 2 1 4 Suffix $ a$ abra$ abracadabra$ acadabra$ adabra$ bra$ bracadabra$ cadabra$ dabra$ ra$ racadabra$ ΨはSuffixの先頭文字が同じなら単調増加。 一文字目が同じ時、二文字目で比較しているから。

i 0 1 2 3 4 5 6 7 8 9 10 11 SA 11 10 7 0 3 5 8 1 4 6 9 2 Ψ 3 0 6 7 8 9 10 11 5 2 1 4 SA[i] mod 4 = 0 のものだけ保存 SA[7]= SA[Ψ[7]]-1 = SA[11]-1 = SA[Ψ[11]]-2 = SA[4]-2 = SA[Ψ[4]]-3 = SA[8]-3 = 4-3 = 1 SA[i]=SA[Ψ[i]]-1を使う

Ψをどのように保存するか 単調増加列なので、転置ファイルの時と同様に差分列を作り整数符号化を行う。 d[i] = Ψ[i+1]-Ψ[i] d[i]をγ符号を用いた場合、O(NH0)で保存可能なことが示されている[Sadakane 2003]. 一定間隔置きに、Ψをサンプリングしておき、任意のΨを求める場合はd[i]を足し合わせて求める Ψ[i] = Ψ[k]+d[k]+d[k+1]+…+d[i-1]

Vertical Code [Okanohara 2005] (to appear) 一回ずつγ符号を復元し、それを足し合わせる操作は計算コストが大きい Σi=1..Nd[i]を高速に求められる符号法 基になったアイディアはRecursive Integer Code [Moffat 2005] Vertical Codeは全てByte単位で処理が可能 (c.f. Range Coderは算術圧縮符号をByte単位の処理で行うことで算術圧縮符号より数十倍高速に処理可能)

Vertical Codeの概要 d[1…N]をM個ずつBlockに分ける d[1…M],d[M+1…2M],d[2M+1…3M],.. それぞれのBlock中の最大値の最上位bitの位置をMaxbit[i]とする。 MaxBit[1] = log2(Max(d[1],…,d[M]))+1 MaxBit[2] = log2(Max(d[M+1],…,d[2M]))+1 i番目のBlockの要素のk bit目をつなげたbit列をV[i][k]とする V[1][1] = d[1]&1,d[2]&1, V[1][2] = (d[1]>>1)&1,(d[2]>>1)&1

Vertical Codeの概要(続) MaxBit[], V[i][1…Maxbit[i]],Ψ[iM]を保存する (M=8の時、これらが全てByte単位で表現されることに注意) Ψ[t] = Σi=1…td[i] を求めるには， j = i / M k = i mod M x = Ψ[jM] for (i = 1; i <= Maxbit[j]; i++) x += popCount(V[j][i] & ((1 << k) – 1))<< i

Vertical Codeの例 Ψ[1…8]={3,6,12,15,18,21,28,31} d [1…8]={3,3,6,3,3,3,7,3} 3 3 6 3 3 3 7 3 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1bit目 V[1][1] V[1][2] 2bit目 3bit目 V[1][3] 3 = 0112

Vertical Codeの例 Ψ[6]を求める Ψ[6]= d[1]+d[2]+…d[6] = popCount(V[1][1] & ((1<<6)-1)) + popCount(V[1][2] & ((1<<6)-1)) << 1 + popCount(V[1][3] & ((1<<6)-1)) << 2

Compressed Suffix Trees (CST) [Sadakane 2005] T[1…N]のSuffix Treesを|CSA|+6N bitで表現 英文テキストで2Byte / 文字 [Okanohara 2005] 普通に保存すると100N bit　程度 Suffix Treeの全機能をシミュレート可能 肝となるのは木構造の圧縮表現 Suffix TreeではT[1…N]のテキストの場合，木の節点個数はN+1個以上2N-1個以下 木構造をそのままポインタで表現すると12 NByte以上

括弧木 [Jacobson 1989] [Raman 2001][Geary 2004] 木を深さ優先探索で辿った時、 入った時’(‘、出た時’)’を出力した時の括弧列 findclose(i) iの位置の括弧に対応する閉じ括弧の位置を返す findopen(i) iの位置の括弧に対応する開き括弧の位置を返す enclose(i) iの位置をもっともきつく囲む括弧対の開き括弧の位置を返す (()(()()))

括弧木を用いた木の操作の実現 (()(()())) parent(i) = enclose(i) child(i) = i+1 sibling(i) = findclose(i)+1 (()(()()))

括弧木の実装 （（）（（（ ））（）（） ）（）） 括弧列をM個ずつブロックに分ける 括弧を3種類に分ける near　対応する括弧対が同一ブロック内に存在 far　　 nearではない pioneer farであり、かつ直前のfarとは違うブロックに対応する括弧対が存在する （（）（（（ ））（）（） ）（）） （ pioneer ( far

括弧木の実装（続） （（）（（（ ））（）（）（ ））（）） (()()) 対応する括弧がpioneerならば、その括弧もpioneerとする。 括弧対を結んだ線が交差しないことからブロック数がBの時、pioneerである括弧の個数は4B-6で抑えられる。 pioneerである括弧のみからなる括弧列を再帰的に構築してく （（）（（（ ））（）（）（ ））（）） (()())

括弧木の使用例 findclose(i) iの括弧の種類で場合わけ 全て定数時間で実現 near → 前もって求めておいた結果表を参照 pioneer　→　pioneer括弧列の答えを使う far　 →　直前のpioneerを求め、対応する括弧対 　　　　　 が存在するブロックを求める。 　　　　　　　　　直前のpioneerまでの開き括弧の個数と 　　　　　　　　 閉じ括弧の個数の差を求めて表参照 全て定数時間で実現

Inverted file Indexing with Wavelet Tree (IIWT) [Okanohara　2005] (to appear) 転置ファイルの索引を圧縮 登録パターン種類数を|Σ|，総回数をMとした時 O(Mlog|Σ|)で保存可能 （正確には登録パターンの0次エントロピーをH0としたときMH0bit) 以下の操作をO(H0)の計算量で実現 パターンのi回目の出現位置 パターンの指定した区間内での出現回数 N=10GB M=1G |Σ| = 1024の時 1GBで保存可能

Wavelet Tree [Grossi 2003] 元々CSA, FM-indexに使われていたデータ構造 アルファベット集合Σからなるテキスト列T[1…N]が与えられた時、任意の文字a∈Σのrank, selectをO(log|Σ|)で求めることができるデータ構造 Static Dictionaryは|Σ|=2の時 必要な領域量はO(NH0)

Wavelet Treeの例 Σ={a,b,c} a = 02 b = 102 c = 112 T= abbccbaacbab 1 a b c abbccbaacbab 011111001101 1 bbccbcbb 00110100 a 1 b c

Wavelet Treeの例 rankb(8)=3 Σ={a,b,c} a = 02 b = 102 c = 112 T= abbccbaacbab 1 a b c rankb(8)=3 abbccbaacbab 011111001101 rank1(8)=5 bbccbcbb 00110100 rank0(5)=3 a b c

IIWT this book is interesting. 1000010000100100000000000 パターンの先頭位置では1、そうでない場合は0であるbit配列T’を考える 出現パターンを順に並べたパターン列T’’[1…M]を作ってWavelet Treeを構築 任意の範囲内[a…b]でのパタンpの出現回数は定数時間で求められる rankp(b)- rankp(a) パタンpでのi番目の出現位置はselectp(T’,i)で求められる this book is interesting. 1000010000100100000000000

IIWTの長所/短所 長所 短所 構築に必要なメモリ量はパタン種類数O(log|Σ|) (CSAは構築に必要なメモリがO(N)) ) データの順序情報を失わず、任意パタンの出現回数、位置を圧縮表現できる (転置ファイルは順序情報の復元は難しい) 短所 任意部分列の検索は難しい

まとめと今後 大規模なデータに対しての索引技術を「現実的」に実現した。 通常のPC(メモリ4GB)で20GB 計算クラスタ(メモリメモリ16GB)で80GB 1TB, 1PBといった情報の索引は、まだ少し工夫が必要だがそう遠くは無い。 現在800GBのゲノム、426GBのTREK Dataを実験予定 大量データを利用した自然言語処理、機械学習 Example Based Learningの復活 非教師学習で教師付き学習に匹敵する精度を出したい