有限オートマトンと一致する文字列

Question

Cormenの「Introduction to Algorithms」の文字列アルゴリズムについて読んでいます。以下に示す遷移の場合。

私の質問：なぜ私たちはmin(m+1, q+2)を行っていると、なぜ私たちは2

次のリンクで1とqによってメートルを増加しているが上記の質問に地面に戻っています。

http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/Fall2009/StringMatching.pdf

親切に簡単な例をここに助けます。

Algorithm Compute-Transition-Function(P, Sigma) 
m = length(P); 
for q = 0 through m do 
    for each character x in Sigma 
     k = min(m+1, q+2); 
     repeat k = k-1 // work backwards from q+1 
     until Pk 'is-suffix-of' Pqx; 
     d(q, x) = k; // assign transition table 
    end for; 
end for; 

return d; 
End algorithm. 

Answer 1

• それが原因次repeatループkにm + 1では、最初に減少します。
• repeatの場合は、q + 1で開始するので、少なくとも1つのcharを持つため、q + 2です。

  ---

次のコードは、 を境界問題（qは== mが不足している）を持っていますが、インデックスが少し明確にしたいかもしれません。

m = length(P); 
for q = 0 through m - 1 do // Loop through substrings [0, q+1] 
    for each character x in Sigma 
     k = q+1; 
     // work backwards from q+1 
     while not Pk 'is-suffix-of' Pqx; 
     do k = k-1; end do; 
     d(q, x) = k; // assign transition table 
    end for; 
end for; 

return d; 

Answer 2

遷移テーブルのエントリd(q,x)はxを消費する前に、最長一致接頭辞がq文字だった場合、文字xを消費した後、パターンの最長一致プレフィックスの長さが含まれています。 1文字を消費するので、q+1より大きくすることはできません。パターンの長さはmなので、最大でmにすることもできます。内部ループはrepeat k = k-1 until condition(k)です。したがって、何かをテストする前にkがデクリメントされます。したがって、kは、可能な限り大きな結果の1より大きくなるように開始する必要があります。k = min(m,q+1) + 1内側のループがwhile negated_condition(k) { k = k-1; }の場合、k = min(m,q+1)で始まります。

Knuth-Morris-Prattアルゴリズムの境界線表を使用すると、遷移表をより効率的に計算できることに注意してください。

Answer 3

コードはので、ここで説明したのですが、文字列は、だから我々は我々の状態は、パターンの部分一致にしたいナノ

あるとしましょう

に何が起こっているかを確認する例です。 "nano"に一致する可能性のある部分は、 "", "n", "na", "nan", or (the complete match) "nano"です。つまり、文字列の接頭辞にすぎません。一般に、パターンがm文字の場合、m + 1状態が必要です。ここではm = 4であり、5つの状態が存在する。

"...nan"を見て、別の文字の"x"を見た場合、どのような状態に進む必要がありますか？明らかに、xが試合の次のキャラクタ（ここでは「o」）であれば、次に長いプレフィックス（ここでは「nano」）に移動する必要があります。そして、明らかに、我々は完全な試合を見た後、我々はその状態に留まります。しかし、"a"のような別の文字があるとしますか？つまり、これまでの文字列は"...nana"のようになります。最も長い部分一致は、ちょうど"na"であり、最後の2文字を利用することができる。したがって、状態"nan"から、"a"というラベルの矢印を状態"na"に描画する必要があります。 "na"は"nano"のプレフィックス（状態なので）と"nana"という接尾辞です（これは部分的に一致しています）。

一般に、状態+文字から状態への遷移は、元のパターンのプレフィックスと、直前に見た状態+文字の接尾辞である最長の文字列です。これは、すべての遷移がどうあるべきかを私たちに伝えるのに十分です。私たちは、パターン"nano"を探しているなら、遷移表は、今どのように我々は、実際に検索パターンを行うには、このテーブルを使用しない

 n  a  o  other 
    ---  ---  ---  --- 
empty: "n"  empty empty empty  
"n": "n"  "na" empty empty 
"na": "nan" empty empty empty 
"nan": "n"  "na" "nano" empty //just as an illustration, nan + n = n because we can only use the last 'n', nan + a = na because now we can use the last two 'na' 
"nano": "nano" "nano" "nano" "nano" 

でしょうか？

これを文字列"banananona"でシミュレートすると、一度に1文字ずつ移動することによって、空の空の"n", "na", "nan", "na", "nan", "nano", "nano", "nano"の状態のシーケンスが得られます。状態"nano"で終わるので、この文字列には"nano"が含まれています。上の表をどのように使うのかを拡張してみましょう。 'b'では、可能な州のいずれにもありません'n', 'na', 'nan', 'nano'。したがって、空であるとみなされます... 'ba'に到達したときと同じです。次の文字「'n'」を押すと、基本的に空からnになりますので、上記の表を使用して、それが'n'で終わるのを見ます。今はbanananonaの4文字になっていますので、'n'から...を追加して、再びテーブルを使用して、それは状態'na'になります。