Morris-Pratt algorithm

アルゴリズム探索アルゴリズム

Morris-Pratt algorithm とは?

 状態:-  閲覧数:534  投稿日:2018-03-11  更新日:2018-03-23  

表記


日本語表記
・Morris-Pratt アルゴリズム

省略表記
・MP法
・MP

「Brute force algorithm」を改善したアルゴリズム


ウィンドウをシフトする際、シフトの長さを改善している
・「パターンと一致するテキストの一部」を記憶することが可能
・パターン文字列に対して「border」と呼ばれる値を計算することにより、シフト量を定める
・これにより、「パターンの文字」と「テキストの文字」との比較が節約され、結果として検索の速度が向上する

具体例をプログラミングせずに日本語で考えていく過程

 閲覧数:231 投稿日:2018-03-14 更新日:2018-07-13 

前提


検索文字列パターン
なるべくなる

border
・「単語の2文字目で不一致となった場合のバックトラックする文字数」で構成された配列
※配列名は任意だが、慣用的にborderを使用することが多い

比較再開テーブルを作成

インデックス 0 1 2 3 4 5
検索文字列パターン

比較再開テーブル0


border[0]を-1 とする
・パターン最初の部分での不一致は特別なケース(バックトラッキングの可能性はない)ので、 border[0] = -1を設定
※文字内容に関わらず常に固定値-1
インデックス 0 1 2 3 4 5
検索文字列パターン
border -1 . . . . .

比較再開テーブル1


border[1]を0 とする
・単語の2文字目で不一致となった場合のバックトラックする文字数であるが、(仮に一致した状態であったとしても)1文字しか一致していない状態ではバックトラックできないため
※文字内容に関わらず常に固定値0

計算式に無理やり当てはめてみる
・検索文字列パターン[0] から 検索文字列パターン[1-1] までの文字列について、検索文字列パターン[1-1] で終わる文字列と 検索文字列パターン[0] から始まる文字列が一致するかどうかを調べる
・「な」から「な」までの文字列について、「な」 と 「な」 が一致するかどうかを調べる
インデックス 0 1 2 3 4 5
検索文字列パターン
border -1 0 . . . .

比較再開テーブル2


border[2]を0 とする
・検索文字列パターン[0] から 検索文字列パターン[2-1] までの文字列について、検索文字列パターン[2-1] で終わる文字列と 検索文字列パターン[0] から始まる文字列が一致するかどうかを調べる
・「な」から「る」までの文字列について、「る」 と 「な」 が一致するかどうかを調べる
・一致していないので「0」
インデックス 0 1 2 3 4 5
検索文字列パターン
border -1 0 0 . . .


例1.'aabaabaaa' → 配列(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]

 閲覧数:225 投稿日:2018-05-09 更新日:2018-09-13 

日本語で考える


文字列
・ 'aabaabaaa'

求める結果
・配列(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]

インデックス0
・-1
・配列(1) [-1]
インデックス 文字列 border
0 存在しない 特別なケース 文字内容に関わらず常に固定値-1
インデックス1まで … a
・比較しようがないため0
・配列(2) [-1,0]
インデックス 文字列 border
0 存在しない 特別なケース 文字内容に関わらず常に固定値-1
1 'a' '' 0
インデックス2まで … aa
・borderはa … 数1
・配列(3) [-1,0,1]
インデックス 文字列 border
0 存在しない 特別なケース 文字内容に関わらず常に固定値-1
1 'a' '' 0
2 'aa' 'a' 1
インデックス3まで … aab
・borderはなし … 数0
・配列(4) [-1,0,1,0]
インデックス 文字列 border
0 存在しない 特別なケース 文字内容に関わらず常に固定値-1
1 'a' '' 0
2 'aa' 'a' 1
3 'aab' '' 0
インデックス4まで … aaba
・borderはa … 数1
・配列(5) [-1,0,1,0,1]
インデックス 文字列 border
0 存在しない 特別なケース 文字内容に関わらず常に固定値-1
1 'a' '' 0
2 'aa' 'a' 1
3 'aab' '' 0
4 'aaba' 'a' 1
インデックス5まで … aabaa
・borderはaa … 数2
・配列(6) [-1,0,1,0,1,2]
インデックス 文字列 border
0 存在しない 特別なケース 文字内容に関わらず常に固定値-1
1 'a' '' 0
2 'aa' 'a' 1
3 'aab' '' 0
4 'aaba' 'a' 1
5 'aabaa' 'aa' 2
インデックス6まで … aabaab
・aabとaabが一致しているため3
・配列(7) [-1,0,1,0,1,2,3]
インデックス 文字列 border
0 存在しない 特別なケース 文字内容に関わらず常に固定値-1
1 'a' '' 0
2 'aa' 'a' 1
3 'aab' '' 0
4 'aaba' 'a' 1
5 'aabaa' 'aa' 2
6 'aabaab' 'aab' 3
インデックス7まで … aabaaba
・aabaとaabaが一致しているため4
・配列(8) [-1,0,1,0,1,2,3,4]
インデックス 文字列 border
0 存在しない 特別なケース 文字内容に関わらず常に固定値-1
1 'a' '' 0
2 'aa' 'a' 1
3 'aab' '' 0
4 'aaba' 'a' 1
5 'aabaa' 'aa' 2
6 'aabaab' 'aab' 3
7 'aabaaba' 'aaba' 4
インデックス8まで … aabaabaa
・aabaaとaabaaが一致しているため5
・配列(9) [-1,0,1,0,1,2,3,4,5]
インデックス 文字列 border
0 存在しない 特別なケース 文字内容に関わらず常に固定値-1
1 'a' '' 0
2 'aa' 'a' 1
3 'aab' '' 0
4 'aaba' 'a' 1
5 'aabaa' 'aa' 2
6 'aabaab' 'aab' 3
7 'aabaaba' 'aaba' 4
8 'aabaabaa' 'aabaa' 5
インデックス9まで … aabaabaaa
・aaとaaが一致しているため2
・配列(10) [-1,0,1,0,1,2,3,4,5,2]
インデックス 文字列 border
0 存在しない 特別なケース 文字内容に関わらず常に固定値-1
1 'a' '' 0
2 'aa' 'a' 1
3 'aab' '' 0
4 'aaba' 'a' 1
5 'aabaa' 'aa' 2
6 'aabaab' 'aab' 3
7 'aabaaba' 'aaba' 4
8 'aabaabaa' 'aabaa' 5
9 'aabaabaaa' 'aa' 2

コードステップ


ECMASCript2015
const S = 'aabaabaaa';
const A = [];
A[0] = -1; //特別なケース。文字内容に関わらず常に固定値-1
let j = -1;
for (let i = 0; i < S.length; i++) {
 while (j >= 0 && S[i] != S[j]) j = A[j];
 j++;
 A[i+1] = j;
}
console.log(A); //(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]


JavaScript
var S = 'abbabba';
var A = [];
A[0] = -1; //特別なケース。文字内容に関わらず常に固定値-1
var j = -1;
for (var i = 0; i < S.length; i++) { // i < 7
 while (j >= 0 && S[i] != S[j]) j = A[j];
 j++;
 A[i+1] = j;
 console.log(i); //0 1 2 3 4 5 6
 console.log(j); //0 0 0 1 2 3 4
}
console.log(A); //(8) [-1, 0, 0, 0, 1, 2, 3, 4]


i0,j-1,A[-1]
a b b a b b a
・false(j >= 0 を満たさない)なので、while文に入らず通過
・+1して、j0
・A[1]=0

i1,j0,A[-1,0]
a b b a b b a
・true(b≠a)なので、A[0]よりj=-1
・false(j >= 0 を満たさない)なので、while文のループ終了
・+1して、j0
・A[2]=0
※「a」以前と「b」以前を比較して、「a」と「b」が一致していないので「0」

i2,j0,A[-1,0,0]
a b b a b b a
・true(b≠a)なので、A[0]よりj=-1
・false(j >= 0 を満たさない)なので、while文のループ終了
・+1して、j0
・A[3]=0
※「a」以前と「b」以前を比較して、「a」と「b」が一致していないので「0」

i3,j0,A[-1,0,0,0]
a b b a b b a
・false(a == a)なので、while文に入らず通過
・+1して、j1
・A[4]=1
※「a」以前と「a」以前を比較して、「a」と「a」が一致しているので「1」

i4,j1,A[-1,0,0,0,1]
a b b a b b a
・false(b == b)なので、while文に入らず通過
・+1して、j2
・A[5]=2
※「b」以前と「b」以前を比較して、「ab」と「ab」が一致しているので「2」

i5,j2,A[-1,0,0,0,1,2]
a b b a b b a
・false(b == b)なので、while文に入らず通過
・+1して、j3
・A[6]=3
※「b」以前と「b」以前を比較して、「abb」と「abb」が一致しているので「3」

i6,j3,A[-1,0,0,0,1,2,3]
a b b a b b a
・false(a == a)なので、while文に入らず通過
・+1して、j4
・A[7]=4
※「a」以前と「a」以前を比較して、「abba」と「abba」が一致しているので「4」

i7,j4,A[-1,0,0,0,1,2,3,4]
検索文字列パターン _ a b b a b b a
border -1 0 0 0 1 2 3 4
0 _ ji _ _ _ _ _ _
1 _ j i _ _ _ _ _
2 _ j _ i _ _ _ _
3 _ _ j _ i _ _ _
4 _ _ _ j _ i _ _
5 _ _ _ _ j _ i _
6 _ _ _ _ _ j _ i


例2

 閲覧数:205 投稿日:2018-06-12 更新日:2018-07-29 

例2


コード
var S = 'aabaabaaa';
var A = [];
A[0] = -1;
var j = -1;
for (var i = 0; i < S.length; i++) {
 console.log(j); //-1 0 1 0 1 2 3 4 5
 while (j >= 0 && S[i] != S[j]) j = A[j]; //trueの間はfalseになるまで繰り返す
 console.log(j); //-1 0 -1 0 1 2 3 4 1
 j++;
 A[i+1] = j;
 //console.log(i); //0 1 2 3 4 5 6 7 8
 //console.log(j); //0 1 0 1 2 3 4 5 2
}
console.log(A); //(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]


i0,j-1,A[-1]
a a b a a b a a a
・false(j >= 0 を満たさない)なので、while文に入らず通過
・+1して、j=0
・A[1]=0

i1,j0,A[-1,0]
a a b a a b a a a
・false(a == a)なので、while文に入らず通過
・+1して、j=1
・A[2]=1
※「a」よリ前と「a」よリ前を比較して、「a」と「a」が一致しているので「1」

i2,j1,A[-1,0,1]
a a b a a b a a a
・true(b≠a)なので、A[1]よりj=0
・s[2]!=s[0]はtrue(b≠a)なので、A[0]よりj=-1
・j >= 0 を満たさないため、while文のループ終了
・+1して、j=0
・A[3]=0
※「a」よリ前と「b」よリ前を比較して、「a」と「b」が一致していないので「0」

i3,j0,A[-1,0,1,0]
a a b a a b a a a
・false(a == a)なので、while文に入らず通過
・+1して、j1
・A[4]=1
※「a」よリ前と「a」よリ前を比較して、「a」と「a」が一致しているので「1」

i4,j1,A[-1,0,1,0,1]
a a b a a b a a a
・false(a == a)なので、while文に入らず通過
・+1して、j=2
・A[5]=2
※「a」よリ前と「a」よリ前を比較して、「aa」と「aa」が一致しているので「2」

i5,j2,A[-1,0,1,0,1,2]
a a b a a b a a a
・false(b == b)なので、while文に入らず通過
・+1して、j3
・A[6]=3
※「b」よリ前と「b」よリ前を比較して、「aab」と「aab」が一致しているので「3」

i6,j3,A[-1,0,1,0,1,2,3]
a a b a a b a a a
・false(a == a)なので、while文に入らず通過
・+1して、j=4
・A[7]=4
※「a」よリ前と「a」よリ前を比較して、「aaba」と「aaba」が一致しているので「4」

i7,j4,A[-1,0,1,0,1,2,3,4]
a a b a a b a a a
・false(a == a)なので、while文に入らず通過
・+1して、j=5
・A[8]=5
※「a」よリ前と「a」よリ前を比較して、「aabaa」と「aabaa」が一致しているので「5」

i8,j5,A[-1,0,1,0,1,2,3,4,5]
a a b a a b a a a
・true(a != b)なので、A[5]よりj=2
・s[8]!=s[2]はtrue(a≠b)なので、A[2]よりj=1
・s[8]!=s[1]はfalse(a==a)なので、while文のループ終了
・+1して、j=2
・A[9]=2

i9,j2,A[-1,0,1,0,1,2,3,4,5,2]
検索文字列パターン _ a a b a a b a a a
border -1 0 1 0 1 2 3 4 5 2
0 _ ji _ _ _ _ _ _ _ _
1 _ _ ji _ _ _ _ _ _ _
2 _ j _ i _ _ _ _ _ _
3 _ _ j _ i _ _ _ _ _
4 _ _ _ j _ i _ _ _ _
5 _ _ _ _ j _ i _ _ _
6 _ _ _ _ _ j _ i _ _
7 _ _ _ _ _ _ j _ i _
8 _ _ j _ _ _ _ _ _ i


例3

 閲覧数:197 投稿日:2018-07-06 更新日:2018-07-21 

検索文字列パターン


・ここでは変数Sとして定義
const S = 'なるべくなる';

border


「単語の2文字目で不一致となった場合のバックトラックする文字数」で構成された配列
・ここでは配列Aとして定義
const A = [];

コード


const S = 'なるべくなる';
const A = [];
A[0] = -1;
let j = -1;
for (let i = 0; i < S.length; i++) {
 while (j >= 0 && S[i] != S[j]) j = A[j];
 j++;
 A[i+1] = j;
}
console.log(A); //(7) [-1, 0, 0, 0, 0, 1, 2]


i0,j-1,A[-1]
・false(j >= 0 を満たさない)なので、while文に入らず通過
・+1して、j=0
・A[1]=0

i1,j0,A[-1,0]
・true(る≠な)なので、A[0]よりj=-1
・j >= 0 を満たさないため、while文のループ終了
・+1して、j=0
・A[2]=0
※「な」よリ前と「る」よリ前を比較して、「な」と「る」が一致していないので「0」

i2,j0,A[-1,0,0]
・true(べ≠な)なので、A[0]よりj=-1
・j >= 0 を満たさないため、while文のループ終了
・+1して、j=0
・A[3]=0
※「な」よリ前と「べ」よリ前を比較して、「な」と「べ」が一致していないので「0」

i3,j0,A[-1,0,0,0]
・true(く≠な)なので、A[0]よりj=-1
・j >= 0 を満たさないため、while文のループ終了
・+1して、j=0
・A[4]=0
※「な」よリ前と「く」よリ前を比較して、「な」と「く」が一致していないので「0」

i4,j0,A[-1,0,0,0,0]
・false(な == な)なので、while文に入らず通過
・+1して、j=1
・A[5]=1
※「な」よリ前と「な」よリ前を比較して、「な」と「な」が一致しているので「1」

i5,j1,A[-1,0,0,0,0,1]
・false(る == る)なので、while文に入らず通過
・+1して、j=2
・A[6]=2
※「る」よリ前と「る」よリ前を比較して、「なる」と「なる」が一致しているので「2」

i6,j2,A[-1,0,0,0,0,1,2]

Morris-Pratt algorithm
Crochemore-Perrin アルゴリズム
文字列の頭良い感じの線形アルゴリズムたち
https://www.cs.helsinki.fi/u/tpkarkka/teach/15-16/SPA/lecture04.pdf
https://www.cs.helsinki.fi/u/hahonen/irm07/lectures/irm07_8.pdf

・終了後 → KMP法


クヌース–モリス–プラット法

Knuth–Morris–Pratt algorithm border

コメント投稿(ログインが必要)



週間人気ページランキング / 6-24 → 6-30
順位 ページタイトル抜粋 アクセス数
1 Flash Video | コンテナフォーマット | プログラミング用語 306
2 curl | HTTPクライアント(ネットワーク) | プログラミング用語 286
3 ルーター | ネットワーク | プログラミング用語 281
3 ユースケース | 開発 | プログラミング用語 281
4 ベクトル | 数学 | プログラミング用語 236
5 デーモン | Linux | プログラミング用語 227
6 正規表現 | プログラミング | プログラミング用語 194
7 YouTube | API | プログラミング用語 171
8 チェックアウト | バージョン管理システム(開発) | プログラミング用語 117
9 分かち書き | 形態素解析 | プログラミング用語 63
10 Linux | プログラミング用語 57
11 リバースエンジニアリング | 開発 | プログラミング用語 54
12 ネットワークアドレス | ネットワーク | プログラミング用語 50
13 PowerShell | スクリプト | プログラミング用語 44
14 クローラ | 検索エンジン | プログラミング用語 31
14 可搬性 | プログラミング | プログラミング用語 31
15 Subversion | バージョン管理システム(開発) | プログラミング用語 27
16 アンチパターン | プログラミング | プログラミング用語 11
17 プログラミング用語 9
18 deflate | ネットワーク | プログラミング用語 8
2022/7/1 1:01 更新