酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年7月12日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html.

Slides:



Advertisements
Similar presentations
山元進.  for 文  while 文  do ~ while 文  文のネスト  break 文  continue 文.
Advertisements

アルゴリズムとデータ構造 2011年7月7日
プログラミング基礎I(再) 山元進.
アルゴリズムとデータ構造 2012年6月27日
アルゴリズムとデータ構造1 2008年7月22日
アルゴリズムとデータ構造 2012年7月26日
プログラミング基礎I(再) 山元進.
アルゴリズムとデータ構造 2012年7月19日
プログラミング基礎I(再) 山元進.
アルゴリズムとデータ構造 第9回演習解答.
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
String - 文字列 2009年10月9日 7ADD2116 佐藤洋輔.
文字列探索 2011/5/30.
アルゴリズムとデータ構造 2011年6月13日
第20章 Flyweight ~同じものを共有して無駄をなくす~
アルゴリズムとデータ構造 2011年6月20日
アルゴリズムとデータ構造 2013年7月18日
アルゴリズムとデータ構造 2012年7月12日
データ構造とプログラミング技法 (第10回) ー文字列照合(KMP法、BM法)ー.
アルゴリズムとデータ構造 2011年7月4日
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
アルゴリズムとデータ構造 2013年7月16日
データ構造とアルゴリズム 第14回 文字列の照合.
プログラミング 4 記憶の割り付け.
アルゴリズムとデータ構造1 2005年7月15日
アルゴリズムとプログラミング (Algorithms and Programming)
暗号技術 ~JAVAプログラム①~ (5週目)
コンパイラ 2012年11月15日
アルゴリズムとデータ構造1 2005年7月1日
P n ポインタの基礎 5 q m 5 7 int* p; int 型の変数を指すポインタ int* q; int 型の変数を指すポインタ int n=5, m=7; int 型の変数 int array[3]; int* pArray[3]; p = &n; ポインタにアドレスを代入しているのでOK.
アルゴリズムとデータ構造 2012年7月17日
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年7月5日
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2011年7月21日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
アルゴリズム論 (第12回) 佐々木研(情報システム構築学講座) 講師 山田敬三
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
アルゴリズムとプログラミング (Algorithms and Programming)
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
プログラミング言語論 第十一回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造 2011年7月11日
アルゴリズムとプログラミング (Algorithms and Programming)
暗号技術 ~JAVAプログラム②~ (6週目)
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造 2013年7月8日
アルゴリズムとデータ構造1 2009年6月15日
アルゴリズムとデータ構造 2012年6月25日
オブジェクト指向 プログラミング 第四回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2012年6月21日
アルゴリズムとデータ構造 2010年6月17日
Javaとは Javaとはオブジェクト指向言語でJava VM(Java仮想マシン)と呼ばれるプログラム上で動作します。
データ構造とアルゴリズム 第14回 文字列の照合.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
プログラミング演習II 2004年11月 16日(第5回) 理学部数学科・木村巌.
8.文字列処理 8.1 C#の文字列 C#では, “ABCD”のように文字列を2重引用符で挟んで指定します。ASCIIコード体系のとき,以下のような内部形式となります。 1 1 文字 ‘A’ ナル文字 1 1 文字 ‘B’ A B C D \ 文字 ‘C’ 1 1 文字 ‘D’ ナル文字‘\0’
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
ねらい 数値積分を例題に、擬似コードのアルゴリズムをプログラムにする。
計算機プログラミングI 第10回 2002年12月19日(木) メソッドの再定義と動的結合 クイズ メソッドの再定義 (オーバーライド)
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年7月12日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html

文字列の照合 (298ページ) テキストとパターンの長さをそれぞれn,mとしたとき、 それぞれ次のように配列で与えられているとする。 char[] text = new char[n]; char[] pattern = new char[m]; 文字列照合あるいは文字列探索とは、テキストとパターンに関して 次のような関係の成り立つposを求めることである。

素朴なアルゴリズム 素朴なアルゴリズムでは、テキストの最初から順に パターンと一致する部分があるかどうかを調べていく。 (299ページ) public class SimpleMatch { public static int match(char[] text, char[] pattern){ shift: for(int i = 0; i <= (text.length - pattern.length); i++){ for(int j = 0; j < pattern.length; j++){ if(text[i+j] != pattern[j]){ continue shift; } return i; return -1; 一致しなければ、1文字 ずらしてやりなおし 最後まで一致したら終了

「テキスト内でパターンが見付かったか」「パターン」 6 「計算量を気にしなければ、この問題の解法はいとも簡単である。」「テキスト」 -1 public static void main(String[] args) { String a, b; int c; a = "テキスト内でパターンが見付かったか"; b = "パターン"; c = match(a.toCharArray(), b.toCharArray()); System.out.println("「" + a + "」「" + b + "」 " + c); a = "計算量を気にしなければ、この問題の解法はいとも簡単である。"; b = "テキスト"; a = "KMPアルゴリズムの比較の回数は、最大2n回である。つまり計算量は…"; b = "、最大"; a = "Dijkstraって読むの難しいよね。ダイクストラって発音するんだよ。"; b = "偉い人なんだよ。"; a = "アルゴリズムとデータ構造"; b = "オペレーティングシステム"; } 「テキスト内でパターンが見付かったか」「パターン」 6 「計算量を気にしなければ、この問題の解法はいとも簡単である。」「テキスト」 -1 「KMPアルゴリズムの比較の回数は、最大2n回である。つまり計算量は…」「、最大」 16 「Dijkstraって読むの難しいよね。ダイクストラって発音するんだよ。」「偉い人なんだよ。」 -1 「アルゴリズムとデータ構造」「オペレーティングシステム」 -1

素朴なアルゴリズムは時間計算量はO(mn)。 実装が簡単なので実行したときの性能はそう悪くない。 a a a a a a = = = = = ≠ ≠ ≠ a b a b a b 一致したという情報を再利用すれば、比較回数が減る。 そこで、t文字一致した後に不一致が検出されたとき、 パターンをテキストに対してどれだけ進めればいいか、 パターンのどこから比較を開始すればいいかを求めておく。 a a a a a a テキストとパターンの 比較は不一致のあった ところからになる。 テキストストリームの 逆戻りがない。 = = = = = ≠ ≠ ≠ a b a b a b

Knuth-Morris-Pratt のアルゴリズム(301ページ) あらかじめパターンを調べておいて 不一致が起きたときに、比較回数を減らす べく、次の比較位置を決定する。 比較中のテキストの文字位置に戻りがない。 後述のBMアルゴリズムほどではないが、 素朴なアルゴリズムより実行性能は良い。

a b c a a b a c c c b テキスト パターン 3文字目で不一致 a b a b 2文字目で不一致 a b 4文字目で不一致 a b 1文字目で不一致 a b 1文字目で不一致 0 1 Pascal的添え字 next配列の内容 -1 0 Java的添え字

a b d e a a b c a b d f a b a b パターン -1 1 1 2 1 2 3 1 2 1 変数t 先頭 先頭から全く一致なし 先頭から全く一致なし 先頭から全く一致なし 先頭から1文字一致 先頭から1文字一致 先頭から2文字一致 先頭から全く一致なし 先頭から1文字一致 先頭から2文字一致 先頭から3文字一致 先頭から全く一致なし 先頭から1文字一致 先頭から2文字一致 先頭から1文字一致 先頭から2文字一致 next配列 (Java) -1 -1 1 2 -1 3 -1 2 パターンの中で、パターン先頭から始まる部分文字列が  パターン中に現れるかどうかを調べる。 これまで一致していた部分文字列の有無、不一致文字が部分文字列  のどこ含まれているかどうかで操作を決定する。

パターンは先頭から、 テキストは未比較の文字位置から それぞれ比較するというフラグ。 (j-2)文字の一致が見られたときに、 public class KnuthMorrisPratt { private static void kmpinit(char[] pattern, int[] next){ int t = -1; next[0] = -1; for(int j = 1; j < pattern.length; j++){ while((t >= 0) && (pattern[j-1] != pattern[t])) t = next[t]; t++; if(pattern[j] != pattern[t]) next[j] = t; else next[j] = next[t]; } private static int kmpmatch(char[] text, char[] pattern, int[] next){ int i = 0; int j = 0; while((i < text.length) && (j < pattern.length)){ while((j >= 0) && (text[i] != pattern[j])){ j = next[j]; i++; j++; if(j < pattern.length) return -1; return i - j; public static int match(char[] text, char[] pattern){ int[] next = new int[pattern.length]; kmpinit(pattern, next); return kmpmatch(text, pattern, next); パターンは先頭から、 テキストは未比較の文字位置から それぞれ比較するというフラグ。 (j-2)文字の一致が見られたときに、 パターンを少しずらせて比較を続ける テキストの中で、パターンと 現在比較しているところを指す。 i=0から単調増加である。

Boyer-Mooreのアルゴリズム (304ページ) あらかじめパターンを調べておいて 不一致が起きたときに、比較回数を減らす べく、次の比較位置を決定する。 2つの作戦により、比較回数を減らす。 KMPアルゴリズムでは少なくとも1回は、テキスト の文字を調べないといけないが、この方法では 1回も調べない文字が存在する。その分速い。 パターンは後ろから比較する。

作戦1 x テキスト パターン a b c 最初の比較で不一致 a b c 比べるだけ無駄 a b c 比べるだけ無駄 新たなるテキストからならば、 比べる意味はある a b c 図5.1.5 作戦1(その1) a テキスト パターン a b c 最初の比較で不一致 a b c 比べるだけ無駄 1文字目が一致するので、 2文字目以降比べる意味はある a b c 図5.1.5 作戦1(その2)

ハッシュテーブルを使うと簡単なので 教科書の擬似プログラムを書き換えた。 パターンに含まれる文字をキー、 スキップ量を値としている。 public class BoyerMooreMap { private static void bminit(char[] pattern, Map<Character, Integer> skip){ for(int j = 0; j < pattern.length - 1; j++){ skip.put(pattern[j], pattern.length - j - 1); } public static int bmmatch(char[] text, char[] pattern, Map<Character, Integer> skip){ shift: for(int i = pattern.length - 1; i < text.length;){ for(int j = pattern.length - 1; j >= 0; i--, j--){ if(text[i] != pattern[j]){ // 教科書のプログラム5.1.8そのまま Integer s = skip.get(text[i]); if(s == null) i += pattern.length; else i += Math.max(s, pattern.length - j); continue shift; return ++i; return -1; public static int match(char[] text, char[] pattern){ Map<Character, Integer> skip = new HashMap<Character, Integer>(pattern.length*2); bminit(pattern, skip); return bmmatch(text, pattern, skip); ハッシュテーブルを使うと簡単なので 教科書の擬似プログラムを書き換えた。 パターンに含まれる文字をキー、 スキップ量を値としている。

計算の手間はともかく、 動作の理解にはいったん元に 戻す方法も悪くない。 public class BoyerMooreMap { private static void bminit(char[] pattern, Map<Character, Integer> skip){ for(int j = 0; j < pattern.length - 1; j++){ skip.put(pattern[j], pattern.length - j - 1); } public static int bmmatch(char[] text, char[] pattern, Map<Character, Integer> skip){ shift: for(int i = pattern.length - 1; i < text.length;){ for(int j = pattern.length - 1; j >= 0; i--, j--){ if(text[i] != pattern[j]){ // 教科書の309ページにあるようにiを元に戻した場合。 i += pattern.length - 1 - j; Integer s = skip.get(text[i]); i += (s == null)? pattern.length: s; continue shift; return ++i; return -1; public static int match(char[] text, char[] pattern){ Map<Character, Integer> skip = new HashMap<Character, Integer>(pattern.length*2); bminit(pattern, skip); return bmmatch(text, pattern, skip); 計算の手間はともかく、 動作の理解にはいったん元に 戻す方法も悪くない。

パターンの比較を末尾から行うということを除けば、 作戦2 パターンの比較を末尾から行うということを除けば、 KMPアルゴリズムと考え方は同じ。 b a テキスト x b 3文字目 で不一致 2文字目 で不一致 a b c a b a b c 無駄 a b 無駄 a b c 無駄 a b 無駄 a b c a b 無駄 図5.1.10 作戦2(その1) a b 図5.1.11 作戦2(その2)

× 文字の並びが同じ 部分がある (ただし、○≠△) 少しずらせる。 ○ 図5.1.12 場合1 △ × 文字の並びが同じ 部分が少しある かなりずらせる。 ○ 図5.1.13 場合2 × 文字の並びが同じ 部分がない ○ 図5.1.14 場合3

bmmatchメソッドなどは次のページで… public class BoyerMoore { private static void bminit(char[] pattern, Map<Character, Integer> skip, int[] next){ int[] g = new int[pattern.length]; int j; for(j = 0; j < pattern.length; j++){ next[j] = 2*pattern.length - j - 1; // length + (length - j - 1) } j = pattern.length; for(int k = pattern.length - 1; k >= 0; k--, j--){ g[k] = j; while((j < pattern.length) && (pattern[j] != pattern[k])){ next[j] = Math.min(next[j], pattern.length - k - 1); j = g[j]; int s = j; next[j] = Math.min(next[j], s + pattern.length - j - 1); if(j >= s){ s = g[s]; for(j = 0; j < pattern.length - 1; j++){ skip.put(pattern[j], pattern.length - j - 1); nextを求める 教科書のm-jに 相当するJava表現 skipを求める bmmatchメソッドなどは次のページで…

public static int bmmatch(char[] text, char[] pattern, Map<Character, Integer> skip, int[] next){ shift: for(int i = pattern.length - 1; i < text.length;){ for(int j = pattern.length - 1; j >= 0; i--, j--){ if(text[i] != pattern[j]){ Integer s = skip.get(text[i]); if(s == null){ i += Math.max(pattern.length, next[j]); } else { i += Math.max(s, next[j]); } continue shift; return ++i; return -1; public static int match(char[] text, char[] pattern){ Map<Character, Integer> skip = new HashMap<Character, Integer>(pattern.length*2); int[] next = new int[pattern.length]; bminit(pattern, skip, next); return bmmatch(text, pattern, skip, next);

期末試験 教室: C101 日時: 2011年7月25日16時30分~18時00分 持ち込み可 学生証必携 入室限度: 16時50分まで 退出可能: 17時00分より 持ち込み可 教科書・資料(自筆・コピー問わず)は持ち込み可 人間・パソコン・携帯電話・PHSなど持ち込み不可 学生証必携 持っていない場合は教務で発行してもらうこと