スライド 1

演習第2回
最終変更 7/14
本講義の評価


試験
演習第2回
演習第2回: 文字列検索



入力:
 A : 参照文字列 (長い)
 q1, q2, …, qm : 問い合わせ文字列(短いのがたくさん)
出力:
 各qmに対してその出現位置すべて(ない場合もある)
基本的な解法は今後説明するが, “Suffix Array”という手法
を使う. 以下が要素技術
 整列
 2分探索
進行





おそらく来週(7/11)に説明を終え, その次再来週(7/16 (土曜
日))に演習を行う
一回で完了するものではない．その後も課題として継続する
「大きなデータを高速に」処理できることに情熱を燃やす．そ
のためにあらゆる工夫をすることを期待する
 アルゴリズム
 プログラミング上の工夫
結果(速度)を報告するウェブページを設けて, 途中結果を共
有する
後日まとめのレポートを提出
Suffix



(ある文字列Aの)接尾辞(suffix)とは, その文字列のある部分
から最後までの部分文字列を言う
 例: 「も」「もも」「すもも」はどれも「すもも」のsuffix
Aをn文字の文字列としたとき, Aのsuffixは明らかにn個ある
 i文字目から最後までのsuffixを Siと書くことにする
例: A = すもも
 S0 = すもも
 S1= もも
 S2=も
Suffix Array

(ある文字列Aの)接尾辞配列(suffix array) とは, 0, 1, …, n –
1 を以下を満たす順序 <A で整列したものである
i <A j  Si <lex Sj

ただし <lex は文字列の辞書式順序を表す
言い換え

Aのsuffixを辞書式に整列し, その順序にしたがってsuffixの「
添え字」を整列させたもの
i <A j  Si <lex Sj

例: A = MOMOKO
0
M
O
M
O
K
1
O
M
O
K
O
2
M
O
K
O
3
O
K
O
4
K
O
5
O
O
4
K
O
2
M
O
K
O
0
M
O
M
O
K
5
O
3
O
K
O
1
O
M
O
K
O
O
要するに


概念的にはAのsuffixすべてを整列させたもの
ただし個々のsuffixは元の文字列における「位置」であらわさ
れている
 用途(検索)を考えれば当然
 メモリ量の節約
作るべきもの二つ



Aからsuffix array (以降SA)を作る関数
 mk_suffix_array(“MOMOKO”, 6)  { 4,2,0,5,3,1 }
A, そのsuffix array SA, 問い合わせ文字列qが与えられたとき
, qのAにおける出現位置を返す関数
 sa_search(“MOMOKO”, {4,2,0,5,3,1}, “MO”)  { 0, 2 }
注: 課題ではreference stringからquery stringを探索する以外
の規定はない. APIも, アルゴリズムも, (極端にいえばsuffix
arrayを使うかどうかも)自分の判断で変更してよい
基本となる方法

mk_suffix_array(A, n)
 0, 1, 2, …, n – 1 が一度ずつ現れる配列を準備
 その配列を整列. ただしその際の「不等号(x < y)」の意味
を少しかえる

x < y  Sx <lex Sy

sa_search(A, SA, q)
 SAを2分探索の要領で検索して, qをprefixに持つ(先頭部
分に含む)suffixを見つける. それには以下を満たすb, eを
見つける




SSA[b] < q  SSA[b+1]
SSA[e]  q < SSA[e+1]
ここで < ()は, 最初の|q|文字だけを比べた(以降はないものとみな
す)際の辞書式順序
b, eが見つかれば答えは { SA[b+1], SA[b+2], …, SA[e] }

ただし問題の仕様ではこれを(整数として)小さい順に配列に格納
する. つまりAの中で前から現れる順に答える.
sa_searchの図解


sa_search( “MOMOKO”, SA, “OK”) = { 3 }
| “OK” | = 2 最初の2文字限定でsuffix arrayを2分探索
 SSA[3] < q  SSA[4] ( O < q  OK)  b = 3
 SSA[4]  q < SSA[5] (OK  q < OM)  e = 4
4
K
O
2
M
O
K
O
0
M
O
M
O
K
5
O
3
O
K
O
1
O
M
O
K
O
O
KO < OK
MO < OK
MO < OK
O < OK
OK = OK
OK < OM
計算量は?




mk_suffix_arrayはn要素の整列だからO(n log n)?
sa_searchはn要素の2分探索だからO(log n)?
どのようなAやqに「弱い」?
それらを改良したアルゴリズムも知られている
ライブラリの利用について



課題の趣旨から考えて“Suffix Array構築プログラム”をまる
ごとどこかから拾ってくるとかいうのは当然ダメ
2分探索(bsearch), 整列(qsort)などを利用するのは??
 これを自分で実装するというのも課題の趣旨なのでダメと
します
 ただし, 「これを使わないとどうしてもできませんでした」と
いう人に限り, それらを利用したプログラムの提出も認め
る(注: おそらくbsearchは今回の目的には使えない)
 プログラムはいくつ提出してもよいことにする. 自分で作成
した版がある限り, 他の版でそれらの関数を用いるのも可
課題の趣旨は「色々試行錯誤, 頑張ること」
C言語ヒント






Aを文字列とするとき, Aのi文字目以降は, A + i (もしくは
&A[i])でOK (ポインタの足し算)
A
A+2
つまりsuffix SiはA + i でOK
M O M O K O \0
二つの文字列A, Bを辞書式順序で比べるには, strcmp(A, B)
先頭 x 文字限定で比べるには, strncmp(A, B, x)
これらは使ってもOK
ただし自分で実装しても大した手間ではない
 文字の比較は通常の < でOK





次回(7/16 土曜日)は演習の時間とする
 ただしそれ以前に作り始めることを期待
 一回の時間内に終わる課題ではない
Webページ準備中 m(_ _)m
データ生成関数(Cで書かれたもの)を提供
 練習用
 本選計測用
自分で書いたプログラム中からそれらの関数を呼び出して利用
メモリぎりぎりの大きなデータを想定してください
 reference string ×5+ query strings = 1.5GBなど

Download Report