省スペースな圧縮接尾辞配列構成アルゴリズム

全文

(1)アルゴリズム 81−3 （２００１．１１．２７）. 省スペースな圧縮接尾辞配列構成アルゴリズム定兼邦彦1. 宋永健2. 姚兆明3. 林徳華3. 1. 東北大学大学院情報科学研究科システム情報科学専攻. 2. 〒 980-8579 仙台市青葉区荒巻字青葉 09 [email protected] 香港大学電子商業科技研究所 [email protected]. 3. 香港大学計算機科学及資訊系統系. {smyiu,twlam}@csis.hku.hk. 文字列検索のための索引として接尾辞配列が有名であるが，そのサイズが問題となっている．圧縮接尾辞配列はそれを圧縮したもので，通常は元の文字列よりもサイズが小さくなる．ただし圧縮接尾辞配列を構成するアルゴリズムとしては一旦接尾辞配列を構成するものしか存在しないため，一時的だが大量のメモリが必要となる．本研究では長さ n の文字列に対し，O(n) ビットの一時記憶を用いる O(n|Σ| log n) 時間 (|Σ| はアルファベットサイズ) のアルゴリズムを提案する．このアルゴリズムは短い文字列に対する圧縮接尾辞配列から長い文字列に対するものを徐々に作成するものになっており，データの追加を容易に行える点も利点である．. A Space-economical Algorithm to Construct the Compressed Suffix Arrays. 1 2 3. Kunihiko Sadakane1 Wing Kin Sung2 Siu Ming Yiu3 Tak Wah Lam3 Department of System Information Sciences, Graduate School of Information Sciences, Tohoku University, Aoba-yama09, Aoba-ku, Sendai 980-8579, Japan E-Business Technology Institute, The University of Hong Kong Department of Computer Science and Information Systems, The University of Hong Kong Though the suffix array is now famous as an index for string matching, it has a problem of its size. The compressed suffix array is a compressed version of the suffix array whose size is usually smaller than the size of the string. However all known algorithms construct the compressed suffix arrays via uncompressed suffix arrays, which temporarily occupy huge amount of memory. This paper proposes an O(n|Σ| log n) time algorithm to construct a compressed suffix array of a string of length n on alphabet Σ using only O(n) bits temporal space. This is an incremental algorithm, which construct the compressed suffix array of a concatenation of a character and a string from that of the string. Therefore this algorithm also has the merit of appending data quickly.. −19− 1.

(2) はじめに. 1. 文字列データの量は増えつづけているため，高速なパタン検索のためにはあらかじめ索引を作成しておくことが必要である．接尾辞木は理論的には優れた索引であり，様々な文字列アルゴリズムで用いられているが [3]，索引サイズが非常に大きいため実用的ではない．一般には文字列サイズの 12 倍以上の領域が必要である．そのため接尾辞木よりもコンパクトである接尾辞配列 [4] が用いられているが，索引サイズは文字列の 4 倍とまだ大きい．最近になって接尾辞配列の圧縮法 [2, 1, 5] が提案された．これらの手法を用いると，接尾辞配列を文字列のサイズと同程度に圧縮できる．よって，大量の文字列データに対しても索引を保存することが現実的となった．文字列の長さを n，Σ をアルファベットとすると，文字列のサイズは n log2 |Σ| ビットである．一方，接尾辞配列のサイズは n log2 n ビットであるため，文字列よりもかなり大きくなる．通常は文字列は 8n ビット，接尾辞配列は 32n ビットであるため，接尾辞配列は文字列の 4 倍のスペースを占める．しかし上記の圧縮法を用いると接尾辞配列のサイズが文字列と同じオーダになり，通常は元の文字列よりも小さく圧縮できる．ただし，これらの接尾辞配列の圧縮法では一旦未圧縮の接尾辞配列を構成した後にそれを圧縮する方法をとっているため，大量の記憶領域を必要とする．本論文では圧縮接尾辞配列を構成する省スペースなアルゴリズムを提案する．一旦接尾辞配列を構成する方法では O(n log n) 時間で構成できるが，2n log2 n ビット (通常 8n バイト) の領域が必要である．一旦接尾辞木を構成する方法では O(n) 時間で構成できるが，12n バイト以上の領域が必要である．本研究のアルゴリズムで必要な記憶領域は，圧縮接尾辞配列のサイズの他に O(n) ビットのみである．時間計算量は O(n|Σ| log n) である．また，このアルゴリズムはインクリメンタルなものであるため，文字列が追加された場合にも高速に索引を構成することができる．. 圧縮接尾辞配列. 2 2.1. 接尾辞配列. 長さ n の文字列 T 中の文字を T [i] (i = 1, 2, . . . , n) で表す. アルファベットを Σ で表す．Σ 中の文字には全順序が定義されている．文字列の最後 T [n + 1] に終端記号 $ を加える．$ は Σ 中にはない文字で，それらよりも小さい順位を持つとする．T の接尾辞 Th (h = 1, 2, . . . .n) を文字列 T [h..n + 1] = T [h]T [h + 1] · · · T [n + 1] と定義する．T の接尾辞配列とは, 接尾辞の添え字 j を接尾辞の辞書順にソートした配列で, SA[1..n] で表す．この配列は要素が 1 から n の値であるため各要素に log2 n ビット必要であり，全体で n log2 n ビット必要である．接尾辞配列 SA と文字列 T を用いると，二分探索により任意のパタン P (長さ m) の T 中の出現頻度. occ を O(m log n) 時間で求めることができ，その後 P の出現位置は O(occ) 時間で求めることができる．. 2.2. 圧縮接尾辞配列. 圧縮接尾辞配列は接尾辞配列を圧縮したものである．接尾辞配列は単なる配列であるが，圧縮接尾辞配列. (CSA) では接尾辞間の関係を利用して要素を圧縮するため，復元は O(log n) 時間かかる1 ．CSA は lookup， inverse，decode という 3 つの基本的な関数を持つ．lookup(i) は SA[i] の値を O(log n) 時間で返す．inverse(j) は SA−1 [j] を O(log n) 時間で返す．decode(j, l) は文字列 T の長さ l の部分文字列 T [j..j +l −1] を O(l +log n) 時間で返す．decode(j, l) により T の任意の部分文字列を復元できるため，CSA を用いて接尾辞配列上での任意の演算をシミュレートできる．文字列 T の圧縮接尾辞配列は，SA の代わりに. Ψ[i] = SA−1 [SA[i] + 1] unless SA[i] = n 1 O(log. n) 時間 (0 < ≤ 1) に改善することも可能．. 2 −20−.

(3) d. γ符号. 1. 1. 2 3. 010 011. 4 5. 00100 00101. 6. 00110. 7. 00111. 図 1: γ符号で定義される Ψ 関数を格納する．Ψ 関数は nH1 + O(n) ビットで表現できる (H1 は文字列の次数 1 のエントロピー)．つまり Ψ 関数は一般的には文字列自身よりも小さくなる．これは次の性質を用いて Ψ の値を符号化するからである．. Proposition 1 任意の文字列 T の接尾辞配列に対して以下が成り立つ: • 文字 T [SA[i]](i = 1, 2, . . . , n) はアルファベット順に並んでいる． • T [SA[i]] = T [SA[j]] のとき，i < j ならば Ψ[i] < Ψ[j]．つまり Ψ は高々 |Σ| 個 (|Σ| はアルファベットサイズ) の単調増加列で表される．よって Ψ[i] の代わりに左隣の値との差分 Ψ[i] − Ψ[i − 1] をγ符号 (図 1 参照) などの自然数の表現法で符号化する．γ符号では自然数 d を 1 + 2log2 d ビットで表現できる．つまり小さい値ほど少ないビット数で表現できる．. 2.3. 圧縮接尾辞配列のデータ構造. 圧縮接尾辞配列は次の要素から構成される:. • Ψ[i] for 1 ≤ i ≤ n • I[i] = SA[i · D] for 1 ≤ i ≤ n/D • J[i] = SA−1 [i · D + 1] for 0 ≤ i ≤ (n − 1)/D • C[c]: アルファベット Σ 中の文字 c とそれより小さい文字の，文字列 T 中の累積出現頻度 D は O(log n) の定数である．D の値を大きくとると CSA のサイズが小さくなるが，lookup などの演算は遅くなる．この演算は図 2 のようになる．. Ψ[i] は左隣の値との差分で符号化されているが，i が定数 L の倍数の場合には Ψ[i] をそのまま格納する．L は O(log n) とする．これにより Ψ[i] を O(log n) 時間で計算できる．なお，この場合 lookup などの演算は平均で O(log2 n) 時間となる．. lookup(i): v := 0; while i mod D = 0 do i := Ψ[i]; v := v + 1; return I[i/D] − v;. inverse(i): p := (i − 1)/D; q := J[p]; while p · D + v < i do. v := 1;. q := Ψ[q]; v := v + 1; return q;. 図 2: Functions lookup(i) = SA[i] and inverse(i) = SA−1 [i]. 3 −21−.

(4) 圧縮接尾辞配列の省スペース構成アルゴリズム. 3. 本節では文字列 T [1..n + 1] が与えられた時に，T の圧縮接尾辞配列を構成する省スペースなアルゴリズムを提案する．アルゴリズムの実行時に必要なスペースは，圧縮接尾辞配列のサイズのほかには O(n) ビットのみである．アルゴリズムは次のようになる:. 1. Ψ 関数を構成する． 2. Ψ 関数から配列 I と J を構成する．. 3.1. Ψ 関数構成アルゴリズム. 本アルゴリズムでは Ψ 関数をインクリメンタルに構成する．つまり，接尾辞 T [n..n + 1], T [n − 1..n +. 1], . . . , T [1..n + 1] に対する Ψ 関数を順に構成していく．次の値を定義する． • Th = T [h..n + 1] • SAh [0..n − h + 1]: Th の接尾辞配列, h ≤ SA[i] ≤ n (1 ≤ i ≤ n − h + 1), SA[0] = n + 1 • Ψh [i] ≡ SA−1 h [SAh [i] + 1] (i = 1, 2, . . . , n − h + 1) Th+1 に対する Ψh+1 が与えられた時に，Th に対する Ψh を構成することを考える．Ψh+1 は Ψh から次のように計算できる:. Ψh [i] =.   Ψh+1 [i]      Ψh+1 [i] + 1     p  p+1      Ψh+1 [i − 1]     Ψ [i − 1] + 1. (1 ≤ i < x and Ψh [i] < x) (1 ≤ i < x and Ψ h [i] ≥ x) (i = x and p < x) (i = x and p ≥ x) (x < i ≤ n + 1 and Ψ h [i − 1] < x) (x < i ≤ n + 1 and Ψ h [i − 1] ≥ x). h+1. ここで x は Th が挿入される SAh+1 中の位置である．つまり Th が SAh+1 [x−1] と SAh+1 [x] (1 ≤ x ≤ n−h+2) の間に挿入されるとする．ただし x = n−h+2 の場合には, SAh+1 [x] は存在しない．また，p は SA−1 h [SAh [x]+1] で定義される値であり，SAh [x] = h であるため，p は Th+1 の挿入位置と等しい．つまり，前回の挿入位置を記憶しておけば再計算する必要はない．上記の変更を行うには，次の操作を行う必要がある:. 1. Ψh [x] = p を挿入する． 2. Ψh+1 [i] ≥ x の場合にそれらの値を 1 増やす． 3. 文字の累積頻度表 C を更新する．本論文では操作 1 を O(log n) 時間，操作 2 を O(|Σ| log n) 時間，操作 3 を O(log |Σ|) 時間で行うアルゴリズムを提案する．つまり Ψ 関数は O(n|Σ| log n) 時間で構成できる．. Ψh [x] の挿入位置 x は Th が挿入される SAh+1 中の位置と等しい． Ψ を構成するアルゴリズムは図 3 のようになる．ここで，insertionpoint(T [h], p) は Th を SAh+1 に挿入する位置を返す関数である．insert(T [h], x, p) 関数は Ψ の配列の位置 x に値 p を挿入し，x 以上の全ての値を. 1 増やすという操作を行う．. 3.2. Ψ のデータ構造. Ψ は高々 |Σ| 個の単調増加列に分割できる．T [SA[i]] = c である i に対応する列を c-リストと呼ぶことにする．各リスト中では Ψ の値は左隣との差分で表されているが，insertionpoint(T [h], p) を O(log n) 時間で計算. 4 −22−.

(5) createpsi(T ): p := 0; for h = n to 1 do x := insertionpoint(T [h], p); insert(T [h], x, p); update(x); p := x; 図 3: Ψ 構成アルゴリズム l 2. log2 n から l log2 n のブロック (l は定数) に分割する．そして各ブロックの先頭の値をそのブロックの代表元とし，無圧縮で二分木に格納する．. するために，リストを長さ. Ψh+1 から Ψh を構成する場合，T [h]-リストに対する 1 回の挿入と，各 c-リストに対してある値 x よりも大きい値を全て 1 増やすという操作を行う．実際には Ψ の値は左隣との差分で表されているため，ある 1 箇所の差分を 1 増やすだけでいい．代表元は二分木の節点に格納する．v(w) は節点 w で表される代表元の値を表す．各節点 w は次の要素を持つ:. • 左右の部分木へのポインタ • 代表元で表されたブロックを格納するビット列へのポインタ • size(w): 節点 w とその子孫で表されている Ψ の数 • dw = v(w) − v(lp(w)) 代表元の数は O(n/ log n) 個であり，二分木の各ノードは O(log n) ビットで表せるため，二分木の占めるスペースは O(n) ビットである．lp(w) は w の祖先で，w から根に向かって登っていきはじめに現れた左の親である．そのような節点が存在しない場合は lp(w) は最小の代表元を表す節点と定義する．この木を用いて. insertionpoint(T [h], p) と insert(T [h], x, p) を実現する．図 4 は代表元を格納する二分木の例である．図の下部に Ψ 関数が示されており，長さ 3 のブロックに区切られている．ブロックの先頭の値 (代表元) は太字で表されている．二分木の各節点 w は代表元に対応しており，節点の下から出る矢印はブロックへのポインタ，上から出る矢印は lp(w) を表している．節点内の左の数字は dw ，右の数字は size(w) を表している．. 3.3. insertionpoint 関数. 新しい接尾辞 Th が挿入される時には新しい Ψh の要素を挿入する必要がある．挿入位置 insertionpoint(T [h], p) を求めるには，単純な方法では接尾辞配列から Th を検索する必要があるが，Th+1 の SAh+1 中での位置 p が与えられていれば次のように計算できる:. insertionpoint(T [h], p) = argmin Ψh+1 [x] ≥ p. x∈[l−1,r+1]. ここで [l, r] は SAh+1 中の区間で，接尾辞の先頭の文字が T [h] と等しいものを含んでいる区間を表している．つまり ∀i ∈ [l, r]T [SAh+1 [i]] = T [h] が成り立つ．なお，番兵 Ψh+1 [l − 1] = −1 と Ψh+1 [r + 1] = n + 1 が存在するとする．l, r は l = C[T [h] − 1] + 1, r = C[T [h]] で計算できる．この方法により，Th の挿入位置は Ψ 関数を格納する木での二分探索により O(log n) 時間で計算できる．まず，二分木に格納された代表元を用いて挿入位置を含むブロックを O(log n) 時間で求める．次に，ブロックの中での逐次検索により挿入位置を O(log n) 時間で求める．なお，代表元の値 v(w) は節点中にそのまま格納さ. 5 −23−.

(6) 24,21. 6,9. 0,3. 14,9. 11,3. 4,3. 7,3. Ψ 1 3 4 7 10 15 18 21 22 25 26 27 28 30 33 38 41 42 45 48 49. 図 4: 代表元を格納する二分木れているわけではなく，dw = v(w) − v(lp(w)) として格納されているため，実際の値を復元しながら二分探索を行う必要がある．. v(w) の値の計算: w が根の場合には定数時間で計算できる．それ以外の場合は二分木の根から w へのパス上の各ノード z で，lp(z) を用いて v(z) を順に計算していく．二分木がバランスされていれば，v(w) は O(log n) 時間で計算できる．また，insertionpoint(T [h], p) の計算で必要な，ある値以上で最小の代表元を求める際は，二分木上で二分探索を行うが，二分探索に必要な v(z) の値は根から z へのパス上のノードでの v の値のみを用いて計算できるため，二分探索も O(log n) 時間で行える．. 3.4. insert 関数. insert 関数では insersionpoint 関数で求めた挿入位置 x に Ψh [x] = p を挿入するが，これは次のようになる: 1. x 以下で最大の代表元を表す節点 w を求める． 2. w で代表されるブロックに x を挿入する． 3. w から根の各ノード u で size(u) を 1 増やす． 4. そのブロックのサイズが l log2 n を超えた場合，そのブロックを 2 つに分割し，新しい代表元を作成し二分木に挿入する． 5. 二分木をバランスさせる．バランス木としては赤黒木を用いる．通常の赤黒木と異なる点は，lp(w) を更新する点のみである．図 5 では赤黒木の回転の例を示している．左の木を右の木に変更する場合，lp は lp(b) のみ変化し，lp(b) は lp(a) と等しくなるため定数時間で変更できる．他の回転も同様に定数時間で行える．. 6 24− −.

(7) a. b a. b. A. C B. A. C. B. 図 5: 赤黒木の回転. 3.5. update 関数. update(x) 関数では Ψh の値全てに対し，値が x 以上の場合に 1 増やすという操作を全ての c-リストに対して行う．これは次のようになる: 1. x 以下で最大の代表元を表す節点 w を求める． 2. w で表されるブロック中の要素 1 つを 1 増やす． 3. w から根の途中の節点 u に対し，u が右の親の場合には du を 1 増やす．. 3.6. Ψ から I, J の計算. I, J の計算は，Ψn から Ψ1 までの計算が終わった後に行う．接尾辞 T1 , T2 , . . . の辞書順を x = Ψ[x] により順に計算していき，x が D の倍数の時に接尾辞の添え字を I に格納し，接尾辞の添え字が D の倍数の時に辞書順 x を J に格納する．Ψ[x] の値は O(log n) 時間で計算できるため，全体で O(n log n) 時間となる．. 3.7. 必要な記憶領域. Ψ 関数のサイズは O(n log |Σ|) ビットである [5]．Ψ の代表元を格納する木の節点数は O(n/ log n) 個であり，各節点のサイズは O(log n) ビットであるため，木の占めるサイズは O(n) ビットである．配列 I, J も要素数が. O(n/ log n) であるため，サイズは O(n) ビットである．よって領域計算量は圧縮接尾辞配列のサイズ+O(n) ビットである．. 4. まとめ本論文では圧縮接尾辞配列を構成する省スペースなアルゴリズムを提案した．必要な記憶領域は，圧縮接尾. 辞配列のサイズの他に O(n) ビットである．時間計算量は O(n|Σ| log n) 時間である．これはアルファベット. Σ が大きいときには遅くなるため，改善する必要がある．これは今後の課題とする．. −25− 7.

(8) 謝辞本研究は第一著者が香港大学滞在中に行われました．滞在費用を負担してくださった香港大学計算機科学及資訊系統系に感謝いたします．. 参考文献 [1] P. Ferragina and G. Manzini. Opportunistic Data Structures with Applications. In 41st IEEE Symp. on Foundations of Computer Science, pages 390–398, 2000. [2] R. Grossi and J. S. Vitter. Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching. In 32nd ACM Symposium on Theory of Computing, pages 397–406, 2000. [3] D. Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997. [4] U. Manber and G. Myers. Suffix arrays: A New Method for On-Line String Searches. SIAM Journal on Computing, 22(5):935–948, October 1993. [5] K. Sadakane. Compressed Text Databases with Efficient Query Algorithms based on the Compressed Suffix Array. In Proceedings of ISAAC’00, number 1969 in LNCS, pages 410–421, 2000.. 8 −26−.

(9)