ALG2010-13

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

Download Report