演習第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など