KMPアルゴリズムを最初から最後まで徹底的に理解できるように指導します

KMPアルゴリズムを最初から最後まで徹底的に理解できるように指導します

[[121931]]

この記事の参考文献: Li Yunqing 他著「データ構造 (C 言語版)」、アルゴリズム入門

導入：

テキスト編集では、テキスト内の特定の位置にある特定の文字やパターンを見つける必要があることがよくあります。

その結果、文字列の一致の問題が発生します。

この記事では、単純な文字列マッチングアルゴリズムから始めて、Rabin-Karp アルゴリズム、KMP アルゴリズムへと進み、KMP アルゴリズムを最初から最後まで徹底的に理解できるようにします。

『アルゴリズム入門』という本でこの文字列問題の定義を見てみましょう。

テキストは長さnの配列T[1...n]であり、パターンは長さm<=nの配列P[1....m]であると仮定します。

さらに、P と T の要素が有限アルファベット Σ に属する文字であると仮定します。

上の図に基づいて、文字列の一致の問題を説明しましょう。目標は、テキスト T=abcabaabcaabac 内のパターン P=abaa のすべての出現を見つけることです。

このパターンはテキスト内で変位 s=3 のところに 1 回だけ出現します。変位s=3は有効変位です。

1. 単純な文字列マッチングアルゴリズム

単純な文字列マッチングアルゴリズムでは、ループを使用してすべての有効な変位を検索します。

ループは、sのn-m+1個の可能な値のそれぞれに対して条件P[1....m]=T[s+1....s+m]をチェックします。

ナイーブ文字列マッチャー(T, P)

1 n ← 長さ[T]

2 m ← 長さ[P]

3 s ← 0 から n - m まで

4 P[1 ≠ m] = T[s + 1 ≠ s + m]の場合

//n-m+1 個の可能な変位 s の各値に対して、対応する文字を比較するループを m 回実行する必要があります。

5 then print "パターンはシフトで発生します" s

単純な文字列マッチングアルゴリズム。上図はテキスト T=acaabc とパターン P=aab の場合です。

上記のコードの 4 行目では、n-m+1 個の可能な変位 s の各値に対して、対応する文字を比較するループを m 回実行する必要があります。

したがって、最悪の場合、この単純なパターン マッチング アルゴリズムの実行時間は O((n-m+1)m) になります。

--------------------------------

もう 1 つの具体的な例と実行中のプログラムを示します。

対象文字列がbanananobanoで、マッチするパターン文字列がnanoの場合、

以下はマッチングのプロセスです。原理は非常に単純です。対象文字列の最初の文字と比較するだけです。

同じ場合は次のパターンと比較します。異なる場合は、パターンを右に移動します。

次に、パターンの各文字を比較します。このアルゴリズムの動作プロセスを下の図に示します。

//インデックスは、一致する n 個の状況を表します。

  1.  #include<iostream>  
  2.  #include<文字列>  
  3. 使用して 名前空間std;
  4.  intマッチ( const文字列& ターゲット, const文字列& パターン)
  5.  {
  6. ターゲットの長さを整数で指定します。
  7. パターンの長さは、パターンのサイズによって異なります。
  8. ターゲットインデックス = 0;
  9. パターンインデックス= 0;
  10.  (ターゲットインデックス< ターゲット長さ && パターンインデックス < パターン長さ)
  11.  （
  12.  if (ターゲット[ターゲットインデックス]==パターン[パターンインデックス])
  13.  {
  14.  ++ターゲットインデックス;
  15.  ++パターンインデックス;
  16.  }
  17. それ以外 
  18.  {
  19. ターゲットインデックス -= (パターンインデックス-1);
  20. パターンインデックス = 0;
  21.  }
  22.  }
  23.  (パターンインデックス == パターン長さ)
  24.  {
  25.  target_index - pattern_lengthを返します。
  26.  }
  27. それ以外 
  28.  {
  29.  -1 を返します。
  30.  }
  31.  }
  32.  intメイン()
  33.  {
  34.  cout<<match( "バナナナノバノ" 、 "ナノ" )<<endl;
  35.  0を返します。
  36.  }
  37.  //実行結果は 4 です。

上記のアルゴリズムの複雑さはO(pattern_length*target_length)です。

私たちは主にどこで時間を無駄にしているのでしょうか?

ステップインデックス = 2 を見ると、3 つの文字が一致していますが、4 番目の文字が一致していません。この時点で一致した文字列は nan です。

1 つ右に移動すると、nan*** が一致する文字シーケンスは an になりますが、これは明らかに一致ではありません。

次に、もう一度 1 つ右にシフトすると、一致した値は nan*** になります。一致したシーケンスは n であり、一致できます。

パターン自体の情報を事前に知っていれば、一致が失敗するたびに target_index をロールバックする必要はありません。

このようなフォールバックは多くの無駄な時間を浪費します。パターン自体のこれらの特性を事前に計算できれば、

その後、不一致がある場合、パターンを次の可能な位置に直接移動できます。

マッチング不可能な工程は省略します。

上の表に示すように、index=2 で不一致があります。この時点で、パターンを index=4 の状態に直接移動できます。

kmp アルゴリズムはこの時点から始まります。

2. KMPアルゴリズム

1. オーバーレイ関数（overlay_function）

カバー関数はパターン自体の特性を表し、左から始まるパターンのすべての連続する部分文字列の自己カバーの度合いによって表すことができます。

たとえば、次の文字列、abaabcaba

カウントは 0 から始まるため、カバレッジ関数の値が 0 の場合、一致が 1 つあることを示します。カウントを 0 から開始するか、0 から開始するかは好みの問題です。

値はご自身で調整してください。-1はカバレッジなしを意味します。ではカバレッジとは何でしょうか？より数学的な方法で定義を見てみましょう。例えば、シーケンスの場合

a0a1...aj-1 aj

を満たすkを見つけるには

a0a1...ak-1ak=aj-kaj-k+1...aj-1aj

この条件を満たす、これより大きい k は存在しません。つまり、パターンの最初の k 文字が最後の k 文字と一致するように、可能な限り最大の k を見つけるには、k を可能な限り大きくする必要があります。

その理由は、比較的大きなkがある場合、条件を満たすより小さなkを選択すると、

すると、不一致があった場合、パターンが右に移動する位置を大きくし、パターンが移動する位置での一致が少なくなるため、一致の可能性のある結果が失われます。

たとえば、次のシーケンスでは、

赤い部分に不一致があります。正しい結果は k=1 の場合なので、パターンを 4 ビット右にシフトします。k=0 を選択した場合、5 ビット右にシフトするとエラーになります。

このオーバーレイ関数の計算方法は再帰的である。パターンの最初のj文字について、オーバーレイ関数の値がkであれば、

a0a1...ak-1ak=aj-kaj-k+1...aj-1aj

パターンの最初の j+1 シーケンス文字については、次の可能性が考えられます。

(1) パターン[k+1]==パターン[j+1]のとき、オーバーレイ(j+1)=k+1=オーバーレイ(j)+1

⑵ pattern[k+1]≠pattern[j+1] このとき、対応するオーバーレイ関数は、パターンの最初のk+1個のサブシンボルの部分文字列h=overlay(k)にのみ存在します。 pattern[h+1]==pattern[j+1]の場合、overlay(j+1)=h+1となります。 それ以外の場合は、処理(2)を繰り返します。

カバレッジ関数を計算するコードは次のとおりです。

  1.  #include<iostream>  
  2.  #include<文字列>  
  3. 使用して 名前空間std;
  4.  void compute_overlay( const文字列&パターン)
  5.  {
  6. 定数 パターンの長さは、パターンのサイズによって異なります。
  7.  int *overlay_function =新規  int [パターンの長さ];
  8. 整数インデックス;
  9. オーバーレイ関数[0] = -1;
  10.  ( int i=1;i<パターン長;++i)の場合
  11. {
  12. インデックス = overlay_function[i-1];
  13.  // 前の失敗位置 k をインデックスに格納します。  
  14.  (インデックス>=0 && パターン[i]!=パターン[インデックス+1])
  15.  {
  16. インデックス = overlay_function[インデックス];
  17.  }
  18.  if (パターン[i]==パターン[インデックス+1])
  19.  {
  20.  overlay_function[i] = インデックス + 1;
  21.  }
  22. それ以外 
  23.  {
  24. オーバーレイ関数[i] = -1;
  25.  }
  26.  }
  27.  (i=0;i<パターン長;++i)の場合
  28. {
  29.  cout<<オーバーレイ関数[i]<<endl;
  30.  }
  31.  [] overlay_functionを削除します。
  32.  }
  33.  intメイン()
  34.  {
  35. 文字列パターン = "abaabcaba" ;
  36.  compute_overlay(パターン);
  37.  0を返します。
  38.  }

実行結果は次のとおりです。

-1

-1

0

0

1

-1

0

1

2

続行するには任意のキーを押してください

-------------------------------------

2. KMPアルゴリズム

カバレッジ関数を使用すると、kmp アルゴリズムを実装するのは非常に簡単です。原則は左から右に一致させることですが、不一致が発生した場合、target_index を戻す必要はありません。target_index の前に一致した部分は、パターン自体に反映できます。pattern_index を移動するだけで済みます。

j の長さの不一致が発生した場合は、パターンを j-overlay(j) の長さだけ右に移動するだけです。

不一致があるときに pattern_index==0 の場合は、パターンの最初の文字が一致しないことを意味します。

このとき、target_index に 1 を加えて 1 ビット右に移動する必要があります。

さて、次の図は KMP アルゴリズムのプロセスを示しています (赤い部分は KMP アルゴリズムの実行プロセスです)。

さて、*** は KMP アルゴリズム実装の C++ コードを示します。

  1.  #include<iostream>  
  2.  #include<文字列>  
  3.  #include<ベクター>  
  4. 使用して 名前空間std;
  5.  int kmp_find(定数文字列& ターゲット,定数文字列& パターン)
  6.  {
  7. 定数 ターゲットの長さを整数で指定します。
  8. 定数 パターンの長さは、パターンのサイズによって異なります。
  9.  int * overlay_value =新しい  int [パターンの長さ];
  10. オーバーレイ値[0] = -1;
  11. 整数インデックス = 0;
  12.  ( int i=1;i<パターン長;++i)の場合
  13. {
  14. インデックス = overlay_value[i-1];
  15.  (インデックス>=0 && パターン[インデックス+1]!=パターン[i])
  16.  {
  17. インデックス = overlay_value[インデックス];
  18.  }
  19.  (パターン[インデックス+1]==パターン[i])の場合
  20. {
  21.  overlay_value[i] = インデックス +1;
  22.  }
  23. それ以外 
  24.  {
  25. オーバーレイ値[i] = -1;
  26.  }
  27.  }
  28.  // 一致アルゴリズムの開始 
  29. パターンインデックス= 0;
  30. ターゲットインデックス = 0;
  31.  (パターンインデックス<パターン長さ&&ターゲットインデックス<ターゲット長さ)
  32.  {
  33.  if (ターゲット[ターゲットインデックス]==パターン[パターンインデックス])
  34.  {
  35.  ++ターゲットインデックス;
  36.  ++パターンインデックス;
  37.  }
  38. それ以外  (パターンインデックス==0)の場合
  39. {
  40.  ++ターゲットインデックス;
  41.  }
  42. それ以外 
  43.  {
  44. パターンインデックス = オーバーレイ値[パターンインデックス-1]+1;
  45.  }
  46.  }
  47.  (パターンインデックス==パターン長さ)の場合
  48. {
  49.  target_index-pattern_indexを返します。
  50.  }
  51. それ以外 
  52.  {
  53.  -1 を返します。
  54.  }
  55.  [] overlay_valueを削除します。
  56.  }
  57.  intメイン()
  58.  {
  59. 文字列ソース = " annbcdanacadsannannabnna " ;
  60. 文字列パターン = " annacanna" ;
  61.  cout<<kmp_find(ソース、パターン)<<endl;
  62.  0を返します。
  63.  }
  64.  //演算の結果は -1 です。  

3. kmpアルゴリズムのソース

kmp は非常に独創的ですが、どのようにして生まれたのでしょうか。また、なぜ 3 人で考案する必要があったのでしょうか。実際、kmp アルゴリズムがなくても、文字マッチングでは同様に効率的なアルゴリズムを見つけることができます。このアルゴリズムは、最終的には kmp アルゴリズムと同等ですが、このアルゴリズムの開始点はカバー関数ではなく、マッチングの内部原理から直接開始されません。この方法を使用して計算されたカバー関数は複雑で理解しにくいですが、このカバー関数が見つかると、将来同じパターンを使用してマッチングする効率は kmp と同じになります。実際、このアルゴリズムによって見つかった関数は、検索プロセス中にカバーの問題がまったく考慮されていないため、カバー関数と呼ぶべきではありません。

長々と話しましたが、この方法とは何でしょうか? この方法は有名な決定性有限状態オートマトン (DFA) です。 DFA が認識できる文法はタイプ 3 文法で、正規文法または規則文法とも呼ばれます。 規則文法を認識できるため、決定性文字列の認識は間違いなく問題ありません (決定性文字列は正規表現のサブセットです)。 DFA を構築する完全なアルゴリズムがありますが、ここでは紹介しません。 DFA を使用して特定の文字列を認識するのは、実際にはやりすぎです。DFA はより一般的な正規表現を認識できますが、特定の文字列を認識するために DFA を構築する一般的な方法を使用すると、オーバーヘッドが大きくなりすぎます。

kmp アルゴリズムの価値は、文字マッチング問題自体の特性から出発し、パターン自体の特性を表すカバー関数の概念を巧みに利用して、文字列を認識するための DFA を迅速かつ直接的に生成することにあります。したがって、kmp のようなアルゴリズムの場合、高校の数学で理解できますが、そのようなアルゴリズムをゼロから設計する場合は、比較的深い数学の基礎が必要です。

原文: http://www.2cto.com/kf/201104/87381.html

著者の声明: この 24 個の古典的なアルゴリズムのシリーズの著作権は July が個人的に所有しています。転載する場合は出典を明記してください。

<<:  クイックソートアルゴリズムの詳細な分析

>>:  必ず読むべき28の古典的なプログラミングアルゴリズム

ブログ    
ブログ    
ブログ    
ブログ    

推薦する

...

...

人工知能の「指紋採取」が検出困難な癌と闘う

検出が難しい膠芽腫などの癌の生存率は1桁ですが、早期治療には検出、治療、監視のための高度な技術が必要...

自動運転車はどれくらい遠いのでしょうか?

現在、5Gや人工知能産業が活況を呈しており、さまざまな大手企業が利益を最大化するために「応用シナリオ...

AIとビッグデータ2017「成長痛」

2017 年、人工知能とビッグデータの開発では次の 10 の成長痛が発生しました。 [[21567...

...

未来：ビッグデータとAIがあなたをより深く理解する

今の時代の発展は本当に速すぎます、それを今実感していただけると思います。 3G から 4G、そして ...

AIとIoT：共生関係

Transforma Insights では、2020 年の大半を、最も優れた詳細な IoT 予測の...

アコーディオン: HBase メモリ圧縮アルゴリズム

最近では、HBase ベースの製品の読み取り速度と書き込み速度に対する要件がますます高まっています。...

今後3年間で、人工知能は全国の小売業界に影響を与える大きな嵐となるでしょう。排除されてしまうのでしょうか？

10 年前、ほとんどの人は、今日では現金やカードを持ち歩かずに携帯電話だけを持って街を歩き回り、買...

Baidu の計算生物学研究が Nature のサブジャーナルに掲載されました!スタンフォード大学やMITを上回る成果、製薬分野に進出

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載...

テスラAIディレクター：33年前にルカンのニューラルネットワークを再現したが、今とあまり変わらない

最近、Tesla AI のシニアディレクターである Andrej Karpathy 氏が、非常に興味...

...

...

ディープラーニングパーセプトロンの原理の詳しい説明

前回の機械学習のトピックは終了しました。機械学習の分野でよく使用されるアルゴリズム、モデル、その原理...