KMP--アルゴリズム、分析と再帰実現
牛先を下ろす.
ええ、大学院受験の准备をしているので、ほとんどブログをしないで、再びKMPアルゴリズムに出会って、心血が潮に来て、だからドラムを打って、间违いなくて、私はXを装って、私のキリンの腕はとっくに喉が渇いて耐えられません.
KMPアルゴリズム
KMPアルゴリズムを見ている人は、KMPアルゴリズムが何を持ってきたのか、文字列パターンマッチングを実現する効率的なアルゴリズムを知っていると思いますが、他のパターンマッチングを持って行ってもいいはずです.アルゴリズムの考え方をもう一度繰り返します.
既に、対象列T[0...n-1]、パターン列P[0...m-1]があると仮定し、注:(T[i...j]はt i t i+1..t j t_{i}t_{i+1}...t_{j}ti ti+1...tj,$0ltilt n-1$)と理解し、Pも同様に理解する.一般性を失わず,T中のs番目(0≦s≦n−1 0le sle n−1 0≦s≦n−1)の位置からP中のj番目($1le jle m−1$)の位置マッチングに失敗した.このときT[s...s+j-1]=P[0...j-1]があり,素朴なアルゴリズムでは,次はt s+1 t_から{s+1}ts+1はPと比較を開始し,マッチングに成功するとT[s+1...s+m]=P[0...m−1]、すなわちT[s+1...s+j−1]=P[0...j−2]となる.総合、既存の条件: T[s…s+j-1] = P[0…j-1] → t s t s + 1 . . t s + j − 1 = p 0 p 1 . . p j − 1\to t_{s}t_{s+1}..t_{s+j-1} = p_{0}p_{1}..p_{j-1} →tsts+1..ts+j−1=p0p1..pj−1 T[s+1…s+j-1] = P[0…j-2] → t s + 1 t s + 2 . . t s + j − 1 = p 0 p 1 . . p j − 2\to t_{s+1}t_{s+2}..t_{s+j-1} = p_{0}p_{1}..p_{j-2} →ts+1ts+2..ts+j−1=p0p1..pj−2
連合1、2は得られ、p 0 p 1である.p j − 2 = p 1 . . p j − 1 p_{0}p_{1}..p_{j-2} = p_{1}..p_{j-1} p0p1..pj−2=p1..pj−1,すなわちP[0…j−2]=P[1…j−1]
以上の導出は,P[0...j−2]=P[1...j−1]が成立する場合にのみ,T[s+1...s+m]=P[0...m−1]が存在することを示している.P[0...j-2]$e$P[1...j-1]の場合、T[s+1...s+m]$e$P[0...m-1]は必然的に生じる.
したがって,Tがs+1からのパターンマッチングを行うのではなく,s+2から試み,式が成立しなければk回目までs+3を試み続け,初めて、こいつを认める*P[0..k]=P[j-k+1.j-1]**こいつを认める**P[0..k]=P[j-k+1..j-1]=P[j-k+1..j-1]こいつを认めるこのときP[j-k+1...j-1]を観察すると、
T[s+j-k+1…s+j-1]=P[j-k+1…j-1]=P[0…k]→to→T[s+j-k+1…s+j-1]=P[0…k]—式3
以前はj番目のマッチングに失敗し、上の3式の成立を確認していたので、私たちはとても楽しかったですp k+1 p_{k+1}pk+1とs s+j s_{s+j}ss+jが比較を開始しました.後の比較も上記の手順を繰り返します.比較したTは遡及しないため効率が高いことが分かる.次に、j番目のマッチングに失敗した後に返されるk値、すなわち、次にT[s+j]と比較するP[k]をNext(j)で表す.ここで、返されるk値は、P[0...k]=P[j-k+1...j-1]を満たす必要があることを明確にする.
次に,問題をk探索値に変換し,Next(j)=kを知っていると仮定し,現在Next(j+1)が要求される.Next(j)=kについて、kがP[j]とT[s+j]のマッチングに失敗したことを明確に知った後、次のT[s+j]とマッチングする位置については、P[k]とT[s+j]が等しいかどうかは分からないが、k値によっては、P[j-k...j-1]=P[0...k-1]=T[s+j-k...s+j-1]がある
ここで、j+1回目のマッチングに失敗したとすると、P[0...j]=T[s...s+j]→to→P[j-k...j]=T[s-k...s+j]となる.この場合,(1)P[k]=P[j]観察P[0...k-1]とP[j-k...j]に分けられ,既にP[j-k...j-1]=P[0...k-1]があり,P[k]=P[j]ならP[0...k]=P[j-k...j]があり,すなわち,j+1回目のマッチングに失敗した場合,次のT[s+j+1]と比較した位置に戻るべきであり,Next(j+1)=k+1である.
(2) P[k] != P[j]しかし、P[j-k...j-1]=P[0...k-1]があり、問題クラス比はP[k]とP[j]のマッチングに失敗した場合、P[0...h-1]=P[k-h...k-1]となるようにh=Next(k)を見つけ、P[h]とP[j]を比較し、等しい場合はh+1を返し、このときP[h+1]とT[s+j+1]をマッチングする必要がある.P[h]!=P[j]は、受信Next()のパラメータが0になるまでステップ(2)を繰り返し、戻り-1は失敗を表す.すなわち、P[0...j-1]の中にP[j]に等しいものは1つもない.このときs:=s+1となり、ターゲット列は一歩前進する.
次に、上記の解析手順に基づいて、再帰アルゴリズムによりj番目の位置マッチングに失敗した後に返すべきk値を算出する.
アルゴリズムは2つの形式で与えられ,1つ目は擬似コード,2つ目はC++コードである.
疑似コード:
C++コード:
まとめ
再帰アルゴリズムは効率が低く、毎回Next値を再計算しますが、KMPがどのように実現されているかをより直感的に理解し、時間+興味があれば再帰を非再帰に書き換え、配列で結果を保存します.もちろん、小さなテクニックでNext()を呼び出して、結果を一緒に保存することもできます.最初は、ちゃんとコントロールできると思っていました.最后に...少し助けてほしいです...殷人昆编集长の《データ构造C++版》も参考にしました.
ええ、大学院受験の准备をしているので、ほとんどブログをしないで、再びKMPアルゴリズムに出会って、心血が潮に来て、だからドラムを打って、间违いなくて、私はXを装って、私のキリンの腕はとっくに喉が渇いて耐えられません.
KMPアルゴリズム
KMPアルゴリズムを見ている人は、KMPアルゴリズムが何を持ってきたのか、文字列パターンマッチングを実現する効率的なアルゴリズムを知っていると思いますが、他のパターンマッチングを持って行ってもいいはずです.アルゴリズムの考え方をもう一度繰り返します.
既に、対象列T[0...n-1]、パターン列P[0...m-1]があると仮定し、注:(T[i...j]はt i t i+1..t j t_{i}t_{i+1}...t_{j}ti ti+1...tj,$0ltilt n-1$)と理解し、Pも同様に理解する.一般性を失わず,T中のs番目(0≦s≦n−1 0le sle n−1 0≦s≦n−1)の位置からP中のj番目($1le jle m−1$)の位置マッチングに失敗した.このときT[s...s+j-1]=P[0...j-1]があり,素朴なアルゴリズムでは,次はt s+1 t_から{s+1}ts+1はPと比較を開始し,マッチングに成功するとT[s+1...s+m]=P[0...m−1]、すなわちT[s+1...s+j−1]=P[0...j−2]となる.総合、既存の条件:
連合1、2は得られ、p 0 p 1である.p j − 2 = p 1 . . p j − 1 p_{0}p_{1}..p_{j-2} = p_{1}..p_{j-1} p0p1..pj−2=p1..pj−1,すなわちP[0…j−2]=P[1…j−1]
以上の導出は,P[0...j−2]=P[1...j−1]が成立する場合にのみ,T[s+1...s+m]=P[0...m−1]が存在することを示している.P[0...j-2]$e$P[1...j-1]の場合、T[s+1...s+m]$e$P[0...m-1]は必然的に生じる.
したがって,Tがs+1からのパターンマッチングを行うのではなく,s+2から試み,式が成立しなければk回目までs+3を試み続け,初めて、こいつを认める*P[0..k]=P[j-k+1.j-1]**こいつを认める**P[0..k]=P[j-k+1..j-1]=P[j-k+1..j-1]こいつを认めるこのときP[j-k+1...j-1]を観察すると、
T[s+j-k+1…s+j-1]=P[j-k+1…j-1]=P[0…k]→to→T[s+j-k+1…s+j-1]=P[0…k]—式3
以前はj番目のマッチングに失敗し、上の3式の成立を確認していたので、私たちはとても楽しかったですp k+1 p_{k+1}pk+1とs s+j s_{s+j}ss+jが比較を開始しました.後の比較も上記の手順を繰り返します.比較したTは遡及しないため効率が高いことが分かる.次に、j番目のマッチングに失敗した後に返されるk値、すなわち、次にT[s+j]と比較するP[k]をNext(j)で表す.ここで、返されるk値は、P[0...k]=P[j-k+1...j-1]を満たす必要があることを明確にする.
次に,問題をk探索値に変換し,Next(j)=kを知っていると仮定し,現在Next(j+1)が要求される.Next(j)=kについて、kがP[j]とT[s+j]のマッチングに失敗したことを明確に知った後、次のT[s+j]とマッチングする位置については、P[k]とT[s+j]が等しいかどうかは分からないが、k値によっては、P[j-k...j-1]=P[0...k-1]=T[s+j-k...s+j-1]がある
ここで、j+1回目のマッチングに失敗したとすると、P[0...j]=T[s...s+j]→to→P[j-k...j]=T[s-k...s+j]となる.この場合,(1)P[k]=P[j]観察P[0...k-1]とP[j-k...j]に分けられ,既にP[j-k...j-1]=P[0...k-1]があり,P[k]=P[j]ならP[0...k]=P[j-k...j]があり,すなわち,j+1回目のマッチングに失敗した場合,次のT[s+j+1]と比較した位置に戻るべきであり,Next(j+1)=k+1である.
(2) P[k] != P[j]しかし、P[j-k...j-1]=P[0...k-1]があり、問題クラス比はP[k]とP[j]のマッチングに失敗した場合、P[0...h-1]=P[k-h...k-1]となるようにh=Next(k)を見つけ、P[h]とP[j]を比較し、等しい場合はh+1を返し、このときP[h+1]とT[s+j+1]をマッチングする必要がある.P[h]!=P[j]は、受信Next()のパラメータが0になるまでステップ(2)を繰り返し、戻り-1は失敗を表す.すなわち、P[0...j-1]の中にP[j]に等しいものは1つもない.このときs:=s+1となり、ターゲット列は一歩前進する.
次に、上記の解析手順に基づいて、再帰アルゴリズムによりj番目の位置マッチングに失敗した後に返すべきk値を算出する.
アルゴリズムは2つの形式で与えられ,1つ目は擬似コード,2つ目はC++コードである.
疑似コード:
Next(P, j)
if j == 0
return -1
k = Next(P, j-1)
while k != -1
if P[k] = P[j-1]
return k+1
k = Next(P, k)
return k+1
C++コード:
//
Next(int next[])
{
int j = 0, k = -1, lengthP = curLength;
next[0] = -1;
while( j < lengthP) //Pj < Pn
{
if( k == -1 || ch[j] == ch[k] ) // P[j-1] P[k]
{
++j; ++k;
next[j] = k; // P[j] = P[k+1]
}
else k = next[k]; //P[j-1] != P[k] ， P[0..k-1] P[j-1]
}
}
int Next(string P, int j)
{
if( j == 0 ) return -1;
int k = j - 1;
do
{
k = Next(P, k);
if( P[k] == P[j-1] ) return k+1;
}while( k != -1 );
return k + 1;
}
// KMP， 1..n 。 ... 。
int KMP(string T, string P)
{
int s, j ;
s = j = 0;
while( abs(j) < P.length() && s < T.length() )
{
cout<まとめ
再帰アルゴリズムは効率が低く、毎回Next値を再計算しますが、KMPがどのように実現されているかをより直感的に理解し、時間+興味があれば再帰を非再帰に書き換え、配列で結果を保存します.もちろん、小さなテクニックでNext()を呼び出して、結果を一緒に保存することもできます.最初は、ちゃんとコントロールできると思っていました.最后に...少し助けてほしいです...殷人昆编集长の《データ构造C++版》も参考にしました.