シリアルの2パターンマッチング方式(BF/KMPアルゴリズム)
6859 ワード
前言
シリアルは、文字列とも呼ばれ、0文字以上の文字からなる有限シーケンスであり、シリアルは同様に順序記憶とチェーン記憶の2つの方法で記憶することができ、主シリアルの中で位置決めサブシリアル問題(モードマッチング)を探すことはシリアルの中で最も重要な操作の一つであり、異なるアルゴリズムの実現は異なる効率を持っている.今日は、学習列の2つのパターンマッチング方法を比較します.素朴なパターンマッチングアルゴリズム(Brute-Forceアルゴリズム、BFアルゴリズムと略称) KMPモードマッチングアルゴリズム 素朴なパターンマッチングアルゴリズム(BFアルゴリズム)
BFアルゴリズムはモードマッチングにおける従来のアルゴリズムであり,その考え方は以下の通りである.第1ラウンド:サブストリングの最初の文字とメインストリングの最初の文字を比較 が等しい場合、主列と子列の2番目の文字 を比較し続ける.等しくなければ、第2ラウンド比較 を行う.
第2ラウンド:サブストリングの最初の文字とメインストリングの2番目の文字を比較...... 第Nラウンド: がすべて一致するまで順次比較する.
図の説明:
第1ラウンド:
第2ラウンド:
...... 原理が一致し、中間ステップを省略
第5ラウンド:
第6ラウンド:
コード実装:
文字と図例の説明を見て、私たちはこのようなアルゴリズムを実現します.
上記の手順を簡単にまとめると、
主列の各文字はサブ列の先頭に一致し、一致に成功するとサブ列と主列の次の文字が一致するかどうかを比較し、一致に失敗するとサブ列と主列の次の文字を比較し、明らかに2つのポインタを使用して主列とサブ列のある文字をそれぞれ指すことができ、このようなアルゴリズムを実現することができる.
マッチングに成功し、サブストリングがプライマリストリングに最初に現れた位置を返し、マッチングに失敗した場合は-1を返し、サブストリングは空のストリングで0を返します.
注意:コードはアルゴリズムの構想を体現するためだけで、具体的な定義は与えられていません
このアルゴリズムは簡単で分かりやすいが、大きな欠点がある.それは、何度も遡る必要があり、効率が低下し、主列が00000000001の子列が00001であれば、各輪が子列の最後の文字を比較してマッチングに失敗することを意味し、より良い方法はないだろうか.次のKMPモードマッチングアルゴリズムはこの問題をよく解決した.
KMPモードマッチングアルゴリズム
わずかなデータの演算を行うだけで、BFアルゴリズムもまあまあだと思っているかもしれませんが、少なくとも簡単に書けます.結局走ることができるのは良いプログラムですが、データ量が大きくなると、「無駄」が本当にスピードを遅くしていることに気づきます.
KMPモードマッチングアルゴリズムはD.E.Knuth,J.H.Morris,V.R.Prattの3人の先輩が提案したもので、素朴なモードマッチングアルゴリズムの改良であり、核心はマッチング失敗後の情報を利用して、できるだけサブプライマリ列のマッチング回数を減らすことであり、その体現はメイン列のポインタがずっと後ろに移動し、サブ列のポインタが遡及することである.
図の説明:
以下に,素朴モードマッチングアルゴリズムの過程を示すが,KMPアルゴリズムを用いると,どのステップが省略できるかを見る.
①の最初の5つの要素は、互いに一致していて、6番目の要素が一致しないことを知っていて、BFアルゴリズムによると、②③操作を直接行いますが、サブストリングの最初の3つの要素a b cは同じではありませんが、①では主ストリングに一致していることがわかります.したがって、サブストリングは、主ストリングの2番目の3番目の要素とそれぞれ一致するのは必ず一致しないので、図中の②③は省略することができる
①中子列における第1の第2の元素abと第4の第5の元素abは同一であり、第4の第5の元素abはすでに主列における第4の第5の元素と整合に成功している.
このように考えれば、上記の例は①と⑥を実行するだけでよい
next配列値の導出
(一)主列ポインタが遡及する必要があるか
上記の2つの過程を観察すると、BFアルゴリズム-①②③④⑤⑥KMPアルゴリズム-①⑥は、2つのポインタ、iとjが、それぞれ主列と子列の位置を指していると仮定すると、上図から分かるように、主列ポインタ、すなわちiの値が①の状態では、ポインタは6の位置を指し、②③④ではそれぞれ2345を指し、⑥では6の位置を指す
これは,単純モードマッチングアルゴリズムでは,主列のi値が遡及し続けるが,KMPモードマッチングアルゴリズムではこのような不要な遡及を省略するため実行回数が減少することを示している.
(二)サブストリングポインタ最適化まとめ
プライマリ・シリアル・ポインタが遡及しない以上、最適化できるのはサブシリアル・ポインタです.一般的には、2つの例を挙げます.サブストリングがabcdef、メインストリングがabcdexabcdefである場合、第1ラウンドが第6文字fとxにマッチングした場合、マッチングに失敗する.この場合、素朴なモードでマッチングすると、サブストリングのヘッダ要素aをメインストリングのbcdeとそれぞれ比較する必要があるが、サブストリングf要素の前の要素には同じ要素がなく、メインストリングとマッチングする.したがって、aは、主列の2-5番の要素であるbcdeと一致することは不可能であり、これらの部分はすべて省略することができ、aと主列のxを直接 に一致させることができる.サブストリングがabcabxであれば、メインストリングがabcababcaxであり、第1ラウンドでは、最初の5つの要素のサブプライマリストリングがそれぞれ一致し、第6の要素の位置が間違っており、素朴なモードでマッチングする必要があります.サブストリングの最初の要素aを持って、メインストリングのaの後ろの要素と順番にマッチングする必要がありますが、サブストリングの前の3つの文字abcは等しくありません.私たちの第1の状況の経験によると、これらのステップを直接スキップして、すべてのサブストリングaを主ストリングの4番目の要素aと直接比較すればいいのですが、サブストリングの中でエラーの位置xの前のストリングabcabの接頭辞と接尾辞はabで、第1ラウンドの時、すでにマッチングに成功した以上、それはサブストリングの第1の第2の要素abは必ず主ストリングの第4の第5の要素abと等しいので、このステップは省略してもよいし、サブストリング接頭辞abの後ろのcを直接aで比較することができる.これは、上述の図の例の詳細な考え方 である.
まとめ:したがって,サブストリングポインタの値は,サブストリングの前接尾辞要素の類似度に依存する法則を導いた.
特定のコードに適用するには、サブストリングの位置が変化するj値をnext配列として定義し、サブストリングの長さと同じ長さにすることができます.
$$next[j]=begin{cases}-1&&j=0max&{k|00&&その他の場合end{cases}$$の場合1:j=0の場合、next[j]=-1は、サブストリングポインタが下に0と表記された要素を指す場合にマッチングに失敗し、サブストリングが遡及できないことを示す(jは-1を付与できない)、このときメインストリングポインタを1桁後ろに移動し、サブストリングは、次の比較 を行う.の場合2:一致したサブ列には、同じプレフィックス列T 0 T 1が存在する...Tk-1と接尾辞列Tj-k Tj-k+1...Tj-1では、サブストリングポインタはnext[j]=kの位置に遡り、次の比較を行う.例えば、サブストリングabcabcは同じ接頭辞と接尾辞abを有するので、サブストリングポインタはcの位置 に遡る.の場合3:一致するサブストリングにおいて、等しい接頭辞と接尾辞が存在しなければ、メインストリングポインタは動かず、サブストリングポインタはj=0の位置に遡り、次の比較 を行う.
例:主列S=“abc 520 abc 520 abcd”,サブ列T=“abc 520 abcd”,KMPアルゴリズムによるマッチングプロセス
サブストリングnext配列
j
0 1 2 3 4 5 6 7 8 9
サブストリング
a b c 5 2 0 a b c d
next[j]
-1 0 0 0 0 0 0 1 2 3
ポインタi=9,j=9の場合,マッチングに失敗し,next[9]=3であるため,サブストリングポインタは下付きj=3の位置,すなわち要素5の位置に遡り,2回目の比較を行い,ちょうど全てマッチングに成功することがわかる.
(三)next配列アルゴリズムの実現を求める
KMPアルゴリズムコード実装
next配列のマットがあればKMPアルゴリズムを実現できます
サブストリングがプライマリストリングで最初に発生した位置に一致し、失敗した場合は-1を返し、サブストリングは空白ストリングで0を返します.
KMPモードマッチングアルゴリズムの改良
KMPアルゴリズムの改良を考慮せざるを得ない特殊な状況が現れた.
それは、主列S="aaabcde"サブ列T="aaaaaaax"が主列ポインタで動かず、移動サブ列ポインタでこれらの値を比較するなど、サブ列に複数の連続的に繰り返される要素であり、実際には、サブ列の最初の5つの要素が同じaであるため、これらの繰り返しのステップを省略することができる.
この改良の核心は,サブストリングにおけるt[i]とt[j]が等しいか否かの判断を増やし,等しいとnextVal[j]の値をnextVal[i]に直接与えることにある.
まとめ
BFアルゴリズムでは、主列と子列が一致しない場合、主列と子列のポインタを遡及する必要があるため、このアルゴリズムは時間的複雑度がO(nm)より高く、空間的複雑度がO(1)注:時間的複雑度がO(nm)であるが、一般的な応用ではO(n+m)に近いため使用されている
KMPアルゴリズムは,サブストリングの構造類似性を利用してnext配列を設計し,その上で主ストリングの遡及しない効果を達成し,比較回数を大幅に減少させたが,それに対応して記憶空間を犠牲にし,KMPアルゴリズムの時間複雑度はO(n+m)空間複雑度はO(n)であった.
終了:
もし文章の中で何か不足があるならば、あるいは间违った地方、みんなの伝言を歓迎して考えを分かち合って、友达の支持に感谢します!
もしあなたを助けることができたら、私に注目してください.微信の文章の読み方が好きなら、私の公衆番号に注目してください.
ここにいる私达は见知らないで、すべて自分の梦のために努力しています❤
オリジナル開発技術の文章をプッシュすることを堅持する公衆番号:理想の二旬は止まらない
シリアルは、文字列とも呼ばれ、0文字以上の文字からなる有限シーケンスであり、シリアルは同様に順序記憶とチェーン記憶の2つの方法で記憶することができ、主シリアルの中で位置決めサブシリアル問題(モードマッチング)を探すことはシリアルの中で最も重要な操作の一つであり、異なるアルゴリズムの実現は異なる効率を持っている.今日は、学習列の2つのパターンマッチング方法を比較します.
BFアルゴリズムはモードマッチングにおける従来のアルゴリズムであり,その考え方は以下の通りである.
図の説明:
第1ラウンド:
第2ラウンド:
...... 原理が一致し、中間ステップを省略
第5ラウンド:
第6ラウンド:
コード実装:
文字と図例の説明を見て、私たちはこのようなアルゴリズムを実現します.
上記の手順を簡単にまとめると、
主列の各文字はサブ列の先頭に一致し、一致に成功するとサブ列と主列の次の文字が一致するかどうかを比較し、一致に失敗するとサブ列と主列の次の文字を比較し、明らかに2つのポインタを使用して主列とサブ列のある文字をそれぞれ指すことができ、このようなアルゴリズムを実現することができる.
マッチングに成功し、サブストリングがプライマリストリングに最初に現れた位置を返し、マッチングに失敗した場合は-1を返し、サブストリングは空のストリングで0を返します.
int String::bfFind(const String &s, int pos) const {
// ，i ，j
int i, j;
// ， ，curLenght
if (curLength < s.curLenght)
return -1;
while (i < curLength && j < s.curLength) {
// ，
if (data[i] == s.data[j])
i+, j++;
else { //
i = i -j + 1; //
j = 0; //
}
//
if (j >= s.curLength)
return (i - s.curLength);
else return -1;
}
}注意:コードはアルゴリズムの構想を体現するためだけで、具体的な定義は与えられていません
このアルゴリズムは簡単で分かりやすいが、大きな欠点がある.それは、何度も遡る必要があり、効率が低下し、主列が00000000001の子列が00001であれば、各輪が子列の最後の文字を比較してマッチングに失敗することを意味し、より良い方法はないだろうか.次のKMPモードマッチングアルゴリズムはこの問題をよく解決した.
KMPモードマッチングアルゴリズム
わずかなデータの演算を行うだけで、BFアルゴリズムもまあまあだと思っているかもしれませんが、少なくとも簡単に書けます.結局走ることができるのは良いプログラムですが、データ量が大きくなると、「無駄」が本当にスピードを遅くしていることに気づきます.
KMPモードマッチングアルゴリズムはD.E.Knuth,J.H.Morris,V.R.Prattの3人の先輩が提案したもので、素朴なモードマッチングアルゴリズムの改良であり、核心はマッチング失敗後の情報を利用して、できるだけサブプライマリ列のマッチング回数を減らすことであり、その体現はメイン列のポインタがずっと後ろに移動し、サブ列のポインタが遡及することである.
図の説明:
以下に,素朴モードマッチングアルゴリズムの過程を示すが,KMPアルゴリズムを用いると,どのステップが省略できるかを見る.
①の最初の5つの要素は、互いに一致していて、6番目の要素が一致しないことを知っていて、BFアルゴリズムによると、②③操作を直接行いますが、サブストリングの最初の3つの要素a b cは同じではありませんが、①では主ストリングに一致していることがわかります.したがって、サブストリングは、主ストリングの2番目の3番目の要素とそれぞれ一致するのは必ず一致しないので、図中の②③は省略することができる
①中子列における第1の第2の元素abと第4の第5の元素abは同一であり、第4の第5の元素abはすでに主列における第4の第5の元素と整合に成功している.
このように考えれば、上記の例は①と⑥を実行するだけでよい
next配列値の導出
(一)主列ポインタが遡及する必要があるか
上記の2つの過程を観察すると、BFアルゴリズム-①②③④⑤⑥KMPアルゴリズム-①⑥は、2つのポインタ、iとjが、それぞれ主列と子列の位置を指していると仮定すると、上図から分かるように、主列ポインタ、すなわちiの値が①の状態では、ポインタは6の位置を指し、②③④ではそれぞれ2345を指し、⑥では6の位置を指す
これは,単純モードマッチングアルゴリズムでは,主列のi値が遡及し続けるが,KMPモードマッチングアルゴリズムではこのような不要な遡及を省略するため実行回数が減少することを示している.
(二)サブストリングポインタ最適化まとめ
プライマリ・シリアル・ポインタが遡及しない以上、最適化できるのはサブシリアル・ポインタです.一般的には、2つの例を挙げます.
まとめ:したがって,サブストリングポインタの値は,サブストリングの前接尾辞要素の類似度に依存する法則を導いた.
特定のコードに適用するには、サブストリングの位置が変化するj値をnext配列として定義し、サブストリングの長さと同じ長さにすることができます.
$$next[j]=begin{cases}-1&&j=0max&{k|00&&その他の場合end{cases}$$
例:主列S=“abc 520 abc 520 abcd”,サブ列T=“abc 520 abcd”,KMPアルゴリズムによるマッチングプロセス
サブストリングnext配列
j
0 1 2 3 4 5 6 7 8 9
サブストリング
a b c 5 2 0 a b c d
next[j]
-1 0 0 0 0 0 0 1 2 3
ポインタi=9,j=9の場合,マッチングに失敗し,next[9]=3であるため,サブストリングポインタは下付きj=3の位置,すなわち要素5の位置に遡り,2回目の比較を行い,ちょうど全てマッチングに成功することがわかる.
(三)next配列アルゴリズムの実現を求める
void Stirng::getNext(const String &t, int *next) {
int i = 0, j = -1;
next[0] = -1;
while (i < t.curLength - 1) {
if ((j == -1) || t[i] == t[j]) {
++i, ++j;
next[i] = j;
}else{
j = next[j];
}
}
}KMPアルゴリズムコード実装
next配列のマットがあればKMPアルゴリズムを実現できます
サブストリングがプライマリストリングで最初に発生した位置に一致し、失敗した場合は-1を返し、サブストリングは空白ストリングで0を返します.
int String::kmpFind(const String &t, int pos) {
// 0
if (t,curLength == 0) return 0;
// ，
if(t.curLength < t.curLength) return -1;
// i， j
int i = 0, j = 0;
int *next = new int[t.curLrngth];
getNext(t,next);
while (i < curLength && j < t,curLength) {
if (j == -1 || data[i] == t.data[j]) // 12
i++, j++;
else // 3
j = next[j];
}
delete []next;
if (j > t.curLength)
return (i - t.curLength)
else
return -1;
}KMPモードマッチングアルゴリズムの改良
KMPアルゴリズムの改良を考慮せざるを得ない特殊な状況が現れた.
それは、主列S="aaabcde"サブ列T="aaaaaaax"が主列ポインタで動かず、移動サブ列ポインタでこれらの値を比較するなど、サブ列に複数の連続的に繰り返される要素であり、実際には、サブ列の最初の5つの要素が同じaであるため、これらの繰り返しのステップを省略することができる.
void String::getNextVal(const String &t, int *nextVal) {
int i = 0, j = -1;
nextVal[0] = -1;
while (i < t.curLength -1) {
if ((k == -1) || (t[i] == t[j])) {
++i, ++j;
if (t[i] != t[j])
nextVal[i] = j;
else
nextVal[i] = nextVal[j];
}
else
j = nextVal[j];
}
}この改良の核心は,サブストリングにおけるt[i]とt[j]が等しいか否かの判断を増やし,等しいとnextVal[j]の値をnextVal[i]に直接与えることにある.
まとめ
BFアルゴリズムでは、主列と子列が一致しない場合、主列と子列のポインタを遡及する必要があるため、このアルゴリズムは時間的複雑度がO(nm)より高く、空間的複雑度がO(1)注:時間的複雑度がO(nm)であるが、一般的な応用ではO(n+m)に近いため使用されている
KMPアルゴリズムは,サブストリングの構造類似性を利用してnext配列を設計し,その上で主ストリングの遡及しない効果を達成し,比較回数を大幅に減少させたが,それに対応して記憶空間を犠牲にし,KMPアルゴリズムの時間複雑度はO(n+m)空間複雑度はO(n)であった.
終了:
もし文章の中で何か不足があるならば、あるいは间违った地方、みんなの伝言を歓迎して考えを分かち合って、友达の支持に感谢します!
もしあなたを助けることができたら、私に注目してください.微信の文章の読み方が好きなら、私の公衆番号に注目してください.
ここにいる私达は见知らないで、すべて自分の梦のために努力しています❤
オリジナル開発技術の文章をプッシュすることを堅持する公衆番号:理想の二旬は止まらない