情報工学概論 (アルゴリズムとデータ構造) 第13回

文字列検索 情報検索で必須の処理 データ量が莫大 サーチエンジン ゲノム情報処理 Web: >20億ページ, 数テラバイト DNA配列: ヒト=28億文字, 総計>150億文字 ゲノム情報処理の例は渋谷君が話す。 だからここではパタンの出現位置を求めることが必要 ということを言う。

文字列検索問題 文字列 T の i 番目の文字を T[i], i 番目から j 番目の文字からなる文字列を T[i..j] と表記する 文字列 T の長さを |T| と書く 文字列 P が, ある i と j に対して P = T[i..j] となっているとき,　P は T の部分文字列であるという. また, T の i 文字目は P とマッチするという 文字列検索問題は，文字列 P と文字列 T を入力 し, P が T の部分文字列となっている場所, つまり P = T[i..j] となる i を全て見つける問題

文字列検索アルゴリズム 逐次検索 索引検索 P と T が与えられてから問題を解く 絶対に O(|P|+|T|) 時間かかる KMP法，BM法，Z法など 索引検索 T が予め与えられたとき，何らかのデータ構造 D を 作っておく．P が与えられたときに D を用いて問題 を高速に解く 転置ファイル，接尾辞木，接尾辞配列など

逐次検索アルゴリズム 文字列マッチングを簡単に解こうと思ったら, 各 i について P = T[i..i+|P|1] となるかどうかを 調べればよい O( |T|  |P| ) 時間のアルゴリズムができる もう一工夫して速くする方法を考える Z アルゴリズム 最も単純な線形時間 (O(|T|+|P|)) アルゴリズム

定義: 文字列 S と位置 i > 1 に対し，Zi(S) を S の i 文字目から始まる部分文字列で, S の 接頭辞と一致するものの中で最長のものの 長さと定義する． 例： S = aabcaabxaaz のとき Z2(S) = 1 (aa…ab) Z5(S) = 3 (aabc…aabx) Z6(S) = 1 (aa…ab) Z9(S) = 2 (aab…aaz) Z10(S) = 1 (aa…az) それ以外は Zi(S) = 0

定義: i > 1 かつ Zi(S) > 0 のとき，i でのZ-boxを 区間 [i, i+Zi(S)1] と定義する 定義: i > 1 に対し，ri を 1< j  i でのZ-boxの 右端点の最大値と定義する．また，li をそのとき の j と定義する．(j が複数ある時はどれでも可) 例： S = a a b c a a b x a a z のとき Z は O(|S|2) 時間で計算できる O(|S|) 時間で計算したい 1 2 3 4 5 6 7 8 9 10 11 Zi 1 0 0 3 1 0 0 2 1 0 ri 2 2 2 7 7 7 7 10 10 10 li 2 2 2 5 5 5 5 9 10 10

Zi, ri, li が 1 < i  k1 に対して計算済みのとき， Zk を計算する r = rk1, l = lk1 とする k > r のとき (k がZ-boxに含まれないとき) S[k..n] と S[1..n] を1文字ずつ比較して Zk を求める Zk > 0 ならば r = k+Zk1, l = k k  r のとき (k があるZ-boxに含まれるとき) S[k]  S[l..r] S[l..r] = S[1..rl+1] より， S[k] = S[kl+1] 同様に S[k..r] = S[kl+1.. rl+1] 1 kl+1 rl+1 l k r

2つの場合が考えられる case 2a: Zkl+1 が S[k..r] の長さより小さいとき Zk = Zkl+1 case 2b: Zkl+1 が S[k..r] の長さ以上のとき S[r+1..n] と S[rk+1+1..n] を比較 (q 文字一致) Zk = qk r = q1 l = k l r k 1 kl+1 rl+1    l r k 1 kl+1  ? rl+1

定理: 全ての Zi は O(|S|) 時間で求まる 文字列の比較は必ずミスマッチで終わる ⇒ミスマッチの回数はループの回数以下 マッチの回数を見積もる． 1回の文字列比較で q 文字マッチしたとすると， r は少なくとも q 増加する．また，r は減少しない． r  |S| よりマッチの回数は |S| 以下．

Z アルゴリズム S = P$T とする．(|P|  |T| とする) Zi(S) を計算する O(|P|+|S|) 時間 Zi(S) = |P| ならば P は S の部分文字列 i は必ず T の中になる ⇒ P は T の部分文字列 そのままだと O(|P|+|S|) 領域だが，O(|P|) にできる Zi(S)  |P| なので，参照される Zi はO(|P|)領域で格納可

索引検索 Web検索のように，決まった文字列に対して 何度も検索を行う場合は，索引検索の方が高速 単語索引 全文検索 決まった単語のみを検索できる 索引のサイズが小さい 転置ファイル 全文検索 任意の部分文字列を検索できる 索引が大きくなる 接尾辞木，接尾辞配列 ゲノム情報処理の例は渋谷君が話す。 だからここではパタンの出現位置を求めることが必要 ということを言う。

転置ファイル 文字列を単語(形態素)に分解 単語ごとに出現位置(出現文書)を列挙 出現回数も記憶 1 4 8 12 15 19 1 4 8 12 15 19 T = いるか|いないか|いないか|いるか|いるいる|いるか いるか: 3回 (1, 12, 19) いないか: 2回 (4, 8) いるいる: 1回 (15) T = いるかいないかいないかいるかいるいるいるか

文字列検索の問題点 任意の文字列を検索したい 部分文字列の数 = nC2 = O(n2) 全ての部分文字列を索引に格納

接尾辞 (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 か

接尾辞木 [Weiner 73] 全ての接尾辞を格納したcompacted trie い か な る 6 いかいないかいるかいるいるいるか 10 いかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 15 いるいるいるか 17 いるいるか 19 いるか 1 いるかいないかいないかいるかいるいるいるか 12 いるかいるいるいるか 21 か 3 かいないかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 14 かいるいるいるか 11 かいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 9 ないかいるかいるいるいるか 16 るいるいるか 18 るいるか 20 るか 2 るかいないかいないかいるかいるいるいるか 13 るかいるいるいるか い か な る

接尾辞配列 [Manber, Myers 93] 接尾辞のポインタを辞書順にソートした配列 SA 6 いかいないかいるかいるいるいるか 10 いかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 15 いるいるいるか 17 いるいるか 19 いるか 1 いるかいないかいないかいるかいるいるいるか 12 いるかいるいるいるか 21 か 3 かいないかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 14 かいるいるいるか 11 かいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 9 ないかいるかいるいるいるか 16 るいるいるか 18 るいるか 20 るか 2 るかいないかいないかいるかいるいるいるか 13 るかいるいるいるか SA 1 いるかいないかいないかいるかいるいるいるか 2 るかいないかいないかいるかいるいるいるか 3 かいないかいないかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 6 いかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 9 ないかいるかいるいるいるか 10 いかいるかいるいるいるか 11 かいるかいるいるいるか 12 いるかいるいるいるか 13 るかいるいるいるか 14 かいるいるいるか 15 いるいるいるか 16 るいるいるか 17 いるいるか 18 るいるか 19 いるか 20 るか 21 か

接尾辞配列を用いた検索 SA の上で二分探索 P = いるか 3回 (1, 12, 19) SA 6 いかいないかいるかいるいるいるか 10 いかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 15 いるいるいるか 17 いるいるか 19 いるか 1 いるかいないかいないかいるかいるいるいるか 12 いるかいるいるいるか 21 か 3 かいないかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 14 かいるいるいるか 11 かいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 9 ないかいるかいるいるいるか 16 るいるいるか 18 るいるか 20 るか 2 るかいないかいないかいるかいるいるいるか 13 るかいるいるいるか 6 いかいないかいるかいるいるいるか 10 いかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 15 いるいるいるか 17 いるいるか 19 いるか 1 いるかいないかいないかいるかいるいるいるか 12 いるかいるいるいるか 21 か 3 かいないかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 14 かいるいるいるか 11 かいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 9 ないかいるかいるいるいるか 16 るいるいるか 18 るいるか 20 るか 2 るかいないかいないかいるかいるいるいるか 13 るかいるいるいるか 6 いかいないかいるかいるいるいるか 10 いかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 15 いるいるいるか 17 いるいるか 19 いるか 1 いるかいないかいないかいるかいるいるいるか 12 いるかいるいるいるか 21 か 3 かいないかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 14 かいるいるいるか 11 かいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 9 ないかいるかいるいるいるか 16 るいるいるか 18 るいるか 20 るか 2 るかいないかいないかいるかいるいるいるか 13 るかいるいるいるか 6 いかいないかいるかいるいるいるか 10 いかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 15 いるいるいるか 17 いるいるか 19 いるか 1 いるかいないかいないかいるかいるいるいるか 12 いるかいるいるいるか 21 か 3 かいないかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 14 かいるいるいるか 11 かいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 9 ないかいるかいるいるいるか 16 るいるいるか 18 るいるか 20 るか 2 るかいないかいないかいるかいるいるいるか 13 るかいるいるいるか 3回 (1, 12, 19)

索引のサイズと検索時間 サイズ 頻度問い合わせ時間 転置ファイル < n bytes O(m) 接尾辞配列 4n bytes + |T| O(m log n) 接尾辞木 >10n bytes + |T| 注: 転置ファイルは文書が単語に分かれている場合

接尾辞配列の構築アルゴリズム 一番簡単な方法 O(n log n) 時間や O(n) 時間のアルゴリズムも存在するが，やや複雑 整数の比較ではなく，文字列の比較に変更 1回の文字列比較が O(n) 時間なので，全体で (平均) O(n2 log n) 時間 O(n log n) 時間や O(n) 時間のアルゴリズムも存在するが，やや複雑 参考: http://homepage3.nifty.com/DO/suffix_array.htm http://www.cs.sysu.edu.cn/nong/

クイックソートを用いる方法 C言語の標準ライブラリを用いる #include <stdlib.h> void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)); 大きさ size バイトの要素 nmemb 個をソートする． 要素は配列に格納され，そのポインタは base compar は2つの要素が与えられたときに大小関係を判定する関数 (自作する)

整数のソートの場合 #include <stdio.h> #include <stdlib.h> int cmpint (const void *x, const void *y) { int *xi, *yi; xi = (int *)x; yi = (int *)y; return *xi - *yi; } void main(void) { int A[14] = {27,17,3,16,13,10,1,5,7,12,4,8,9,0}; int i,n; n = 14; qsort(A, n, sizeof(int), cmpint); for (i=0; i<n; i++) printf("A[%d] = %d\n", i, A[i]);

文字列のソートの場合 typedef uchar *string; // 文字列型は文字の配列へのポインタ int cmpstr (const void *x, const void *y) {// 引数は必ず const void * 型 int c1, c2; string xs,ys; xs = *(string *)x; ys = *(string *)y; // 文字列へのポインタへ変換 // 配列の中身は文字列(文字へのポインタ) // uchar *xs, *ys; // xs = *(uchar **)x; ys = *(uchar **)y; // と書いても同じ while (1) { c1 = *xs++; c2 = *ys++; if (c1 != c2) break; // 異なる文字が現れたら終了 if (c1 == 0) break; // 文字列の最後に到達したら, 等しい (0) を返す } return c1 - c2; qsort(B, n, sizeof(string), cmpstr);

接尾辞配列を用いた文字列検索 P[1..m] を探すことを考える まず, P[1]から始まる接尾辞の範囲 [s,t] を求める 全ての i  [s,t] に対し，T[SA[i]] = P[1] である 全ての i  [s,t] に対し，接尾辞の2文字目 T[SA[i]+1] はアルファベット順に並んでいる [s,t] の範囲で T[SA[i]+1] に従って2分探索し， 2文字目が P[2] である接尾辞の範囲 [s’,t’] を 求める m 回繰り返す O(m log n) 時間

P に対応する接尾辞配列の区間 [s,t] が求まったら，P の出現位置を求めるのは容易 P の出現回数 occ に比例した時間で列挙できる 検索全体の時間計算量は O(m log n + occ)

レポート問題 以下の問題からいくつか (好きなだけ) 選び 解答すること． 提出期限 8月13日(金) 提出先 sada@nii.ac.jp までメール 受理メールが来ない場合は再送してください

問1. (キー, データ) のペアを格納するデータ構造 D について，以下の操作を行うことを考える search(D, k): D からキーが k である要素を得る insert(D, x): D にペア x を格納する delete(D, x):ペア x のポインタが与えられたとき， D から x を格納する なお，キーには全順序があるとする． これらを実現するデータ構造として， 既ソート一方向連結リスト 未ソート一方向連結リスト 既ソート双方向連結リスト 未ソート双方向連結リスト

既ソート配列 未ソート配列 2色木 が考えられる．これらの各データ構造それぞれに ついて，D の要素数が n の時の上の3つの操作の 最悪時間計算量を求めよ．データ構造の簡単な説明 も行うこと．(40点)

問2. n 個の数をソートする場合，比較に基づくどんな ソートアルゴリズムも (n log n) 回の比較が必要で あることを示せ．(30点)

問3. n 個の頂点, m 本の枝からなるグラフを表現 するデータ構造で，以下の操作を実現するものを 設計し，プログラムを作成せよ．言語は問わない． なお，頂点には 1,…,n の番号，枝には 1,…,m の 番号が付いているとする． 番号 i の頂点に隣接する全頂点の番号を列挙する 番号 j の枝の両端点の頂点番号を求める サンプルプログラムを改変して利用してもいい． (40点)

問4. n 個の整数をソートするクイックソート，マージ 時間の関係を表すグラフを描き，考察せよ． (30点)

問5. 以下の問に答えよ 安定なソートとは何か 安定ではない任意のソートアルゴリズムが 与えられたとき，それを時間計算量を変化させ ずに安定なソートアルゴリズムにする方法を 与えよ．(ヒント:各要素に何らかの情報を付加) (40点)

問6. 2色木のプログラムを次のように改変せよ． 現在のプログラムでは z が左の子の場合と右の子 の場合で左右対称なほぼ同じコードが書かれている． これを1つにまとめよ． (ヒント: 左右の子をサイズ2の配列を使って表す) (40点)

問7. 以下の問に答えよ n 個の数に対しランダムに構成された2分探索木の高さが O(log n) であることを示せ 2色木の高さが O(log n) であることを示せ (30点)

問8. ソートされた整数の配列に対し，以下の操作を実現するプログラムを作成せよ． 指定されたキーが存在するかどうかを判定する 指定されたキーの順位 (小さい方から何番目か)を求める．なお，指定されたキーが複数ある場合は全ての順位を求める． (40点)

問9. 接尾辞配列を作成する O(n log n) 時間または O(n) 時間のアルゴリズムを実装せよ． (60点)