部分文字列を検索します。 クヌース–モリス–プラットアルゴリズム

情報を検索するタスクで最も重要なタスクの1つは、文字列内の正確に指定されたサブストリングを検索することです。 文字列内の部分文字列のプリミティブ検索アルゴリズムは、長さが検索パターンの長さに等しいすべての部分文字列の列挙と、そのような部分文字列と検索パターンとの文字ごとの比較に基づいています。 伝統的に、検索パターンまたはパターンを針（英語の「針」）として指定し、検索が実行される行を干し草（英語の「干し草」）として指定するのが慣例です。 Pythonでは、プリミティブアルゴリズムは次のようになります。

index = -1 for i in xrange(len(haystack)-len(needle)+1): success = True for j in xrange(len(needle)): if needle[j]<>haystack[i+j]: success = False break if success: index = i break print index
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

n = | haystack |、m = | needle |を示します。 最も単純な検索アルゴリズムは、最良の場合であっても、n – m + 1の比較を実行します。 部分一致が多数ある場合、速度はO（n * m）に低下します。



以下で検討するアルゴリズムは、「良い」データでは低速ですが、「悪い」データでの回帰がないことで補われます。 Knut-Morris-Prattアルゴリズムは、最初の最悪の場合の線形推定アルゴリズムの1つです。 アルゴリズムの説明に進む前に、プレフィックス関数の概念を考慮する必要があります。



文字列π（S、i）の接頭辞関数は、文字列S [1..i]の最大接頭辞の長さであり、この文字列と一致せず、同時にその接尾辞でもあります。 簡単に言えば、これは、行の最も長い開始点の長さであり、行の最後でもあります。 文字列Sの場合、プレフィックス関数を長さ| S | -1のベクトルとして表すと便利です。 π（S、1）= 0と設定することにより、長さ| S |のプレフィックス関数を考慮することができます。 文字列「abcdabcabcdabcdab」の関数プレフィックスの例：

S [i]	a	b	c	d	a	b	c	a	b	c	d	a	b	c	d	a	b
π（S、i）	0	0	0	0	1	2	3	1	2	3	4	5	6	7	4	5	6

π（S、i）= kと仮定します。 プレフィックス関数の次のプロパティに注意してください。

1. S [i + 1] = S [k + 1]の場合、π（S、i + 1）= k + 1。
2. S [1..π（S、k）]は、文字列S [1..i]の接尾辞です。 実際、文字列S [1..i]が文字列S [1 ...π（S、i）] = S [1..k]で終わり、文字列S [1..k]が文字列S [1..π]で終わる場合（S、k）]の場合、線S [1..i]は線S [1..π（S、k）]で終了します。
3. ∀j∈（k、i）、S [1..j]は文字列S [1..i]の接尾辞ではありません。 そうでない場合、j> kであるため、仮定π（S、i）= kは偽になります。

考慮されたプロパティにより、プレフィックス関数を計算するためのアルゴリズムを取得できます。

π（S、i）= kとする。 π（S、i + 1）を計算する必要があります。

1. S [i + 1] = S [k + 1]の場合、π（S、i + 1）= k + 1。
2. それ以外の場合、k = 0の場合、π（S、i + 1）= 0です。
3. それ以外の場合、k：=π（S、k）を入力して、ステップ1に進みます。

アルゴリズムの本質を理解するための鍵は、前のステップで見つかったサフィックスを次の位置に拡張できない場合、できるだけ小さなサフィックスを考慮しようとするという事実です。



Pythonでプレフィックス関数を計算するアルゴリズム：

 def prefix(s): v = [0]*len(s) for i in xrange(1,len(s)): k = v[i-1] while k > 0 and s[k] <> s[i]: k = v[k-1] if s[k] == s[i]: k = k + 1 v[i] = k return v
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

アルゴリズムの実行時間がO（n）であることがわかります。ここで、n = | S |です。 アルゴリズムの漸近的な動作は、whileループの反復の総数によって決定されることに注意してください。 これは、whileループを考慮せずに、forループの各反復が定数を超えない時間で実行されるためです。 サイクルの各反復で、kが1以下しか増加しないため、可能な最大値k = n – 1を意味します。 kの値はwhileループ内でのみ減少するため、kは合計でn – 1倍以上減少することはできません。 これは、whileループが最終的にn回まで実行されることを意味し、O（n）アルゴリズムの時間の最終的な推定値を提供します。



プレフィックス関数の使用に基づいたKnuth-Morris-Prattアルゴリズムを検討してください。 原始部分文字列検索アルゴリズムの場合と同様に、パターンは一致を検出するために左から右に線に沿って「移動」します。 ただし、重要な違いは、プレフィックス関数を使用すると、意図的に無用なシフトを回避できることです。



S [0..m – 1]をサンプル、T [0..n – 1]を検索対象の文字列とします。 位置iの行の比較を検討します。つまり、パターンS [0..m – 1]は文字列T [i..i + m – 1]の一部にマッピングされます。 文字S [j]とT [i + j]の間で最初の不一致が発生したとします（i <j <m）。 P = S [0..j – 1] = T [i..i + j – 1]を示します。 シフトするとき、接頭辞Sが文字列Pの何らかの接尾辞と収束すると予想できます。接尾辞でもある最長の接頭辞の長さは、インデックスjの文字列Sの接頭辞関数であるため、次のアルゴリズムに到達します。

1. サンプルSのプレフィックス関数を作成し、Fで示します。
2. k = 0、i = 0と入力します。
3. 文字S [k]とT [i]を比較します。 文字が等しい場合は、kを1増やします。同時にkがサンプルの長さと等しくなる場合、文字列TでのサンプルSの出現が検出され、出現のインデックスはi-| S | + 1.アルゴリズムは終了します。 文字が等しくない場合、プレフィックス関数を使用してシフトを最適化します。 k> 0である限り、k = F [k – 1]を割り当てて、ステップ3の最初に進みます。
4. i <| T |の間、iを1増やしてステップ3に進みます。

PythonでのKnut-Morris-Prattアルゴリズムの可能な実装は次のようになります。

 def kmp(s,t): index = -1 f = prefix(s) k = 0 for i in xrange(len(t)): while k > 0 and s[k] <> t[i]: k = f[k-1] if s[k] == t[i]: k = k + 1 if k == len(s): index = i - len(s) + 1 break return index