Microsoft PowerPoint - アルデIII 10回目12月09日

Size: px

Start display at page:

Download "Microsoft PowerPoint - アルデIII 10回目12月09日"

れんかやまのかみしゃ
5 years ago
Views:

1 アルゴリズムとデータ構造 III 9 回目 : 月 9 日全文検索アルゴリズム (Simple Serh, KMP) 授業資料授業の予定 ( 中間試験まで ) / スタック ( 後置記法で書かれた式の計算 ) / チューリング機械, 文脈自由文法 / 構文解析 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.8 問.. CYK 法問 8. 問トップダウンチャート法問問問問

2 中間試験の解答例の月日の授業資料本日のメニュー全文検索アルゴリズム全文検索とは simple serh 動作の説明アルゴリズム KMP 動作の説明アルゴリズム全文検索文書中から, 与えられた文字列と完全に一致する部分を探し出す. 全文検索の種類文字列照合による全文検索索引を用いた全文検索全文検索文書中から, 与えられた文字列と完全に一致する部分を探し出す. 全文検索の種類文字列照合による全文検索索引を用いた全文検索文字列照合タスクテキストにキーワードが含まれているか? その出現は? テキスト処理には不可欠タスク例テキストTからキーワードKを見つけるテキストT:x キーワードK: 8 9 答えキーワードは含まれているか :YES 出現 : 文字目から始まる文字列と9 文字目から始まる文字列 x 8 9 文字列照合アルゴリズム Simple Serh Knuth-Morris-Prtt 法 Boyer-Moore 法 Aho-Corsik 法

3 文字列照合問題の単純な解決法 Simple Serh Simple Serh の文字列照合手順 Simple Serh のアルゴリズム Simple Serh の評価単純な文字列照合アルゴリズム Simple Serh テキストの文字目から n 文字目まで, 文字目から n+ 文字目まで, がキーワードと一致するかどうかをチェックする.(n: キーワードの文字数 ) x 文字目からの照合回目の照合で失敗文字目からの照合回目の照合で失敗文字目からの照合回目の照合で失敗文字目からの照合照合成功!! 文字目からの照合回目の照合で失敗は照合失敗箇所は文字照合に成功は文字列照合に成功 Simple Serh text 照合回数同じ部分を何度も照合しなければならない 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 法文字照合の実行中に次回の文字照合を考慮しつつ処理を進める文字照合中, バックトラックの必要がない

4 Knuth-Morris-Prtt 法次にキーワードの何文字目から照合すればよいか Key: next 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; 決定

5 KMP 法の評価 KMP 法漸近的時間計算量 O(m) next 関数が必要 Simple Serh 法漸近的時間計算量 O(mn) m: テキストの文字数 n: キーワードの文字数テキスト文字列の各文字に対して回照合テキスト文字列の各文字に対してキーワード文字数回照合

Microsoft PowerPoint - アルデIII 02回目10月15日

Microsoft PowerPoint - アルデIII 02回目10月15日アルゴリズムとデータ構造 III 2 回目 :10 月 15 日文脈自由文法,CYK 法授業資料 http://ir.cs.ymnshi.c.jp/~ysuzuki/lgorithm3/inde.html 1 2 3 4 5 6 7 8 9 授業の予定 ( 中間試験まで ) 10/01 スタック ( 後置記法で書かれた式の計算 ) 10/15 文脈自由文法, 構文解析,CYK 法 10/22 構文解析