簡潔データ構造 国立情報学研究所 定兼　邦彦

目次 0. 基礎 1. ビットベクトル 2. 木構造1 3. 木構造2 4. 接尾辞配列 5. 接尾辞木 6. 動的なデータ構造 7. 配列

4. 接尾辞配列

文字列用の標準的データ構造 操作 代表的データ構造 サイズ：文字列 + O(n log n) bits パタンの出現回数，場所 共通部分文字列，極大パタン アラインメント 代表的データ構造 接尾辞木 [1,2] 接尾辞配列 [3] サイズ：文字列 + O(n log n) bits ヒトのDNA配列：30億文字 (750MB) 接尾辞木：40GB

接尾辞 (suffix) 文字列 T の先頭の何文字を除いたもの (n 種類) T の任意の部分文字列は，ある接尾辞の接頭辞 = T 1 いるかいないかいないかいるかいるいるいるか 2 るかいないかいないかいるかいるいるいるか 3 かいないかいないかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 6 いかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 9 ないかいるかいるいるいるか 10 いかいるかいるいるいるか 11 かいるかいるいるいるか 12 いるかいるいるいるか 13 るかいるいるいるか 14 かいるいるいるか 15 いるいるいるか 16 るいるいるか 17 いるいるか 18 るいるか 19 いるか 20 るか 21 か

接尾辞配列 [3] 接尾辞のポインタを 辞書順にソートした配列 サイズ n log n + n log |A| bits パタン P の検索 6 いかいないかいるかいるいるいるか 10 いかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 15 いるいるいるか 17 いるいるか 19 いるか 1 いるかいないかいないかいるかいるいるいるか 12 いるかいるいるいるか 21 か 3 かいないかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 14 かいるいるいるか 11 かいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 9 ないかいるかいるいるいるか 16 るいるいるか 18 るいるか 20 るか 2 るかいないかいないかいるかいるいるいるか 13 るかいるいるいるか SA 接尾辞のポインタを 辞書順にソートした配列 サイズ n log n + n log |A| bits パタン P の検索 O(|P| log n) time

圧縮接尾辞配列 (CSA) [4,5] SA の代わりに [i] = SA-1[SA[i]+1] を格納 サイズ: O(n log |A|) bits パタン P の検索: O(|P| log n) time 0 1 7 $ 5 2 1 ababac$ 6 3 3 abac$ 7 4 5 ac$ 3 5 2 babac$ 4 6 4 bac$ 1 7 6 c$ SA  i

の計算法 接尾辞配列 SA を作る i を (T[SA[i]-1], i) の順に基数ソート  SA i=1,2,...,n に対し, c=T[SA[i]-1] を求める で c に対応する範囲に i を書く 0 1 7 $ 5 2 1 ababac$ 6 3 3 abac$ 7 4 5 ac$ 3 5 2 babac$ 4 6 4 bac$ 1 7 6 c$ SA  i

なぜ圧縮できるのか 接尾辞は辞書順に格納される 先頭の1文字を消しても辞書順は同じ  SA 12 14 15 16 17 18 19 20 21 3 4 5 9 1 2 6 7 10 11 13  6 いかいないかいるかいるいるいるか 10 いかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 15 いるいるいるか 17 いるいるか 19 いるか 1 いるかいないかいないかいるかいるいるいるか 12 いるかいるいるいるか 21 か 3 かいないかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 14 かいるいるいるか 11 かいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 9 ないかいるかいるいるいるか 16 るいるいるか 18 るいるか 20 るか 2 るかいないかいないかいるかいるいるいるか 13 るかいるいるいるか SA 接尾辞は辞書順に格納される 先頭の1文字を消しても辞書順は同じ

CSA の性質 i < j のとき T[SA[i]]  T[SA[j]] i < j より T[SA[i]+1..n] < T[SA[j]+1..n] SA[i’] = SA[i]+1, SA[j’] = SA[j]+1 とすると, i’ < j’ つまり i’ =SA-1[SA[i]+1]=[i]<[j]=j’ 0 1 7 $ 5 2 1 ababac$ 6 3 3 abac$ 7 4 5 ac$ 3 5 2 babac$ 4 6 4 bac$ 1 7 6 c$ SA  i

の符号化法 ’[i] = T[SA[i]]  n + [i] を格納 ’[i] (i = 1,2,...,n) は単調増加列になる [i] = ’[i] mod n T[SA[i]] = ’[i] div n ’[i] (i = 1,2,...,n) は単調増加列になる n(2+log ) $: 2 a: 5, 8, 9 c: 3, 4 g: 1, 6, 7 $: 000010 a: 010101, 011000, 011001 c: 100011, 100100 g: 110001, 110110, 110111

’の符号化法 ’[i] の2進表現の上位 log n ビット ’[i] の下位 log  ビットはそのまま格納 $: 2 直前の値からの差分を1進数で符号化 最大 2n ビット (1の数 = n，0の数  n) ’[i] の下位 log  ビットはそのまま格納 n log  bits $: 2 a: 5, 8, 9 c: 3, 4 g: 1, 6, 7 $: 000010 a: 010101, 011000, 011001 c: 100011, 100100 g: 110001, 110110, 110111 1, 000001, 01, 1, 001, 01, 0001, 01, 1 10, 01, 00, 01, 11, 00, 01, 10, 11

’の復号 ’[i] = x   + y 時間計算量： O(1) 上位桁： x = select(H,i)  i 下位桁： y = L[i] ’[i] = x   + y 時間計算量： O(1) 領域計算量： n(2+log ) + O(n log log n/log n) $: 2 a: 5, 8, 9 c: 3, 4 g: 1, 6, 7 H: 1, 000001, 01, 1, 001, 01, 0001, 01, 1 L: 10, 01, 00, 01, 11, 00, 01, 10, 11

の圧縮 [i] を T[SA[i]] で分割 各 S(c) を符号化： 全体で H0  log  (等号は p1 = p2 = … のとき) ( :文字 c の出現確率)

要素 SA[i]のアクセス方法 i が log n の倍数のときに SA[i] を格納 k = 0; w = log n;  SA while (i % w != 0) i = [i]; k++; return SA2[i / w] - k;  i SA 0 8 0 1 7 $ 5 2 1 ababac$ 6 3 3 abac$ 7 4 5 ac$ 3 5 2 babac$ 4 6 4 bac$ 1 7 6 c$ SA2 0 8 1 3 2 4 アクセス時間: 平均 O(log n) 時間

SA[i]が log n の倍数のものを SA2 に格納 B[i]=1  SA[i] が log n の倍数 SA[i]が log n の倍数のものを SA2 に格納 10 8 9 11 13 15 1 6 7 12 14 16 2 3 4 5  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 B 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 T E B D E B D D A D D E B E B D C SA 8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11 SA2 2 3 4 1 k = 0; w = log n; while (B[i] != 0) i = [i]; k++; return SA2[rank (B,i)]w  k; B : n+o(n) ビット アクセス時間: O(log n) 時間

の階層的表現 レベル i では T 中の連続する 2i 文字を1つの文字とみなす 文字列のエントロピーは増えない B 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 0 T E B D E B D D A D D E B E B D C SA 8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11 BD EB DD AD DE BE BD C$ SA1 4 7 1 6 8 3 5 2 BDEB DDAD DEBE BDC$ SA2 2 3 4 1

データ構造のサイズ レベル数が 1/ のとき : 1/  n(3+H0) bits SA1/ : n/log n  log n = n bits B:  n + n/2 + n/4 + ...  2n bits 合計: bits SA[i] の計算: 時間

部分文字列の検索 二分探索時に実際のSAの値は必要ない T E B D E B D D A D D E B E B D C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 　　10 8 9 11 13 15 1 6 7 12 14 16 2 3 4 5  r 1 2 2 2 2 3 4 4 4 4 4 4 5 5 5 5 D 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 SA 8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11 A B B B B C D D D D D D E E E E D D D D E A C D D E E B B B B C D E A E B B D D D E D E C D E 1 2 3 4 5 C A B C D E

後方検索 P=P[1..p] の検索 for (k = p; k >=1; k--)  SA 0 1 7 $ C[$]=[1,1] C[a]=[2,4] C[b]=[5,6] C[c]=[7,7] P=P[1..p] の検索 for (k = p; k >=1; k--) 0 1 7 $ 5 2 1 ababac$ 6 3 3 abac$ 7 4 5 ac$ 3 5 2 babac$ 4 6 4 bac$ 1 7 6 c$ SA  i O(p log n) time

の値で二分探索: O(log n) time P の検索に O(|P| log n) time

テキストの部分的な復元  T[9..13] = DDEBEを復元する場合 i=SA-1[9]=10 を求める 1 2 3 4 5 C A B C D E 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 T E B D E B D D A D D E B E B D C A B B B B C D D D D D D E E E E  10 8 9 11 13 15 1 6 7 12 14 16 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 SA 8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11

圧縮接尾辞配列の機能 lookup(i): SA[i] を返す (O(log n) 時間) inverse(i): SA-1[i] を返す (O(log n) 時間) [i]: SA-1[SA[i]+1] を返す(O(1) 時間) substring(i,l): T[SA[i]..SA[i]+l-1]を返す O(l) 時間 (i からT[SA[i] は長さ n のベクトルのrankで求まる)

CSAの問題点 サイズが n(H0(S)+O(1)) bits nHk(S)+o(n) にしたい

ブロックソート圧縮法 Burrows, Wheeler 1994 [6] gzipよりも高圧縮率, PPM [7] に迫る 伸張はさらに高速 データの配布に適する

ブロックソート圧縮法 ababac$ c$bbaaa 3441411 BW変換 接尾辞ソート MTF変換 2 0 10 3 0 11 4 00 100 5 00 101 MTF変換 3441411 ハフマン符号 算術符号 δ符号 011 00100 00100 1 00100 1 1

接尾辞配列 T = acagcagg$ acagcagg$ $ 1 9 cagcagg$ acagcagg$ 2 1 agcagg$ SA acagcagg$ cagcagg$ agcagg$ gcagg$ cagg$ agg$ gg$ g$ $ $ acagcagg$ agcagg$ agg$ cagcagg$ cagg$ g$ gcagg$ gg$ 1 2 3 4 5 6 7 8 9 9 1 3 6 2 5 8 4 7 辞書順に ソート

BW変換 T = acagcagg$ BW = g$ccaggaa BW[i] = T[SA[i]1] g $ 9 ソートした各接尾辞の1つ前の文字を並べたもの T の並び替えになる BWから T を復元可能 BWは圧縮しやすい g $ $ acagcagg c agcagg$ c agg$ a cagcagg$ g cagg$ g g$ a gcagg$ a gg$ 9 1 3 6 2 5 8 4 7

逆BW変換 T は BW から復元できる SA も復元できる [8] g $ c a acagcagg$ agcagg$ agg$

FM-index [9] BWだけでパタン検索が可能 P=P[1, p] を検索 g $ c a 1 2 3 4 5 6 7 8 9 c = P[p] l = C[c]+1, r = C[c+1] while (--p  0) { l = C[c]+rankc(BW,l1)+1 r = C[c]+rankc(BW,r) } $: 0 a: 1 c: 4 g: 6 C [l,r] は P の辞書順

LF mapping g $ c a 1 2 3 4 5 6 7 8 9 LF[5]=C[a]+ranka(BW,5) =1+1 =2 SA[5]=2 SA[2]=2-1 1つ前の接尾辞の辞書順を表す C $ a b c 0 1 4 6

BW をウェーブレット木で格納すれば，rankを O(log /log log n) 時間で計算できる パタン検索が O(|P| log /log log n) 時間 BWのサイズ: nH0(BW) + O(n log /log log n) bits lookup/inverseの索引を d 個おきにすると サイズ: O(n log n/d) bits 時間: O(d log /log log n) サイズを o(n) にするために d = log1+ n とする

文字列の高次圧縮 BW変換後の文字列では，同じ文脈を持つ文字が集まっている 各文脈ごとに H0 まで圧縮 ⇒全体では Hk を達成 g $ $ acagcagg c agcagg$ c agg$ a cagcagg$ g cagg$ g g$ a gcagg$ a gg$ 文脈 = $ 文脈 = a 文脈 = c 文脈 = g

まとめ: FM-index  = polylog(n) とする 索引サイズ: nHk(S) + o(n) bits パタンの検索: O(|P|) time lookup/inverse: O(log1+ n) time 長さ l の部分文字列の復元: O(l + log1+ n) time

CSAとFM-indexの関係 両者は同じものを表している 片方でもう一方を模倣できる  $: 010000000 (2) $: 010000000 (2) a: 000010011 (5, 8, 9) c: 001100000 (3, 4) g: 100001100 (1, 6, 7) BW: g$ccaggaa 

 は BW 上のselectで求まる LF, BW は  回の  の後方探索で求まる t:  を求める時間 tLF: LF を求める時間 ts: BW でのselectを求める時間

参考文献 [1] P. Weiner. Linear Pattern Matching Algorithms. In Proceedings of the 14th IEEE Symposium on Switching and Automata Theory, pages 1–11, 1973. [2] E. M. McCreight. A Space-economical Suffix Tree Construction Algorithm. Journal of the ACM, 23(12):262–272, 1976. [3] Udi Manber, Gene Myers. Suffix arrays: a new method for on-line string searches, Proc. SODA, 1990. [4] R. Grossi and J. S. Vitter. Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching. SIAM Journal on Computing, 35(2):378–407, 2005. [5] Kunihiko Sadakane: New text indexing functionalities of the compressed suffix arrays. J. Algorithms 48(2): 294-313 (2003). [6] M. Burrows, D. Wheeler. A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, 1994.

[7] John G. Cleary, Ian H. Witten: A comparison of enumerative and adaptive codes. IEEE Transactions on Information Theory 30(2): 306-315 (1984) [8] Kunihiko Sadakane: A Modified Burrows-Wheeler Transformation for Case-Insensitive Search with Application to Suffix Array Compression. Data Compression Conference 1999: 548 [9] P. Ferragina and G. Manzini. Indexing compressed texts. Journal of the ACM, 52(4):552–581, 2005.