大規模テキスト索引（suffix array）の構築法とその情報検索への応用 suffix array構築アルゴリズムと実装定兼邦彦東京大学理学系研究科情報科学専攻内容 • suffix array(接尾辞配列)とは • 関連研究 – Bentley, Sedgewick 97 – Manber, Myers 93 • Larsson, Sadakaneのアルゴリズム – 計算量 – 実装 – メモリ • disk上での構成アルゴリズム • Application (proximity search) 2 記号の説明 • X = X[0..n] 文字列 • Sj j 番目の接尾辞(suffix) X[j..n] • I [0..n] 接尾辞の添字 j の配列 X = BANaNa S0 S1 S2 3 suffix array ・文字列の全てのsuffixのポインタを辞書順にソートした配列・省スペース(文字列自身と配列１つ) X suffix array 0 BANaNa 1 ANaNa 2 NaNa 3 aNa 4 Na 5a ソート I 1 0 4 2 5 3 ANaNa BANaNa Na NaNa a aNa 4 suffix arrayの特徴 • 省スペース(文字列自身と配列１つ) • 任意の部分文字列の検索が可能 – O(|P|log n) 時間 – 補助配列を使うと O(|P|+log n) 時間 • 答えの列挙が簡単 5 関連研究 • Bentley, Sedgewick 97 • Manber, Myers 93 6 Bentley, Sedgewick • quick sortの拡張(<, =, >に分ける) • 実際に高速 • 冗長な文字列で極端に遅くなる – O(n2) 時間 7 t obeor not t o b e $ 0 1 2 3 4 5 6 7 8 9101112 2 3 6 11 12 2 11 b 2 11 0589 5 6 r t 5 089 1 10 7 t b r 1 10 4 7 e 1 10 12 e $ o 2 11 12 3 $ o 1 4 7 10 n e 3 12 6 11 o 11 2 $ 8 o t 09 8 b 09 e 09 10 o 10 1 h=1 h=2 h=3 h=4 $ 9 o 9 0 8 h=5 Manber, Myers • • • • doubling techniqueを用いる Radixソート O(n log n) 時間実際は遅い 9 doubling technique [Karp, Miller, Rosenberg 72] • 長さ 1, 2, 4, 8, ...の部分文字列に番号を割り当てる t obeor not t o b e $ 64124534664 1 2 0 h=1 9 5 1 3 6 8 4 710 9 5 1 2 0 h=2 11 7 2 4 8105 912116 1 3 0 h=4 12 7 2 4 8105 913116 1 3 0 h=8 10 Manber, Myers t 0 13 0 o b 1 2 211 1 1 e o 3 4 312 3 3 13 21112 0 1 1 3 1311 212 0 1 2 3 3 4 3 4 r 5 6 5 n 6 1 6 o 7 4 6 6 5 6 5 110 6 6 110 6 7 t t o b e $ 8 910111213 710 5 0 8 9 6 610111111 4 8 4 8 7 5 0 9 8 810111113 7 5 0 9 8 910111113 1311 212 3 6 110 4 7 5 9 0 8 0 1 2 3 4 5 6 7 8 910111213 h=1 h=2 h=4 h=8 11 Manber, Myersの問題点 • 各反復で全ての要素を見る – O ( n log 最大反復長) – 後のほうのパスでは無駄が多い – すでにソートされている部分をスキップする • 配列1つでRadixソートを行うために遅くなっている – in-placeのソートを使う (quick sortなど) 12 ソートされた部分のスキップ t 0 13 0 13 o b e o 1 2 3 4 211 312 1 1 3 3 21112 3 1 1 3 4 1311 212 3 1 2 1311 212 3 r 5 6 5 6 n o 6 7 1 4 6 6 110 6 6 6 110 6 7 6 110 t t o b e $ 8 910111213 710 5 0 8 9 6 610111111 4 7 5 0 9 8 8 8 111113 4 7 5 0 9 8 8 9 1111 4 7 5 9 0 8 1112 h=1 h=2 h=4 h=8 13 Larsson, Sadakaneの方法 • ２つの方法を組合わせる – Bentley, Sedgewick – doubling technique 14 実験結果 Ultra60 (メモリ2GB) 時間(s) 7000 6000 新聞記事(109M) 特許 (89M) Reuters (27M) html (125M) 5000 4000 3000 2000 1000 0 Larsson Sadakane B&S M&M Kurtz 15 t obeor not t o b e $ 0 1 2 3 4 5 6 7 8 9101112 2 3 6 11 12 2 11 b 2 11 1 1 0589 6 e n 3 12 6 3 3 5 12 3 0 6 2 11 12 3 1 1 3 4 8 11 0 o 10 1 4 7 10 666 6 5 r 5 0 8 9 10 111111 1 10 7 1 10 11 1 10 4 7 6 6 8 9 4 3 11 2 1 2 10 1 6 7 t 0 6 8 0 9 11 1111 8 1 13 09 1111 9 8 9 0 11 12 h=1 h=2 h=4 16 h=8 計算量 • O(n log n)時間 • 木の根から各葉へのパス上に – <, > に対応する枝の数 log2 n +1以下 – = に対応する枝の数 log2 n +1 以下 – 1回の分割は線形時間 17 比較回数の期待値 • = に対応する枝の数は平均的には少ない log2 n • 2  log2 以下(H は文字列のエントロピー) H 2 log n 2 • Bentley, Sedgewickでは以下 H 18 実装(基本) • 配列 • アルゴリズム • 配列の更新方法 19 配列 • X[0..n] 文字列 • I [0..n] 接尾辞の添え字の配列 • V[ j ] 接尾辞 j の先頭 h 文字につける番号 = j を含むグループの左端の添え字 i • L[ i ] 辞書順で i 番目の接尾辞から始まるグループのサイズ 20 アルゴリズム • 接尾辞を先頭の1文字でグループ分け • I, V, Lの計算, h=1 1 2 3 4 5 各グループの I[i] を V[I[i]+h] に従い並び替える V が隣と異なる場合はグループを分け, Lを更新 L を見て異なるグループに異なる V を書く隣り合うサイズ1のグループを一つにし, Lを更新サイズが2以上のグループがあれば h := 2h として1に戻る 21 I の並び替え(h=1) V[I[i]+1] V[I[i]] I[i] 0 1 10 11 1 6 11 6 6 6 10 11 11 11 3 12 6 1 4 7 ｅｅｎｏｏｏｏ＄ｏｂｒｔｒｔｅｎｔｎｔｏｏｏ 10 ｏｂｅ＄ 3 3 6 0 1 1 3 3 13 2 11 ＄ｂｂｅｅｏ＄ｒ 5 6 5 ｒｎｏｔ 0 ｔｏｂｅ 8 ｔｔｏｂｔｏｂｅｏｒｎｏｔｔｏｂｅ$ 先頭の２文字でソート 22 6 9 ｔｏｂｅ I の並び替え(h=2) V[I[i]+2] 8 0 1 1 V[I[i]] 0 I[i] 13 2 3 4 3 1 1 4 5 6 6 8 9 10 11 11 13 11 12 3 6 1 10 4 7 5 0 9 8 ｏｒｎｏｏｔｔｏｒｎｏｔｔｏｂｅｔｏｂｅｔｔｏｂ＄ｂｂｅｅｎｏｏｂｅｅ＄ｏｔｅｒｏ＄ｎｔｏｒｏｂｅ＄ｔｏｂｅｏｒｎｏｔｔｏｂｅ$ 先頭の４文字でソート 23 I の並び替え(h=4) V[I[i]+4] 8 V[I[i]] 0 I[i] 13 11 2 1 2 3 0 4 5 6 7 8 9 10 11 11 13 12 3 6 10 1 4 7 5 0 9 8 ｎｏｔｔｏｂｅ＄ｏｒｎｏｏｔｔｏｒｎｏｔｔｏｂｅｏｒｔｏｂｅ＄ｔｔｏｂ＄ｂｂｅｅｅｅ＄ｏｒ＄ｏｎｒｏｂｅｏｔｏｂｅｏｒｎｏｔｔｏｂｅ$ 先頭の８文字でソート 24 I の並び替え(h=8) V[I[i]] 0 I[i] 13 11 2 1 2 3 4 5 6 7 8 9 10 11 12 13 12 3 6 10 1 4 7 5 9 0 8 ｎｏｔｔｏｂｅ＄ｏｒｎｏｏｔｔｏｒｎｏｔｔｏｂｅｏｒｔｏｂｅ＄ｔｔｏｂ＄ｂｂｅｅｅｅ＄ｏｒ＄ｏｎｒｏｂｅｏｔｏｂｅｏｒｎｏｔｔｏｂｅ$ ソート終了 25 Lの更新 X t o I 0 1 L 1 2 V 0 1 L 1 2 V 0 1 L-11 V 0 1 L-14 V 0 1 b e o 2 3 4 2 1 3 3 -3 1 3 4 r 5 1 5 n 6 4 6 2 5 6 o t t o b e $ 7 8 910111213 h=1 1 3 6 6 610111111 2 1 2 1 h=2 6 8 810111113 2 1 h=4 2 3 4 5 6 7 8 910111113 h=8 2 3 4 5 6 7 8 910111213 26 実装(改良) • 1パス化 – I, V, L の更新を一度に行う • L (グループのサイズの配列)を消去 – V で L を表す 27 1パス化 • I を並び替える際に V を更新 – – – – <, =, > に分割 > を再帰的にソート = の V を更新 < を再帰的にソート • 更新の順番が重要 – V は常に大きくなるので < を先に更新すると順序が狂う 28 t obeor not t o b e $ 0 1 2 3 4 5 6 7 8 9101112 2 3 6 11 12 2 11 b 2 11 1 1 0589 6 e n 3 12 6 3 3 5 12 3 0 6 2 11 12 3 1 1 3 4 8 11 0 o 10 1 4 7 10 666 6 5 r 5 0 8 9 10 111111 1 10 7 1 10 11 1 10 4 7 6 6 8 9 4 3 11 2 1 2 10 1 6 7 t 0 6 8 0 9 11 1111 8 1 13 09 1111 9 8 9 0 11 12 h=1 h=2 h=4 29 h=8 L の消去 • V[ j ] = j を含むグループの左端の添え字 i j を含むグループの右端の添え字 i • <, =, > の順に V を更新 • スキップするグループのサイズは I に格納 – スキップされる接尾辞の I は使われない • 最後に V から I を復元 – I[V[ j ]] = j 30 t o b e o r 0 1 2 3 4 5 I-1 211 312-1 V0 2 2 4 4 5 -1 211-3 0 2 2 3 4 5 -11 0 1 2 3 4 5 -14 0 1 2 3 4 5 n o 6 7 1 4 9 9 110 7 7 t t o b e $ 8 910111213 710-1 0 8 9 9 910131313 4 7-1 0 9-1 9 910121213 0 9-1 6 7 8 910121213 h=1 h=2 h=4 h=8 6 7 8 910111213 31 アルゴリズム (改良版) 各反復で i=0 while (i  n) { s = I[ i ] if (s < 0) i = i - s else { // ソート済みグループをスキップソート済みグループを連結 I [i .. i+V[i] ] をソート i = i + V[i] + 1 // i を次のグループの先頭に } } 32 メモリ • 必要なメモリ • ディスク上での構成 33 必要メモリ • • • • Bentley, Sedgewick Manber, Myers Larsson, Sadakane Kurtz 5n (8n) 8n 8n >13n 34 Suffix arrayのディスク上での構成 • Gonnet, Baeza-Yates, Snider 92 – diskはsequential accessのみ 2 n 2 MB I/O (M: メモリサイズ, B: ページサイズ) • Crauser, Ferragina 98 – doubling algorithm + discarding n n log2 n(logM / B ) B M I/O 35 Doubling technique + discarding • doubling technique • log2 n 回の反復 • M/B-way マージソートを用いるメモリ内と異なる点 • すでにソートされている部分はスキップ 36 現実的な方法 • 文字列を分割 • メモリ内でsuffix arrayを作る • disk上のsuffix arrayにマージする – メモリ内のsuffixを辞書順にdisk上に挿入 • disk上の文字列がメモリに入るなら速い 37 さらなる高速化 • 伊東の方法[2]と組み合わせる – suffixを2種類に分割 – 片方をBentley, Sedgewickなどでソート – もう片方はRadixソート 38 Application (proximity search) • 指定したキーワードが近くに現れている場所を見つける • 検索結果を絞れる • 近くに現れている関連がある – 「今井」+「ホームページ」+「東京」 – 「samba」+「98」 39 参考文献 [1] N. J. Larsson and K. Sadakane. Faster Suffix Sorting. Technical Report LU-CS-TR:99-214, LUNDFD6/(NFCS3140)/1-20/(1999), Department of Computer Science, Lund University, Sweden, May 1999. http://www.cs.lth.se/home/Jesper_Larsson/ [2] 伊東秀夫. 大規模テキストに対する Suffix Array の効率的な構成法. SIGNL-129-5, IPSJ, January 1999. 40