KMPアルゴリズム(Matrix神牛から転載)
もし機械室がもうすぐ閉まるならば、あるいはあなたが急いでMMとデートするならば、直接6番目の自然段に飛び込んでください.
ここでいうKMPは、映画を上映するためのものではなく、アルゴリズムです.KMPアルゴリズムは文字列マッチングを処理するために使用されます.言い換えれば、B列がA列のサブ列(A列にB列が含まれているかどうか)かどうかを答える必要があります.例えば、文字列A=「I'm matrix 67」、文字列B=「matrix」ああ、BはAの子串だと言います.あなたは婉曲にあなたのMMに闻くことができます:“もしあなたが好きな人に告白するならば、私の名前はあなたの告白の言叶の中の子串ですか?”
このような問題を解決するには、通常、我々の方法は、A列のどの位置からBとマッチングを開始し、マッチングするかどうかを検証することである.A列長がn,B列長がmの場合,この方法の複雑さはO(mn)である.複雑さがmnに達しない場合が多いが(検証時に最初の1文字か2文字だけを見て不一致を発見)、A=「aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
KMPというのは、このアルゴリズムがKnuth、Morris、Prattの3つから提案され、この3人の名前の最初のアルファベットを取ったからです.このとき、AVLツリーがなぜAVLなのか、Bellman-Fordがなぜ鉄棒なのかが急に分かったのかもしれません.時々7、8人が研究したことがありますが、どうやって命名しますか?通常、これは「3 x+1問題」などの論争を避けるために、人の名前で命名する必要はありません.話が遠くなった.
個人的にはKMPは最も言う必要のないものだと思います.これはネット上で多くの資料を見つけることができるからです.しかし、ネット上の論法は基本的に「移動(shift)」、「Next関数」などの概念に関連しており、誤解を生みやすい(少なくとも1年半前にこれらの資料を見てKMPを勉強したときは分からなかった).ここでは、KMPアルゴリズムを説明する方法を変えた.
もし,A="abababaabacb",B="ababacb"であれば,KMPがどのように動作しているかを見てみよう.A[i-j+1..i]はB[1..j]と完全に等しいことを2つのポインタiとjでそれぞれ表した.すなわち、iは増加し続け、iの増加jに応じて変化し、そしてjはA[i]で終わる長さjの文字列がB列の前j文字にぴったり合っている(jはもちろん大きいほど良い)ことを満たしており、現在はA[i+1]とB[j+1]の関係を検証する必要がある.A[i+1]=B[j+1]の場合、iとjはそれぞれ1つずつ加算される.いつj=mになったら、BはAの子列(B列はすでに完成している)と言い、このときのi値からマッチング位置を算出することができる.A[i+1]<>B[j+1]KMPのポリシーは、A[i-j+1..i]がB[1..j]と一致し、新しいB[j+1]がA[i+1]と一致するようにjの位置を調整することである(iとjが増加し続けるようにする).i=j=5の場合を見てみる.
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7
このとき、A[6]<>B[6].これは,このときjが5に等しくないことを示しており,jをそれより小さい値j′に変更する.j'はいくらかもしれませんか.よく考えてみるとj'は、B[1..j]の頭j'文字と末尾j'文字を完全に等しくしなければならない(これによりjがj'になってからiとjの性質を維持し続けることができる).このj'はもちろん大きくなればなるほど良い.ここで、B[1..5]=「ababa」で、頭3文字と末尾3文字が「aba」である.新しいjが3の場合、A[6]はちょうどB[4]と等しい.すると、iは6になり、jは4になる.
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7
以上の例から,新しいjがどれだけiに関係なくB列にのみ関係するかを見ることができる.このような配列P[j]を完全に前処理することができ,B配列のj番目のアルファベットにマッチングし,j+1番目のアルファベットがマッチングできない場合,新しいjが最大でどれだけ大きいかを示す.P[j]はすべてB[1..P[j]=B[j-P[j]+1を満たすべきである.j]の最大値.
その後、A[7]=B[5]、iとjはそれぞれ1ずつ増加した.このとき、A[i+1]<>B[j+1]の場合も発生する.
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7
P[5]=3のため、新しいj=3:
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7
このとき、新しいj=3は依然としてA[i+1]=B[j+1]を満たすことができず、このとき我々は再びj値を小さくし、jを再びP[3]に更新する.
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7
今、iはまだ7で、jはもう1になりました.このときA[8]はB[j+1]に等しくない.このように、jはP[1]、すなわち0に小さくしなければならない.
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 0 1 2 3 4 5 6 7
ついに、A[8]=B[1],iは8,jは1となる.実際には、jが0になってもA[i+1]=B[j+1](例えばA[8]=d)を満たすことができない可能性がある.したがって、正確には、j=0になった場合、i値を増加させるが、A[i]=B[1]が現れるまでjを無視する.
このプロセスのコードは短い(本当に短い)ので、ここで説明します.
最後のj:=P[j]は、複数のマッチングを見つけることができるため、プログラムを継続させるためです.
このプログラムは想像以上に簡単かもしれません.i値の増加に対して、コードはforループを使用しているからです.したがって、このコードは、文字列Aをスキャンし、Bのどの位置に一致するかを更新することをイメージ的に理解することができる.
今、私たちはまた2つの重要な問題を残しました:1、どうしてこのプログラムは線形ですか;二、P配列をどのように迅速に前処理するか.
なぜこのプログラムはO(n)なのですか?実際、主な論争はwhileサイクルが実行回数に不確定な要素を生じさせたことにある.時間的複雑さの償却解析における主な戦略を用い,簡単に言えば,ある変数や関数値の変化を観察することによって,ばらばらで乱雑で不規則な実行回数を積算する.KMPの時間的複雑度分析は,償却分析の典型といえる.上記のプログラムのj値から着手する.whileサイクルを実行するたびにjは減少するが(負には減少できない)、j値を変更する場所は5行目のみである.この行を実行するたびにjは1しか増加できない.そのため、全過程でjは最大n個1を増加した.したがって、jは最大n回減少する機会しかない(j値が減少した回数はもちろんnを超えてはならない.jは永遠に非負の整数であるからである).これはwhileサイクルが合計で最大n回実行されたことを示している.屋台分析によると、forサイクルごとに均等に広げた後、1回のforサイクルの複雑さはO(1)である.全過程は明らかにO(n)であった.このような解析は,後のP配列の前処理過程においても同様に有効であり,同様に前処理過程の複雑さO(m)を得ることができる.
前処理はPの定義に従ってO(m^2)乃至O(m^3)と書く必要はない.P[1],P[2],...,P［j−1］の値を用いてP［j］の値を得た.先ほどのB=「ababacb」について、P[1],P[2],P[3]およびP[4]を求めた場合、P[5]およびP[6]をどのように求めるべきかを見てみましょう.P[4]=2であれば、P[5]は明らかにP[4]+1に等しい.P[4]から分かるように、B[1,2]はすでにB[3,4]と等しくなっており、現在はB[3]=B[5]もあるので、P[5]はP[4]の後に1文字を加えて得ることができる.P[6]もP[5]+1に等しいか.明らかにそうではない.なぜなら、B[P[5]+1]<>B[6].では、「一歩下がる」ことを考えましょう.P[6]がP[5]の場合に含まれるサブストリングから得られる可能性があるか,すなわちP[6]=P[5]+1であるかを考える.ここで納得できない場合はよく見てみましょう.
1 2 3 4 5 6 7 B = a b a b a c b P = 0 0 1 2 3 ?
P[5]=3は、B[1..3]とB[3..5]が共に「aba」であるためである.P[3]=1は,B[1],B[3],B[5]ともに「a」であることを示している.P[6]がP[5]から得られない以上、P[3]から得られるかもしれない(B[2]がちょうどB[6]と等しければ、P[6]はP[3]+1に等しい).明らかに、P[6]もP[3]から得られない.
どうしてこの前処理過程は前のKMPメインプログラムとこんなに似ているのですか?実は、KMPの前処理自体がB列の「自己整合」の過程である.そのコードは上のコードと似ています.
最後に、KMPアルゴリズムはB列のみを前処理するため、このアルゴリズムはこのような問題に適している:1つのB列と1つの異なるA列を与えて、BがどのA列のサブ列であるかを聞く.
シリアルマッチングは研究価値のある問題である.実際,接尾辞ツリー,オートマチックなど多くの方法があり,これらのアルゴリズムは前処理を巧みに運用し,線形の時間で文字列のマッチングを解決することができる.私たちは後で話します.
ここでいうKMPは、映画を上映するためのものではなく、アルゴリズムです.KMPアルゴリズムは文字列マッチングを処理するために使用されます.言い換えれば、B列がA列のサブ列(A列にB列が含まれているかどうか)かどうかを答える必要があります.例えば、文字列A=「I'm matrix 67」、文字列B=「matrix」ああ、BはAの子串だと言います.あなたは婉曲にあなたのMMに闻くことができます:“もしあなたが好きな人に告白するならば、私の名前はあなたの告白の言叶の中の子串ですか?”
このような問題を解決するには、通常、我々の方法は、A列のどの位置からBとマッチングを開始し、マッチングするかどうかを検証することである.A列長がn,B列長がmの場合,この方法の複雑さはO(mn)である.複雑さがmnに達しない場合が多いが(検証時に最初の1文字か2文字だけを見て不一致を発見)、A=「aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
KMPというのは、このアルゴリズムがKnuth、Morris、Prattの3つから提案され、この3人の名前の最初のアルファベットを取ったからです.このとき、AVLツリーがなぜAVLなのか、Bellman-Fordがなぜ鉄棒なのかが急に分かったのかもしれません.時々7、8人が研究したことがありますが、どうやって命名しますか?通常、これは「3 x+1問題」などの論争を避けるために、人の名前で命名する必要はありません.話が遠くなった.
個人的にはKMPは最も言う必要のないものだと思います.これはネット上で多くの資料を見つけることができるからです.しかし、ネット上の論法は基本的に「移動(shift)」、「Next関数」などの概念に関連しており、誤解を生みやすい(少なくとも1年半前にこれらの資料を見てKMPを勉強したときは分からなかった).ここでは、KMPアルゴリズムを説明する方法を変えた.
もし,A="abababaabacb",B="ababacb"であれば,KMPがどのように動作しているかを見てみよう.A[i-j+1..i]はB[1..j]と完全に等しいことを2つのポインタiとjでそれぞれ表した.すなわち、iは増加し続け、iの増加jに応じて変化し、そしてjはA[i]で終わる長さjの文字列がB列の前j文字にぴったり合っている(jはもちろん大きいほど良い)ことを満たしており、現在はA[i+1]とB[j+1]の関係を検証する必要がある.A[i+1]=B[j+1]の場合、iとjはそれぞれ1つずつ加算される.いつj=mになったら、BはAの子列(B列はすでに完成している)と言い、このときのi値からマッチング位置を算出することができる.A[i+1]<>B[j+1]KMPのポリシーは、A[i-j+1..i]がB[1..j]と一致し、新しいB[j+1]がA[i+1]と一致するようにjの位置を調整することである(iとjが増加し続けるようにする).i=j=5の場合を見てみる.
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7
このとき、A[6]<>B[6].これは,このときjが5に等しくないことを示しており,jをそれより小さい値j′に変更する.j'はいくらかもしれませんか.よく考えてみるとj'は、B[1..j]の頭j'文字と末尾j'文字を完全に等しくしなければならない(これによりjがj'になってからiとjの性質を維持し続けることができる).このj'はもちろん大きくなればなるほど良い.ここで、B[1..5]=「ababa」で、頭3文字と末尾3文字が「aba」である.新しいjが3の場合、A[6]はちょうどB[4]と等しい.すると、iは6になり、jは4になる.
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7
以上の例から,新しいjがどれだけiに関係なくB列にのみ関係するかを見ることができる.このような配列P[j]を完全に前処理することができ,B配列のj番目のアルファベットにマッチングし,j+1番目のアルファベットがマッチングできない場合,新しいjが最大でどれだけ大きいかを示す.P[j]はすべてB[1..P[j]=B[j-P[j]+1を満たすべきである.j]の最大値.
その後、A[7]=B[5]、iとjはそれぞれ1ずつ増加した.このとき、A[i+1]<>B[j+1]の場合も発生する.
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7
P[5]=3のため、新しいj=3:
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7
このとき、新しいj=3は依然としてA[i+1]=B[j+1]を満たすことができず、このとき我々は再びj値を小さくし、jを再びP[3]に更新する.
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7
今、iはまだ7で、jはもう1になりました.このときA[8]はB[j+1]に等しくない.このように、jはP[1]、すなわち0に小さくしなければならない.
i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 0 1 2 3 4 5 6 7
ついに、A[8]=B[1],iは8,jは1となる.実際には、jが0になってもA[i+1]=B[j+1](例えばA[8]=d)を満たすことができない可能性がある.したがって、正確には、j=0になった場合、i値を増加させるが、A[i]=B[1]が現れるまでjを無視する.
このプロセスのコードは短い(本当に短い)ので、ここで説明します.
j:=0;
for i:=1 to n do
begin
while (j>0) and (B[j+1]<>A[i]) do j:=P[j];
if B[j+1]=A[i] then j:=j+1;
if j=m then
begin
writeln('Pattern occurs with shift ',i-m);
j:=P[j];
end;
end; 最後のj:=P[j]は、複数のマッチングを見つけることができるため、プログラムを継続させるためです.
このプログラムは想像以上に簡単かもしれません.i値の増加に対して、コードはforループを使用しているからです.したがって、このコードは、文字列Aをスキャンし、Bのどの位置に一致するかを更新することをイメージ的に理解することができる.
今、私たちはまた2つの重要な問題を残しました:1、どうしてこのプログラムは線形ですか;二、P配列をどのように迅速に前処理するか.
なぜこのプログラムはO(n)なのですか?実際、主な論争はwhileサイクルが実行回数に不確定な要素を生じさせたことにある.時間的複雑さの償却解析における主な戦略を用い,簡単に言えば,ある変数や関数値の変化を観察することによって,ばらばらで乱雑で不規則な実行回数を積算する.KMPの時間的複雑度分析は,償却分析の典型といえる.上記のプログラムのj値から着手する.whileサイクルを実行するたびにjは減少するが(負には減少できない)、j値を変更する場所は5行目のみである.この行を実行するたびにjは1しか増加できない.そのため、全過程でjは最大n個1を増加した.したがって、jは最大n回減少する機会しかない(j値が減少した回数はもちろんnを超えてはならない.jは永遠に非負の整数であるからである).これはwhileサイクルが合計で最大n回実行されたことを示している.屋台分析によると、forサイクルごとに均等に広げた後、1回のforサイクルの複雑さはO(1)である.全過程は明らかにO(n)であった.このような解析は,後のP配列の前処理過程においても同様に有効であり,同様に前処理過程の複雑さO(m)を得ることができる.
前処理はPの定義に従ってO(m^2)乃至O(m^3)と書く必要はない.P[1],P[2],...,P［j−1］の値を用いてP［j］の値を得た.先ほどのB=「ababacb」について、P[1],P[2],P[3]およびP[4]を求めた場合、P[5]およびP[6]をどのように求めるべきかを見てみましょう.P[4]=2であれば、P[5]は明らかにP[4]+1に等しい.P[4]から分かるように、B[1,2]はすでにB[3,4]と等しくなっており、現在はB[3]=B[5]もあるので、P[5]はP[4]の後に1文字を加えて得ることができる.P[6]もP[5]+1に等しいか.明らかにそうではない.なぜなら、B[P[5]+1]<>B[6].では、「一歩下がる」ことを考えましょう.P[6]がP[5]の場合に含まれるサブストリングから得られる可能性があるか,すなわちP[6]=P[5]+1であるかを考える.ここで納得できない場合はよく見てみましょう.
1 2 3 4 5 6 7 B = a b a b a c b P = 0 0 1 2 3 ?
P[5]=3は、B[1..3]とB[3..5]が共に「aba」であるためである.P[3]=1は,B[1],B[3],B[5]ともに「a」であることを示している.P[6]がP[5]から得られない以上、P[3]から得られるかもしれない(B[2]がちょうどB[6]と等しければ、P[6]はP[3]+1に等しい).明らかに、P[6]もP[3]から得られない.
どうしてこの前処理過程は前のKMPメインプログラムとこんなに似ているのですか?実は、KMPの前処理自体がB列の「自己整合」の過程である.そのコードは上のコードと似ています.
P[1]:=0;
j:=0;
for i:=2 to m do
begin
while (j>0) and (B[j+1]<>B[i]) do j:=P[j];
if B[j+1]=B[i] then j:=j+1;
P[i]:=j;
end; 最後に、KMPアルゴリズムはB列のみを前処理するため、このアルゴリズムはこのような問題に適している:1つのB列と1つの異なるA列を与えて、BがどのA列のサブ列であるかを聞く.
シリアルマッチングは研究価値のある問題である.実際,接尾辞ツリー,オートマチックなど多くの方法があり,これらのアルゴリズムは前処理を巧みに運用し,線形の時間で文字列のマッチングを解決することができる.私たちは後で話します.