【オリジナル】なぜKMPアルゴリズムにおける主列ポインタはロールバックを必要としないのか
KMP(Knuth-Morris-Pratt)アルゴリズムの出現の前因と結果について,その解決可能な問題と潜在的な効率の向上については,本やネットワーク上で見つけられる資源が多すぎて,本稿ではこれ以上述べない.
この文章の主な目的は、自分の実際の総括と心得を結びつけて、別の角度から、KMPアルゴリズムマッチングにおける主列のポインタが戻る必要がない理由をさらに説明することである.
背景
KMPアルゴリズムを学習する前に、次の例では、現在のマッチングが文字'e'に進み、失敗したなど、いくつかの例で説明されることがよく見られました.
a b a d
a b a d
次に、一般的な説明では、マッチングは、現在の主列'e'から直接開始することができる.すなわち、主列のポインタはロールバックする必要はなく、パターン列がポインタを位置にシフトさせてマッチングを継続するだけでよい.
このプレゼンテーションの説明は確かに分かりやすく、操作性が高い.しかし、個人的には、なぜ主列に見えるポインタが遡及する必要がないのかを理論/汎用性の観点から理解するのは難しい.
例えば現在、主文字列T[t 1,t 2,t 3,...,tn]、パターン列P[p 1,p 2,p 3,...pm]があり、主列とパターン列のポインタは、最初のマッチング時にk+1の位置に一致し、すなわちTとPの前のk文字が1:1で一致し、
t1 t2 t3 ... tktk+1 ... tn
p1 p2 p3 ... pkpk+1 ... pm
具体的な文字が現れない場合、Tのk+1での文字列ポインタが2文字目に戻る必要がないことをどのように説明しますか?
この疑問は私の頭の中に長く残っていて、私も大量の資料を探すことを試みて、《アルゴリズムの導論》を含んで、KMPの3人の作者が共同で発表した論文《Fast pattern matching in strings》を含んで、残念ながら基本的に1筆持ったことがあるか、あるいは本人の資質に限られて、その中の説明を理解することができませんでした.
クオラでKMPの解釈に関する文章を見るまで、主にnext(j)をどのように検索するかをめぐって説明したが、私の疑問を理解し、解決する別の考え方を提供してくれた.
もし他の学生も私と同じ疑問を持っていたら、私のこの文章があなたを助けることができることを望んでいます.
本題に入る
本明細書で説明する用語の定義を簡単に説明します.
パターン列P.すなわち、通常文字列検索で言及されるサブ列である.長さm、ポインタは現在の文字の位置をjと定義することを示す.
主列T.すなわち、一致する文字列であり、この文字列において、上モード列を完全に一致させることができる開始位置を検索する.長さn(n>m)、ポインタは現在の文字の位置をiとして定義することを示す.
iとjの最初のマッチングはいずれも1から計算を開始する.すなわち、t 1はTの最初の文字を表し、p 1はPの最初の文字を表す.
前に数回のマッチングが行われて失敗したと仮定し、現在の1回のマッチングは、主列の任意の位置k+1から始まり、主列とモード列は連続L文字のマッチングに成功した.主列の位置(k+L+1)へのマッチングに失敗しました.
では、k+L+1=i(it1 t2 t3 ... tk
tk+1 tk+2 tk+3 ... tk+L
tk+L+1
... ... ... tn
p1 p2 p3 ... pL
pL+1
... pm
私の前の疑問は、もし主列ポインタが(k+L+1)から(k+2)の位置に遡らなければ、もしk+2でパターン列と主列が一致し始めたら、このような一致に成功したシーンが、漏れてしまう可能性があるのではないかということです.
次に,(k+2)においてモード列と主列が本当に一致する可能性があると仮定すると,我々の既知の情報に基づいて,必然的に次のような内容が成立する必要がある.
[p1, p2, p3, ..., pL-1 ] == [tk+2, tk+3, tk+4, ..., tk+L]
分析を続け、
Alt 1:もし私たちの主列とモード列が確かに上記の条件を満たすことができたら、次に私たちがマッチングする必要があるのはpLとtk+L+1で、見ましたか、この時主列のポインタは遡及前の位置に着きました;
Alt 2:我々の主列とモードが上記の条件を満たすことができない場合、主列ポインタは(k+2)の位置マッチングプロセスを終了することができ、位置ポインタは(k+3)の位置を再指し示すことができ、モード列は再び1の位置に遡り、主列とモード列が正常にマッチングする可能性があるかどうかを引き続き見ることができる.
次に,(k+3)においてモード列と主列が本当に一致する可能性があると仮定すると,我々の既知の情報に基づいて,必然的に次のような内容が成立する必要がある.
[p1, p2, p3, ..., pL-2 ] == [tk+3, tk+4, tk+5, ..., tk+L]
どのように、よく知っていると思いますか.これは上述したAlt 1とAlt 2の分析を繰り返す過程で、最終的な結果は2つで、このとき主列のポインタがk+L+1の位置に着いたのか、主列のポインタが次のラウンドに入った(k+4)の位置から一致する過程です.
上記の手順を繰り返すことができれば,マッチングは常に発見されず,(k+L)まで主列ポインタが指し示すまで,モード列ポインタは再び1の位置に遡り,以下の式が成立するか否かを判断する必要がある:[p 1]=[tk+L]
また、我々の分析結果:成立すれば、次の主列とモード列が一致する文字は、主列ポインタの(k+L+1)の位置で、モード列のt 2と一致するが、このとき主列の位置は、最初にk位置から一致し始めたときに、一致に失敗した位置である.式が成立しない場合、主列ポインタは自然に(k+L+1)の位置を指し、モード列はp 1を用いてtk+L+1とマッチングを開始する必要がある.
結論
上記の過程の分析から,主列がk+1の位置からモード列と整合し始めると,L個の連続文字の整合に成功した後,主列のポインタは後退する必要がないことが分かったが,実は:
マルチホイールの暗黙的な遡及整合過程があると仮定し,既知の情報[p 1,p 2,p 3,...,pL]=[tk+1,tk+2,tk+3,...,tk+L]を用いて,これらのホイール整合のうち少なくとも1つが主列の(k+L+1)文字の前に,すべての文字が有効なモード列文字と整合することに成功するかどうかにかかわらず,完全に推定できる.最終的には、取得者列ポインタが(k+L+1)、すなわちiという位置を指す.
では,相対的にポインタiを主列に遡る必要がなく,モード列の位置ポインタjの位置変化(next(j)関数)を調整することで,迅速なマッチングの効果を達成する.
参考文献 https://www.quora.com/How-do-... http://www.mathcs.emory.edu/~... https://blog.csdn.net/v_july_... http://www.doc88.com/p-097376...
この文章の主な目的は、自分の実際の総括と心得を結びつけて、別の角度から、KMPアルゴリズムマッチングにおける主列のポインタが戻る必要がない理由をさらに説明することである.
背景
KMPアルゴリズムを学習する前に、次の例では、現在のマッチングが文字'e'に進み、失敗したなど、いくつかの例で説明されることがよく見られました.
a b a d
e f g h i a b a d
x a 次に、一般的な説明では、マッチングは、現在の主列'e'から直接開始することができる.すなわち、主列のポインタはロールバックする必要はなく、パターン列がポインタを位置にシフトさせてマッチングを継続するだけでよい.
このプレゼンテーションの説明は確かに分かりやすく、操作性が高い.しかし、個人的には、なぜ主列に見えるポインタが遡及する必要がないのかを理論/汎用性の観点から理解するのは難しい.
例えば現在、主文字列T[t 1,t 2,t 3,...,tn]、パターン列P[p 1,p 2,p 3,...pm]があり、主列とパターン列のポインタは、最初のマッチング時にk+1の位置に一致し、すなわちTとPの前のk文字が1:1で一致し、
t1 t2 t3 ... tktk+1 ... tn
p1 p2 p3 ... pkpk+1 ... pm
具体的な文字が現れない場合、Tのk+1での文字列ポインタが2文字目に戻る必要がないことをどのように説明しますか?
この疑問は私の頭の中に長く残っていて、私も大量の資料を探すことを試みて、《アルゴリズムの導論》を含んで、KMPの3人の作者が共同で発表した論文《Fast pattern matching in strings》を含んで、残念ながら基本的に1筆持ったことがあるか、あるいは本人の資質に限られて、その中の説明を理解することができませんでした.
クオラでKMPの解釈に関する文章を見るまで、主にnext(j)をどのように検索するかをめぐって説明したが、私の疑問を理解し、解決する別の考え方を提供してくれた.
もし他の学生も私と同じ疑問を持っていたら、私のこの文章があなたを助けることができることを望んでいます.
本題に入る
本明細書で説明する用語の定義を簡単に説明します.
パターン列P.すなわち、通常文字列検索で言及されるサブ列である.長さm、ポインタは現在の文字の位置をjと定義することを示す.
主列T.すなわち、一致する文字列であり、この文字列において、上モード列を完全に一致させることができる開始位置を検索する.長さn(n>m)、ポインタは現在の文字の位置をiとして定義することを示す.
iとjの最初のマッチングはいずれも1から計算を開始する.すなわち、t 1はTの最初の文字を表し、p 1はPの最初の文字を表す.
前に数回のマッチングが行われて失敗したと仮定し、現在の1回のマッチングは、主列の任意の位置k+1から始まり、主列とモード列は連続L文字のマッチングに成功した.主列の位置(k+L+1)へのマッチングに失敗しました.
では、k+L+1=i(i
tk+1 tk+2 tk+3 ... tk+L
tk+L+1
... ... ... tn
p1 p2 p3 ... pL
pL+1
... pm
私の前の疑問は、もし主列ポインタが(k+L+1)から(k+2)の位置に遡らなければ、もしk+2でパターン列と主列が一致し始めたら、このような一致に成功したシーンが、漏れてしまう可能性があるのではないかということです.
次に,(k+2)においてモード列と主列が本当に一致する可能性があると仮定すると,我々の既知の情報に基づいて,必然的に次のような内容が成立する必要がある.
[p1, p2, p3, ..., pL-1 ] == [tk+2, tk+3, tk+4, ..., tk+L]
分析を続け、
Alt 1:もし私たちの主列とモード列が確かに上記の条件を満たすことができたら、次に私たちがマッチングする必要があるのはpLとtk+L+1で、見ましたか、この時主列のポインタは遡及前の位置に着きました;
Alt 2:我々の主列とモードが上記の条件を満たすことができない場合、主列ポインタは(k+2)の位置マッチングプロセスを終了することができ、位置ポインタは(k+3)の位置を再指し示すことができ、モード列は再び1の位置に遡り、主列とモード列が正常にマッチングする可能性があるかどうかを引き続き見ることができる.
次に,(k+3)においてモード列と主列が本当に一致する可能性があると仮定すると,我々の既知の情報に基づいて,必然的に次のような内容が成立する必要がある.
[p1, p2, p3, ..., pL-2 ] == [tk+3, tk+4, tk+5, ..., tk+L]
どのように、よく知っていると思いますか.これは上述したAlt 1とAlt 2の分析を繰り返す過程で、最終的な結果は2つで、このとき主列のポインタがk+L+1の位置に着いたのか、主列のポインタが次のラウンドに入った(k+4)の位置から一致する過程です.
上記の手順を繰り返すことができれば,マッチングは常に発見されず,(k+L)まで主列ポインタが指し示すまで,モード列ポインタは再び1の位置に遡り,以下の式が成立するか否かを判断する必要がある:[p 1]=[tk+L]
また、我々の分析結果:成立すれば、次の主列とモード列が一致する文字は、主列ポインタの(k+L+1)の位置で、モード列のt 2と一致するが、このとき主列の位置は、最初にk位置から一致し始めたときに、一致に失敗した位置である.式が成立しない場合、主列ポインタは自然に(k+L+1)の位置を指し、モード列はp 1を用いてtk+L+1とマッチングを開始する必要がある.
結論
上記の過程の分析から,主列がk+1の位置からモード列と整合し始めると,L個の連続文字の整合に成功した後,主列のポインタは後退する必要がないことが分かったが,実は:
マルチホイールの暗黙的な遡及整合過程があると仮定し,既知の情報[p 1,p 2,p 3,...,pL]=[tk+1,tk+2,tk+3,...,tk+L]を用いて,これらのホイール整合のうち少なくとも1つが主列の(k+L+1)文字の前に,すべての文字が有効なモード列文字と整合することに成功するかどうかにかかわらず,完全に推定できる.最終的には、取得者列ポインタが(k+L+1)、すなわちiという位置を指す.
では,相対的にポインタiを主列に遡る必要がなく,モード列の位置ポインタjの位置変化(next(j)関数)を調整することで,迅速なマッチングの効果を達成する.
参考文献