酒居敬一(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など持ち込み不可 学生証必携 持っていない場合は教務で発行してもらうこと