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

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

2012

7

19

酒居敬一

([email protected])

http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html

1

文字集合と符号化

•

‒

‒

•

‒

‒

•

‒

‒

2

javac に -J-Dfile.encoding=UTF8 というオプションを与える理由

文字列の照合

（２９８ページ）

]

1 [

] 1 [

] 1 [

] 1 [

] [

] 0 [

− +

=

−

+

=

=

m pos

text m

pattern

pos text

pattern

pos text

pattern



ｃｈａｒ［］ ｔｅｘｔ ＝ ｎｅｗ ｃｈａｒ［ｎ］； 

ｃｈａｒ［］ ｐａｔｔｅｒｎ ＝ ｎｅｗ ｃｈａｒ［ｍ］；       

テキストとパターンの長さをそれぞれｎ，ｍとしたとき、

それぞれ次のように配列で与えられているとする。

( Java

char

Unicode

)

文字列照合あるいは文字列探索とは、テキストとパターンに関して 次のような関係の成り立つｐｏｓを求めることである。

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;

} }

4

最後まで一致したら終了

素朴なアルゴリズム

（２９９ページ）

素朴なアルゴリズムでは、テキストの最初から順に

パターンと一致する部分があるかどうかを調べていく。

一致しなければ、１文字 ずらしてやりなおし

ａ ｂ ｃ ａ ａ ｂ ａ ｂ ａ ｂ

ｃ

ａ ｃ ｃ ｂ

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);

}

5

「テキスト内でパターンが見付かったか」「パターン」 6

「計算量を気にしなければ、この問題の解法はいとも簡単である。」「テキスト」 -1

「KMPアルゴリズムの比較の回数は、最大2n回である。つまり計算量は 」「、最大」 16

「Dijkstraって読むの難しいよね。ダイクストラって発音するんだよ。」「偉い人なんだよ。」 -1

「アルゴリズムとデータ構造」「オペレーティングシステム」 -1

6

ａ ａ ａ ｂ

ａ ａ ａ ａ ａ ａ

＝ ≠

＝ ≠＝＝ ≠＝

ａ ａ ａ ａ ａ ｂ ａ ｂ

素朴なアルゴリズムは時間計算量はＯ（ｍｎ）。

実装が簡単なので実行したときの性能はそう悪くない。

一致したという情報を再利用すれば、比較回数が減る。

そこで、ｔ文字一致した後に不一致が検出されたとき、

パターンをテキストに対してどれだけ進めればいいか、

パターンのどこから比較を開始すればいいかを求めておく。

ａ ａ ａ ｂ

ａ ａ ａ ａ ａ ａ

＝ ≠

＝ ≠＝＝ ≠＝

ａ ａ ａ ａ ａ ｂ ａ ｂ

テキストとパターンの 比較は不一致のあった ところからになる。

テキストストリームの 逆戻りがない。

Knuth-Morris-Prattの
 アルゴリズム


（３０１ページ）

•  

不一致が起きたときに、比較回数を減らすべく、

次の比較位置を決定する。

•  

•  

素朴なアルゴリズムより実行性能は良い。

7

8

ａ ｂ ｃ ａ ａ ｂ

ａ ｂ ａ ｂ パターン

３文字目で不一致 テキスト

ａ ｂ ａ ｂ

ｃ ａ

ａ ｂ ａ ｂ

ａ ｂ ａ ｂ ｃ

ｃ ｂ

０ １ ０ １ ａ ｂ ａ ｂ

-1 ０ -1 ０

Pascal的添え字

(教科書の例)

Java的添え字

ｎｅｘｔ配列の内容

２文字目で不一致 ４文字目で不一致 １文字目で不一致 １文字目で不一致

9

パターン

先

頭 先

頭

文 字 一 致

先 頭

文 字 一 致

先 頭

文 字 一 致 先

頭 全 一 致

先 頭 全 一 致

先 頭 全 一 致

先 頭 全 一 致

先 頭

文 字 一 致

先 頭

文 字 一 致

先 頭

文 字 一 致

ａ ｂ ｄ ｅ ａ ａ ｂ ｃ ａ ｂ ｄ ｆ

先 頭 全 一 致

-1 0 0 0 -1 1 0 2 -1 0 0 3 ｎｅｘｔ配列

（Ｊａｖａ）

• パターンの中で、パターン先頭から始まる部分文字列が  パターン中に現れるかどうかを調べる。

• これまで一致していた部分文字列の有無、不一致文字が部分文字列  のどこ含まれているかどうかで操作を決定する。

先 頭

文 字 一 致

先 頭

文 字 一 致 ａ ｂ

-1 0 先 頭

文 字 一 致

先 頭

文 字 一 致 ａ ｂ

2 0 -1 0 0 0 0 1 1 2 0 1 2 3 0 1 2 1 変数ｔ

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);

} }

パターンは先頭から、

テキストは未比較の文字位置から それぞれ比較するというフラグ。

テキストの中で、パターンと

現在比較しているところを指す。

 ｉ＝０から単調増加である。

（ｊ-２）文字の一致が見られたときに、

パターンを少しずらせて比較を続ける

Boyer-Mooreのアルゴリズム


（３０４ページ）

•  

不一致が起きたときに、比較回数を減らすべく、

次の比較位置を決定する。

–  

–  

•  

11

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]){

// 教科書のプログラム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]){

// 教科書の３０９ページにあるように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);

} }

計算の手間はともかく、

動作の理解にはいったん元に 戻す方法も悪くない。

15

作戦２

図５.１.１０ 作戦２（その１）

図５.１.１１ 作戦２（その２）

テキスト

３文字目 で不一致

無駄

無駄

ａ ｂ ｃ ａ ｂ ａ ｂ ａ ｂ ａ ｂ ｃ ａ ｂ

ａ ｂ ｃ ａ ｂ

ａ ｂ ｃ ａ ｂ ｂ ａ ｂ

ａ ｂ ａ ｂ

ａ ｂ ａ ｂ

ａ ｂ ａ ｂ

ａ ｂ ａ ｂ ｘ ｂ

無駄 ２文字目 で不一致

無駄

無駄 パターンの比較を末尾から行うということを除けば、

ＫＭＰアルゴリズムと考え方は同じ。

16

○

×

△

○

○

×

×

図５.１.１２ 場合1

図５.１.１３ 場合２

図５.１.１４ 場合３ 文字の並びが同じ

部分がある

（ただし、○≠△）

少しずらせる。

文字の並びが同じ 部分が少しある かなりずらせる。

文字の並びが同じ 部分がない

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;

for(j = 0; j < pattern.length; 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);

} }

} ｂｍｍａｔｃｈメソッドなどは次のページで…

ｓｋｉｐを求める

ｎｅｘｔを求める

教科書のｍ‐ｊに 相当するＪａｖａ表現

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);

}