Download presentation
Presentation is loading. Please wait.
1
情報工学概論 (アルゴリズムとデータ構造)
第13回
2
文字列検索 情報検索で必須の処理 データ量が莫大 サーチエンジン ゲノム情報処理 Web: >20億ページ, 数テラバイト
DNA配列: ヒト=28億文字, 総計>150億文字 ゲノム情報処理の例は渋谷君が話す。 だからここではパタンの出現位置を求めることが必要 ということを言う。
3
文字列検索問題 文字列 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 を全て見つける問題
4
文字列検索アルゴリズム 逐次検索 索引検索 P と T が与えられてから問題を解く 絶対に O(|P|+|T|) 時間かかる
KMP法,BM法,Z法など 索引検索 T が予め与えられたとき,何らかのデータ構造 D を 作っておく.P が与えられたときに D を用いて問題 を高速に解く 転置ファイル,接尾辞木,接尾辞配列など
5
逐次検索アルゴリズム 文字列マッチングを簡単に解こうと思ったら, 各 i について P = T[i..i+|P|1] となるかどうかを 調べればよい O( |T| |P| ) 時間のアルゴリズムができる もう一工夫して速くする方法を考える Z アルゴリズム 最も単純な線形時間 (O(|T|+|P|)) アルゴリズム
6
定義: 文字列 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
7
定義: 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 ri li
8
Zi, ri, li が 1 < i k1 に対して計算済みのとき, Zk を計算する
r = rk1, l = lk1 とする k > r のとき (k がZ-boxに含まれないとき) S[k..n] と S[1..n] を1文字ずつ比較して Zk を求める Zk > 0 ならば r = k+Zk1, l = k k r のとき (k があるZ-boxに含まれるとき) S[k] S[l..r] S[l..r] = S[1..rl+1] より, S[k] = S[kl+1] 同様に S[k..r] = S[kl+1.. rl+1] 1 kl+1 rl+1 l k r
9
2つの場合が考えられる case 2a: Zkl+1 が S[k..r] の長さより小さいとき Zk = Zkl+1
case 2b: Zkl+1 が S[k..r] の長さ以上のとき S[r+1..n] と S[rk+1+1..n] を比較 (q 文字一致) Zk = qk r = q l = k l r k 1 kl+1 rl+1 l r k 1 kl+1 ? rl+1
10
定理: 全ての Zi は O(|S|) 時間で求まる
文字列の比較は必ずミスマッチで終わる ⇒ミスマッチの回数はループの回数以下 マッチの回数を見積もる. 1回の文字列比較で q 文字マッチしたとすると, r は少なくとも q 増加する.また,r は減少しない. r |S| よりマッチの回数は |S| 以下.
11
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|)領域で格納可
12
索引検索 Web検索のように,決まった文字列に対して 何度も検索を行う場合は,索引検索の方が高速 単語索引 全文検索
決まった単語のみを検索できる 索引のサイズが小さい 転置ファイル 全文検索 任意の部分文字列を検索できる 索引が大きくなる 接尾辞木,接尾辞配列 ゲノム情報処理の例は渋谷君が話す。 だからここではパタンの出現位置を求めることが必要 ということを言う。
13
転置ファイル 文字列を単語(形態素)に分解 単語ごとに出現位置(出現文書)を列挙 出現回数も記憶 1 4 8 12 15 19
T = いるか|いないか|いないか|いるか|いるいる|いるか いるか: 3回 (1, 12, 19) いないか: 2回 (4, 8) いるいる: 1回 (15) T = いるかいないかいないかいるかいるいるいるか
14
文字列検索の問題点 任意の文字列を検索したい 部分文字列の数 = nC2 = O(n2) 全ての部分文字列を索引に格納
15
接尾辞 (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 か
16
接尾辞木 [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 るかいるいるいるか い か な る
17
接尾辞配列 [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 か
18
接尾辞配列を用いた検索 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)
19
索引のサイズと検索時間 サイズ 頻度問い合わせ時間 転置ファイル < n bytes O(m) 接尾辞配列
4n bytes + |T| O(m log n) 接尾辞木 >10n bytes + |T| 注: 転置ファイルは文書が単語に分かれている場合
20
接尾辞配列の構築アルゴリズム 一番簡単な方法 O(n log n) 時間や O(n) 時間のアルゴリズムも存在するが,やや複雑
整数の比較ではなく,文字列の比較に変更 1回の文字列比較が O(n) 時間なので,全体で (平均) O(n2 log n) 時間 O(n log n) 時間や O(n) 時間のアルゴリズムも存在するが,やや複雑 参考:
21
クイックソートを用いる方法 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つの要素が与えられたときに大小関係を判定する関数 (自作する)
22
整数のソートの場合 #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]);
23
文字列のソートの場合 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);
24
接尾辞配列を用いた文字列検索 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) 時間
25
P に対応する接尾辞配列の区間 [s,t] が求まったら,P の出現位置を求めるのは容易
P の出現回数 occ に比例した時間で列挙できる 検索全体の時間計算量は O(m log n + occ)
26
レポート問題 以下の問題からいくつか (好きなだけ) 選び 解答すること. 提出期限 8月13日(金)
提出先 までメール 受理メールが来ない場合は再送してください
27
問1. (キー, データ) のペアを格納するデータ構造 D について,以下の操作を行うことを考える
search(D, k): D からキーが k である要素を得る insert(D, x): D にペア x を格納する delete(D, x):ペア x のポインタが与えられたとき, D から x を格納する なお,キーには全順序があるとする. これらを実現するデータ構造として, 既ソート一方向連結リスト 未ソート一方向連結リスト 既ソート双方向連結リスト 未ソート双方向連結リスト
28
既ソート配列 未ソート配列 2色木 が考えられる.これらの各データ構造それぞれに ついて,D の要素数が n の時の上の3つの操作の 最悪時間計算量を求めよ.データ構造の簡単な説明 も行うこと.(40点)
29
問2. n 個の数をソートする場合,比較に基づくどんな
ソートアルゴリズムも (n log n) 回の比較が必要で あることを示せ.(30点)
30
問3. n 個の頂点, m 本の枝からなるグラフを表現
するデータ構造で,以下の操作を実現するものを 設計し,プログラムを作成せよ.言語は問わない. なお,頂点には 1,…,n の番号,枝には 1,…,m の 番号が付いているとする. 番号 i の頂点に隣接する全頂点の番号を列挙する 番号 j の枝の両端点の頂点番号を求める サンプルプログラムを改変して利用してもいい. (40点)
31
問4. n 個の整数をソートするクイックソート,マージ
時間の関係を表すグラフを描き,考察せよ. (30点)
32
問5. 以下の問に答えよ 安定なソートとは何か 安定ではない任意のソートアルゴリズムが 与えられたとき,それを時間計算量を変化させ ずに安定なソートアルゴリズムにする方法を 与えよ.(ヒント:各要素に何らかの情報を付加) (40点)
33
問6. 2色木のプログラムを次のように改変せよ.
現在のプログラムでは z が左の子の場合と右の子 の場合で左右対称なほぼ同じコードが書かれている. これを1つにまとめよ. (ヒント: 左右の子をサイズ2の配列を使って表す) (40点)
34
問7. 以下の問に答えよ n 個の数に対しランダムに構成された2分探索木の高さが O(log n) であることを示せ 2色木の高さが O(log n) であることを示せ (30点)
35
問8. ソートされた整数の配列に対し,以下の操作を実現するプログラムを作成せよ.
指定されたキーが存在するかどうかを判定する 指定されたキーの順位 (小さい方から何番目か)を求める.なお,指定されたキーが複数ある場合は全ての順位を求める. (40点)
36
問9. 接尾辞配列を作成する O(n log n) 時間または O(n) 時間のアルゴリズムを実装せよ.
(60点)
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.