アルゴリズムとデータ構造1

アルゴリズムとデータ構造
2011年7月12日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html
1
文字列の照合
(298ページ)
テキストとパターンの長さをそれぞれn,mとしたとき、
それぞれ次のように配列で与えられているとする。
char[] text = new char[n];
char[] pattern = new char[m];
文字列照合あるいは文字列探索とは、テキストとパターンに関して
次のような関係の成り立つposを求めることである。
pattern[0]  text[ pos]
pattern[1]  text[ pos  1]

pattern[m  1]  text[ pos  m  1]
2
素朴なアルゴリズム
(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]){
一致しなければ、1文字
continue shift;
ずらしてやりなおし
}
}
return i;
最後まで一致したら終了
}
return -1;
}
}
3
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 = "テキスト";
c = match(a.toCharArray(), b.toCharArray());
System.out.println("「" + a + "」「" + b + "」 " + c);
a = "KMPアルゴリズムの比較の回数は、最大2n回である。つまり計算量は…";
b = "、最大";
c = match(a.toCharArray(), b.toCharArray());
System.out.println("「" + a + "」「" + b + "」 " + c);
a = "Dijkstraって読むの難しいよね。ダイクストラって発音するんだよ。";
b = "偉い人なんだよ。";
c = match(a.toCharArray(), b.toCharArray());
System.out.println("「" + a + "」「" + b + "」 " + c);
a = "アルゴリズムとデータ構造";
b = "オペレーティングシステム";
c = match(a.toCharArray(), b.toCharArray());
System.out.println("「" + a + "」「" + b + "」 " + c);
}
「テキスト内でパターンが見付かったか」「パターン」 6
「計算量を気にしなければ、この問題の解法はいとも簡単である。」「テキスト」 -1
「KMPアルゴリズムの比較の回数は、最大2n回である。つまり計算量は…」「、最大」 16
4
「Dijkstraって読むの難しいよね。ダイクストラって発音するんだよ。」「偉い人なんだよ。」 -1
「アルゴリズムとデータ構造」「オペレーティングシステム」 -1
素朴なアルゴリズムは時間計算量はO(mn)。
実装が簡単なので実行したときの性能はそう悪くない。
a
a
a
a
a
a
≠
a
≠
a
≠
= = = = =
a
b
a
b
a
b
一致したという情報を再利用すれば、比較回数が減る。
そこで、t文字一致した後に不一致が検出されたとき、
パターンをテキストに対してどれだけ進めればいいか、
パターンのどこから比較を開始すればいいかを求めておく。
a
a
a
a
a
a
≠
a
≠
a
≠
= = = = =
a
b
a
b
a
b
テキストとパターンの
比較は不一致のあった
ところからになる。
テキストストリームの
逆戻りがない。
5
Knuth-Morris-Pratt
のアルゴリズム(301ページ)
• あらかじめパターンを調べておいて
不一致が起きたときに、比較回数を減らす
べく、次の比較位置を決定する。
• 比較中のテキストの文字位置に戻りがない。
• 後述のBMアルゴリズムほどではないが、
素朴なアルゴリズムより実行性能は良い。
6
a
b
c
a
a
b
a
b
a
a
b
a
c
c
c
b
テキスト
パターン
3文字目で不一致
b
a
b
a
b
a
2文字目で不一致
b
a
4文字目で不一致
b
a
b
a
b
a
1文字目で不一致
b
1文字目で不一致
0
1
0
1
Pascal的添え字
-1
0
-1
0
Java的添え字
next配列の内容
7
a
b
d
e
a
a
b
c
a
b
d
f
a
b
a
b
パターン
-1 0 0
先 先 先
頭 頭 頭
か か
ら ら
全 全
く く
一 一
致 致
な な
し し
0
先
頭
か
ら
全
く
一
致
な
し
0
先
頭
か
ら
1
文
字
一
致
1
先
頭
か
ら
1
文
字
一
致
1
先
頭
か
ら
2
文
字
一
致
2
先
頭
か
ら
全
く
一
致
な
し
0
先
頭
か
ら
1
文
字
一
致
1
先
頭
か
ら
2
文
字
一
致
2
先
頭
か
ら
3
文
字
一
致
3
先
頭
か
ら
全
く
一
致
な
し
0
先
頭
か
ら
1
文
字
一
致
1
先
頭
か
ら
2
文
字
一
致
2
先
頭
か
ら
1
文
字
一
致
1
先
頭
か
ら
2
文
字
一
致
変数t
-1
0
-1
1
0
2
-1
0
0
3
-1
0
2
0
0
0
next配列
(Java)
•パターンの中で、パターン先頭から始まる部分文字列が
パターン中に現れるかどうかを調べる。
•これまで一致していた部分文字列の有無、不一致文字が部分文字列
のどこ含まれているかどうかで操作を決定する。
8
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)){
(j-2)文字の一致が見られたときに、
while((j >= 0) && (text[i] != pattern[j])){
j = next[j];
パターンを少しずらせて比較を続ける
}
i++; j++;
}
テキストの中で、パターンと
if(j < pattern.length) return -1;
return i - j;
現在比較しているところを指す。
}
i=0から単調増加である。
public static int match(char[] text, char[] pattern){
int[] next = new int[pattern.length];
kmpinit(pattern, next);
return kmpmatch(text, pattern, next);
9
}
}
Boyer-Mooreのアルゴリズム
(304ページ)
• あらかじめパターンを調べておいて
不一致が起きたときに、比較回数を減らす
べく、次の比較位置を決定する。
– 2つの作戦により、比較回数を減らす。
– KMPアルゴリズムでは少なくとも1回は、テキスト
の文字を調べないといけないが、この方法では
1回も調べない文字が存在する。その分速い。
• パターンは後ろから比較する。
10
作戦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
a
b
比べるだけ無駄
c
図5.1.5 作戦1(その2)
1文字目が一致するので、
2文字目以降比べる意味はある
11
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);
}
}
12
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);
}
13
}
作戦2
パターンの比較を末尾から行うということを除けば、
KMPアルゴリズムと考え方は同じ。
a
b
a
b
テキスト
b
c
a
b
3文字目
で不一致
a
b
c
a
b
無駄
a
b
c
a
b
無駄
a
b
c
a
b
図5.1.10 作戦2(その1)
a
x
b
b
a
b
2文字目
で不一致
a
b
a
b
無駄
a
b
a
b
無駄
a
b
a
b
無駄
a
b
a
b
図5.1.11 作戦2(その2)
14
×
文字の並びが同じ
部分がある
(ただし、○≠△)
少しずらせる。
○
図5.1.12 場合1
△
×
文字の並びが同じ
部分が少しある
○
図5.1.13 場合2
かなりずらせる。
×
文字の並びが同じ
部分がない
○
図5.1.14 場合3
15
public class BoyerMoore {
private static void bminit(char[] pattern, Map<Character, Integer> skip, int[] next){
int[] g = new int[pattern.length];
int j;
nextを求める
for(j = 0; j < pattern.length; j++){
next[j] = 2*pattern.length - j - 1; // length + (length - j - 1)
}
j = pattern.length;
教科書のm-jに
for(int k = pattern.length - 1; k >= 0; k--, j--){
相当するJava表現
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;
for(j = 0; j < pattern.length; j++){
next[j] = Math.min(next[j], s + pattern.length - j - 1);
if(j >= s){
s = g[s];
}
}
skipを求める
for(j = 0; j < pattern.length - 1; j++){
skip.put(pattern[j], pattern.length - j - 1);
}
}
16
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);
}
17
期末試験
• 教室: C101
• 日時: 2011年7月25日16時30分~18時00分
– 入室限度: 16時50分まで
– 退出可能: 17時00分より
• 持ち込み可
– 教科書・資料(自筆・コピー問わず)は持ち込み可
– 人間・パソコン・携帯電話・PHSなど持ち込み不可
• 学生証必携
– 持っていない場合は教務で発行してもらうこと
18