KMPアルゴリズム小結
KMPアルゴリズム小結
Posted on
2011/06/14
by
huangchao
主にここを見て、とてもいい感じで、まとめてみました.
まず、検索する列をS、長さをn、一致する列をM、長さをmと宣言する.
暴力のアルゴリズムを先に考えて、暴力のアルゴリズムはSのすべての文字を遍歴して、それからこの文字からM列とマッチングします.時間的複雑度はO(nm)である.
どのようにして最適化しますか?ある位置(sとする)からM列とマッチングすると仮定し,マッチングが成功しなければ暴力アルゴリズムはこの位置の次の位置(s+1)からマッチングし,直感的にはマッチングした文字列が後ろに「スライド」した.
図1
Mが後ろに移動する距離を最大化する方法を考えてもらえますか?最良の場合、Mと一致するSのm文字とMの文字が等しくなければ、mビットを右に移動することができる.最悪の場合、例えば上図では、1人しか移動できません.
KMPはここで文章を作って、M列を後ろに「スライド」する距離を最大化します.
図2
上の図を考慮すると、Mのグレー部分はSのグレー部分と一致しているが、グレー部分の後ろの文字が一致していない場合、Mは後ろにスライドし、図の位置がSと再び一致するまで後ろにスライドすると仮定すると、ここから以下の結論を得ることができる.
このように、Sをしばらく考慮せずにMのみを見ると、一致したMの文字列(すなわち、図中のMの灰色部分)がsubMであると仮定すると、subMには【等しい】の【接頭辞】と【接尾辞】がある.また,Mは不整合に遭遇したときにsubMの接頭辞とsubMの接尾辞を重ね合わせる場所に直接スライドすることができる.Mが後ろにスライドするとき、最初のsubMの接頭辞と接尾辞が重なるのは、このときの等しいsubMの接頭辞と接尾辞の長さが最大であることを意味する.
私たちの任務はsubMの最長の接頭辞と接尾辞が等しい列を探すことです.
それを知って、KMPの真の意味も遠くない.次に、この上の図と組み合わせて、KMPアルゴリズムの全体的な流れをシミュレートします.
上記の手順から分かるように、KMPの鍵は、S列の文字とM列の文字が一致しない場合、S列がM列のどの文字と一致し続けるかを知ることである.これがステータスマシンモデルを用いるKMPアルゴリズムを解釈する際のステータス遷移である.
KMPは、Sの文字とMの文字が一致しない場合、SがMの文字と再一致する座標値を保存するnext配列を定義します.図2に示す例のように、S中のX位置とMが一致しない場合、SはM中のAセグメントの後ろの文字と比較し、図から見るとMが後ろにスライドしている.
言い換えれば、next[i]は常にM[i]が一致しない場合にM[next[i]]から一致することを保存しており、このM[next[i]]は一致する可能性がありますが、まだ一致していない場合は?では、M[next[next[i]]で一致する可能性があります.ここでは、iの前の文字とnext[i]の前の文字が同じ、すなわちM[0...i-1]の等しい接頭辞と接尾辞とが同時に隠されている.
ここでnext[0]、next[1]...next[i]を考慮すると、以下のように図示される.
j=next[i]とし、灰色の部分はこの2つの文字が等しいことを示し、i位置の文字とj位置の文字が等しい場合、next[i+1]=j+1とする.前のグレー部分とj位置の文字からなる文字列と、後のグレーのi接続によって形成される文字列は等しいからである.これは、next配列の定義です.等しくない場合は、iからiを含む前の文字列が0から始まる文字列と等しいことを見つけ、等しい接頭辞と接尾辞を形成します.幸いなことに、next[next[i]]の値は、next[i]の前の文字列にも最も長い共通接頭辞と接尾辞があるため、この共通の接頭辞は現在のiと前に形成された文字列と等しい可能性があり、このようにずっと前に探していて、見つからない場合は、i位置の文字が来る前に現れたことがないことを示しています.
このようにして求めたnext配列は、実は下付き文字1から始まる.下付き文字0の前は空欄であり、下付き文字1はM列の0番目の文字に対応しているからだ.私たちはnext[0]=-1を設定して、ただの標識で、特別な意味はありません.
前述したように、next配列を初期化するコードを簡単に書くことができる
1: void kmpGetNext() 2: { 3: int i=0, j=-1; 4: b[i]=j; 5: while (i<m) 6: { 7: while (j>=0 && p[i]!=p[j]) j=b[j]; 8: i++; j++; 9: b[i]=j; 10: } 11: }next配列の値が分かれば、S列とのマッチングは比較的簡単です.不一致に遭遇したときにnext配列を検索すれば、現在の文字と一致する文字が見つかるまで検索できます.見つからなかったらどうする?見つからない場合は-1、つまり彼と一致する文字がない場合は、この文字をスキップして、次の文字から直接一致すればいいです.
コードは次のとおりです.
1: void kmpSearch() 2: { 3: int i=0, j=0; 4: while (i<n) 5: { 6: while (j>=0 && t[i]!=p[j]) j=b[j]; 7: i++; j++; 8: if (j==m) 9: { 10: report(i-j); 11: j=b[j]; 12: } 13: } 14: }上のコードを見て、2層のループ、このコードは線形ではないようですが、実はそうではありません.外層がn回循環しているのは問題ありませんが、肝心なのは中のwhile循環です.この循環の回数はいくらなのかはよく分かりませんが、jの値の変化だけを考えると、7行目のjが1増加し、6行目のjが1減少し、1減少する可能性があり、2減少する可能性があります.もっと少ないかもしれませんが、j<0で循環が終了します.つまり、jはn回増加する機会があります.何度減るチャンスがありますか?あるいはjに最大何回減らしますか?jが最も減少した回数が最も多かったのは,毎回1減少し,これが最も多かったのはn回減少し,すなわち6行目のループは最大でn回実行された.各サイクルに割り振ると、実行回数はO(1)であるため、kmpSearchの時間的複雑度は依然として線形のO(n)であり、同様にkmpGetNextの時間的複雑度はO(m)である.