アルゴリズムとデータ構造 III 9 回目 : 月 9 日 全文検索アルゴリズム (Simple Serh, KMP) 授業資料 http://ir.s.ymnshi..jp/~ysuzuki/puli/lgorithm/index.html 授業の予定 ( 中間試験まで ) / スタック ( 後置記法で書かれた式の計算 ) / チューリング機械, 文脈自由文法 / 構文解析 CYK 法 / 構文解析 CYK 法 / 構文解析 ( チャート法 ) /8 構文解析 ( チャート法 ), グラフ ( ダイクストラ法, DPマッチング ) /9 グラフ (A* アルゴリズム,DPマッチング) 時限 B- 8 / グラフ ( DPマッチング ), 前半のまとめ 9 / 中間試験 授業の予定 ( 中間試験以降 ) /9 全文検索アルゴリズム (simple serh, KMP) 中間試験の結果 / 全文検索アルゴリズム (BM, Aho-Corsik) / 全文検索アルゴリズム (Aho-Corsik), データ圧縮 / 暗号 ( 黄金虫, 踊る人形 ) 符号化 ( モールス信号, Zipfの法則, ハフマン符号 ) テキスト圧縮 / テキスト圧縮 (zip), 音声圧縮 (ADPCM,MP,CELP), 画像圧縮 (JPEG) / 期末試験 受験者 平均点 満点獲得者数 今年 年度 9 年度 人 人 8 点 人 8 点 人 8 年度 9 人 9 点 人 年度 8 人 点 人 得点 9 8 中間試験の結果 年度 9 年度 8 年度 年度 中間試験結果 9 9 9 9 9 成績順位 問題別得点結果 問毎の平均点 スタック 問 文脈自由文法 オートマトン教科書例題. 問 9.8 問.. CYK 法 問 8. 問 トップダウンチャート法 問 問 問 問
中間試験の解答例 http://ir.s.ymnshi..jp/~ysuzuki/puli/lgorithm/ の 月 日の授業資料 本日のメニュー 全文検索アルゴリズム 全文検索とは simple serh 動作の説明 アルゴリズム KMP 動作の説明 アルゴリズム 全文検索 文書中から, 与えられた文字列と完全に一致する部分を探し出す. 全文検索の種類 文字列照合による全文検索 索引を用いた全文検索 全文検索 文書中から, 与えられた文字列と完全に一致する部分を探し出す. 全文検索の種類 文字列照合による全文検索 索引を用いた全文検索 文字列照合タスク テキストに キーワードが含まれているか? その出現は? テキスト処理には不可欠 タスク例テキストTからキーワードKを見つける テキストT:x キーワードK: 8 9 答えキーワードは含まれているか :YES 出現 : 文字目から始まる文字列と9 文字目から始まる文字列 x 8 9 文字列照合アルゴリズム Simple Serh Knuth-Morris-Prtt 法 Boyer-Moore 法 Aho-Corsik 法
文字列照合問題の単純な解決法 Simple Serh Simple Serh の文字列照合手順 Simple Serh のアルゴリズム Simple Serh の評価 単純な文字列照合アルゴリズム Simple Serh テキストの 文字目から n 文字目まで, 文字目から n+ 文字目まで, がキーワードと一致するかどうかをチェックする.(n: キーワードの文字数 ) 8 9 8 9 x 文字目からの照合 回目の照合で失敗 文字目からの照合 回目の照合で失敗 文字目からの照合 回目の照合で失敗 文字目からの照合 照合成功!! 文字目からの照合 回目の照合で失敗 は照合失敗箇所は文字照合に成功は文字列照合に成功 Simple Serh text 照合回数 同じ部分を何度も照合しなければならない 8 9 8 9 x x 文字照合失敗 文字照合成功 Simple Serh のアルゴリズム 入力 : テキスト (text), キーワード (key) 出力 : テキスト中のキーワードの m: テキストの長さ n: キーワードの長さ Method egin for i:= to m-n+ do 起点を決めて egin for j:= to n do キーワードと 字ずつ照合 if text[i+j-] key[j] then 照合に失敗したらループを抜ける goto ; print i; 出現を表示 : Simple Serh 最も効率の悪い場合 key = text = text 照合回数 文字照合回数 (-+)*= (m-n+)*n 回一般に m n なので O(mn) Knuth-Morris-Prtt 法 (KMP 法 ) Simple Serh テキスト文字列中の各文字がキーワードと複数回照合される 冗長 KMP 法 文字照合の実行中に次回の文字照合を考慮しつつ処理を進める 文字照合中, バックトラックの必要がない
Knuth-Morris-Prtt 法 次にキーワードの何文字目から照合すればよいか Key: next 8 9 8 9 text x x (keyの 文字目で照合失敗 ) キーワードの 文字目に対応している ( 照合成功 ) Keyの 文字目から ( 照合成功 ) Keyの 文字目から (keyの 文字目で照合失敗 ) Keyの 文字目から Keyの 文字目から KMP 法アルゴリズム m :textの長さ n :keywordの長さ i: textの照合 Method KMP J: keywordの照合 egin j:=; for i:= to m do egin while j> nd key[j] text[i] do j:=next(j); 次の照合 if j=n then 照合成功 print i-n+: j:=j+; 照合 キーワードの接頭辞文字列の出現 関数 next: 次回の照合でキーワードの何文字目を照合すべきか テキスト文字列中の照合に失敗した文字の直前の何文字がキーワードの接頭辞になっているかを調べる キーワード キーワード next 関数値 文字目で照合失敗した場合 : 直前文字列が なので 文字目から照合開始 照合に成功した場合 : 直前文字が なので 文字目から照合開始 Keyword: のとき 文字目の で照合失敗 ( 直前の文字が ) 照合失敗箇所の右隣と : を照合 next 関数 照合失敗箇所はキーワードの 文字目と照合 next()= 文字目の で照合失敗 ( 直前の文字が ) 照合失敗箇所と : を照合 next()= 文字目の で照合失敗 ( 直前の文字が ) 照合失敗箇所と : を照合 next()= : : keywordの一文字目の : 以外の文字 next 関数 Keyword: のとき : : keywordの一文字目の : 以外の文字 文字目の で照合失敗 ( 直前の文字が ) 照合失敗箇所の右隣と : を照合 照合失敗箇所はキーワードの 文字目と照合 next()= 文字目の で照合失敗 ( 直前の文字が ) 照合失敗箇所と : を照合 next()= 文字目の で照合失敗 ( 直前の文字が ) 照合失敗箇所と : を照合 next()= 文字目の で照合成功 ( 直前の文字が ) 照合失敗箇所 ( 照合成功末尾の右隣 ) と : を照合 next()= KMP 法アルゴリズム next 関数入力 : キーワード key, 出力 :next 関数 n : keyの長さ Method next j : keyの照合 egin t : keyのj 文字目の直前の何文字がkeyの接頭辞になっているか t:=; next():=; for j:= to n do keyの各文字に対してnext 関数値を計算 egin while t nd key[j] key[t] do t:=next(t); keyのj 文字目までの文字列がkeyの t:=t+; 接頭辞と一致しているか調べる if key[j+]=key[t] then keyの next(j+):=next(t); j+ 文字目の else next 関数値を next(j+):=t; 決定
KMP 法の評価 KMP 法 漸近的時間計算量 O(m) next 関数が必要 Simple Serh 法 漸近的時間計算量 O(mn) m: テキストの文字数 n: キーワードの文字数 テキスト文字列の各文字に対して 回照合 テキスト文字列の各文字に対してキーワード文字数回照合