Morris-Pratt algorithm とは？
状態:-
閲覧数:970
投稿日:2018-03-11
更新日:2018-03-23
表記
日本語表記
・Morris-Pratt アルゴリズム
省略表記
・MP法
・MP
「Brute force algorithm」を改善したアルゴリズム
ウィンドウをシフトする際、シフトの長さを改善している
・「パターンと一致するテキストの一部」を記憶することが可能
・パターン文字列に対して「border」と呼ばれる値を計算することにより、シフト量を定める
・これにより、「パターンの文字」と「テキストの文字」との比較が節約され、結果として検索の速度が向上する
具体例をプログラミングせずに日本語で考えていく過程
前提
検索文字列パターン
なるべくなる
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]
日本語で考える
文字列
・ 'aabaabaaa'
求める結果
・配列(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]
インデックス0
・-1
・配列(1) [-1]
| インデックス | 文字列 | border | 数 |
|---|---|---|---|
| 0 | 存在しない | 特別なケース | 文字内容に関わらず常に固定値-1 |
・比較しようがないため0
・配列(2) [-1,0]
| インデックス | 文字列 | border | 数 |
|---|---|---|---|
| 0 | 存在しない | 特別なケース | 文字内容に関わらず常に固定値-1 |
| 1 | 'a' | '' | 0 |
・borderはa … 数1
・配列(3) [-1,0,1]
| インデックス | 文字列 | border | 数 |
|---|---|---|---|
| 0 | 存在しない | 特別なケース | 文字内容に関わらず常に固定値-1 |
| 1 | 'a' | '' | 0 |
| 2 | 'aa' | 'a' | 1 |
・borderはなし … 数0
・配列(4) [-1,0,1,0]
| インデックス | 文字列 | border | 数 |
|---|---|---|---|
| 0 | 存在しない | 特別なケース | 文字内容に関わらず常に固定値-1 |
| 1 | 'a' | '' | 0 |
| 2 | 'aa' | 'a' | 1 |
| 3 | 'aab' | '' | 0 |
・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 |
・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 |
・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 |
・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 |
・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 |
・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 |
|---|
・+1して、j0
・A[1]=0
i1,j0,A[-1,0]
| a | b | b | a | b | b | a |
|---|
・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 |
|---|
・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 |
|---|
・+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 |
|---|
・+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 |
|---|
・+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 |
|---|
・+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
例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 |
|---|
・+1して、j=0
・A[1]=0
i1,j0,A[-1,0]
| a | a | b | a | a | b | a | a | a |
|---|
・+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 |
|---|
・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 |
|---|
・+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 |
|---|
・+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 |
|---|
・+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 |
|---|
・+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 |
|---|
・+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 |
|---|
・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
検索文字列パターン
・ここでは変数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]
| な | る | べ | く | な | る |
|---|
・+1して、j=0
・A[1]=0
i1,j0,A[-1,0]
| な | る | べ | く | な | る |
|---|
・j >= 0 を満たさないため、while文のループ終了
・+1して、j=0
・A[2]=0
※「な」よリ前と「る」よリ前を比較して、「な」と「る」が一致していないので「0」
i2,j0,A[-1,0,0]
| な | る | べ | く | な | る |
|---|
・j >= 0 を満たさないため、while文のループ終了
・+1して、j=0
・A[3]=0
※「な」よリ前と「べ」よリ前を比較して、「な」と「べ」が一致していないので「0」
i3,j0,A[-1,0,0,0]
| な | る | べ | く | な | る |
|---|
・j >= 0 を満たさないため、while文のループ終了
・+1して、j=0
・A[4]=0
※「な」よリ前と「く」よリ前を比較して、「な」と「く」が一致していないので「0」
i4,j0,A[-1,0,0,0,0]
| な | る | べ | く | な | る |
|---|
・+1して、j=1
・A[5]=1
※「な」よリ前と「な」よリ前を比較して、「な」と「な」が一致しているので「1」
i5,j1,A[-1,0,0,0,0,1]
| な | る | べ | く | な | る |
|---|
・+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法