文字列マッチングのためのKMPアルゴリズム

文字列の照合は、コンピューターの基本的なタスクの 1 つです。

たとえば、「BBC ABCDAB ABCDABCDABDE」という文字列がありますが、そこに「ABCDABD」という別の文字列が含まれているかどうかを知りたいのです。

[[72072]]

このタスクを実行できるアルゴリズムは多数ありますが、Knuth-Morris-Pratt アルゴリズム (略して KMP) は最もよく使用されるアルゴリズムの 1 つです。これは 3 つの *** にちなんで名付けられ、最初の K は有名な科学者の Donald Knuth に由来しています。

[[72073]]

このアルゴリズムは理解しにくいです。インターネット上には多くの説明がありますが、どれも読みにくいです。私は Jake Boxer の記事を読むまで、このアルゴリズムを本当に理解していませんでした。以下では、KMP アルゴリズムについて、私自身の言葉でより分かりやすく説明してみたいと思います。

1.

まず、文字列「BBC ABCDAB ABCDABCDABDE」の最初の文字が、検索語「ABCDABD」の最初の文字と比較されます。 B は A と一致しないため、検索語は 1 つ後ろの位置に移動します。

2.

B は A と一致しないため、検索用語は後ろに移動します。

3.

これは、文字列に検索語の最初の文字と同じ文字が含まれるまで続きます。

4.

次に、文字列の次の文字を検索語と比較します。これはまだ同じです。

#p#

5.

これは、検索語に対応する文字と異なる文字が文字列内に存在するまで続きます。

6.

この時点で、最も自然な対応は、検索語全体を 1 つ前の位置に移動し、最初から 1 つずつ比較することです。これは実行可能ですが、「検索位置」をすでに比較した位置に移動して再度比較する必要があるため、非効率的です。

7.

基本的な事実は、スペースが D と一致しない場合、最初の 6 文字が実際には「ABCDAB」であることがわかるということです。 KMP アルゴリズムの考え方は、この既知の情報を使用して、「検索位置」を比較された位置に戻すのではなく、後方に移動し続けることで効率を向上させることです。

8.

これをどうやって行うのでしょうか?検索用語の部分一致テーブルを計算できます。このテーブルがどのように生成されるかについては後で説明します。今は、使い方だけを知っておいてください。

9.

スペースはDと一致しないこと、そして最初の6文字「ABCDAB」が一致することがわかります。表から、最後に一致する文字 B に対応する「部分一致値」は 2 であることがわかります。したがって、後方に移動するビット数は次の式に従って計算されます。

シフト数 = 一致した文字数 - 対応する部分一致値

6 - 2 は 4 なので、検索語は 4 桁後ろに移動します。

10.

スペースが C と一致しないため、検索語をさらに後ろに移動する必要があります。このとき、一致した文字数は 2 (「AB」) であり、対応する「部分一致値」は 0 です。したがって、シフト数 = 2 - 0、結果は 2 なので、検索語は 2 つ後ろにシフトされます。

11.

スペースがAと一致しないため、1つ後ろに移動します。

12.

C と D が一致しないことがわかるまで、少しずつ比較します。したがって、シフト数 = 6 - 2 となり、検索語は引き続き 4 つ後ろにシフトされます。

#p#

13.

検索語の最後のビットが完全に一致すると判断されるまで、ビットごとに比較し、検索を完了します。検索を続行する場合（つまり、すべての一致を検索する場合）、移動された場所の数 = 7 - 0 となり、検索用語は 7 か所前に戻り、ここでは繰り返されません。

14.

部分一致テーブルが生成される仕組みを次に説明します。

まず、「プレフィックス」と「サフィックス」という 2 つの概念を理解する必要があります。 「プレフィックス」は、最初の文字を除く文字列の先頭の組み合わせ全体を指します。「サフィックス」は、最初の文字を除く文字列の末尾の組み合わせ全体を指します。

15.

「部分一致値」とは、「プレフィックス」と「サフィックス」の最長共通要素の長さです。 「ABCDABD」を例に挙げると、

  - 「A」の接頭辞と接尾辞は両方とも空集合であり、要素の合計の長さは 0 です。 
 
  - 「AB」の接頭辞は[A]、接尾辞は[B]、共通要素の長さは0です。 
 
  - 「ABC」のプレフィックスは[A、AB]、サフィックスは[BC、C]で、要素の合計長は0です。 
 
  - 「ABCD」のプレフィックスは[A、AB、ABC]、サフィックスは[BCD、CD、D]であり、共通要素の長さは0です。 
 
  - 「ABCDA」のプレフィックスは[A、AB、ABC、ABCD]、サフィックスは[BCDA、CDA、DA、A]、合計要素は「A」、長さは1です。 
 
  - 「ABCDAB」のプレフィックスは[A、AB、ABC、ABCD、ABCDA]、サフィックスは[BCDAB、CDAB、DAB、AB、B]、要素の合計は「AB」、長さは2です。 
 
  - 「ABCDABD」のプレフィックスは[A、AB、ABC、ABCD、ABCDA、ABCDAB]、サフィックスは[BCDABD、CDABD、DABD、ABD、BD、D]であり、共通要素の長さは0です。

16.

「部分一致」の本質は、文字列の先頭と末尾が繰り返される場合があることです。たとえば、「ABCDAB」には「AB」が 2 つあるため、「部分一致値」は 2 (「AB」の長さ) になります。検索語が移動すると、最初の「AB」は 4 桁 (文字列の長さ - 部分一致の値) 後方に移動し、2 番目の「AB」の位置に到達します。

オリジナルリンク: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html