この検索アルゴリズムの実施例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/08 01:52 UTC 版)
「クヌース–モリス–プラット法」の記事における「この検索アルゴリズムの実施例」の解説
実際にこのアルゴリズムがどのように動作するかを見てみよう。このアルゴリズムの状態は二つの整数 m と i で表される。m はテキスト S 内の文字の位置であり、単語 W にマッチする可能性のある位置でもある。i は、その時点で照合中の W 内の文字の位置を示す。検索開始時点の状態は以下のように表される。 m: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDEW: ABCDABDi: 0123456 まず、上記の状態で W の先頭と S の先頭から照合していく。この例では4文字目の照合で S[3] が空白、W[3] = 'D' となるため、不一致となる。W 内でそこまでに照合された範囲で 'A' が 0 番目にしかないことから、そこまで照合した S の範囲内に 'A' が出現しないことは明らかである。つまり、S[1] から S[3] までは W[0] とマッチすることはない。そのため、次の照合を単純に S[1] から開始するのではなく、m = 4 および i = 0 として次の照合を開始する。 m: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDEW: ABCDABDi: 0123456 ここで、"ABCDAB" までマッチすることがわかるが、W[6] (S[10]) で不一致となる。しかし、前回の不一致とは異なり、"AB" が2回出現していることに注意が必要である。この範囲での2回目の "AB" は W の先頭ともマッチするので、ここでは m = 8 および i = 2 として照合を再開する。これにより S の事前にマッチした文字列の照合を省くだけでなく、W 内の照合済み文字列の照合も省略している。 m: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDEW: ABCDABDi: 0123456 今回の照合は即座に失敗し、次の照合は m = 11 および i = 0 として再開する。 m: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDEW: ABCDABDi: 0123456 ここでも "ABCDAB" までマッチしていることが明らかとなるが、次の一文字は 'C' であり、W 内の次の文字 'D' と不一致となる。前述の場合と同様 "AB" が2回マッチしているので、m = 15 および i = 2 として検索を行う。 m: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDEW: ABCDABDi: 0123456 ここで完全に照合でき、その際の最初の文字の位置は S[15] となる。
※この「この検索アルゴリズムの実施例」の解説は、「クヌース–モリス–プラット法」の解説の一部です。
「この検索アルゴリズムの実施例」を含む「クヌース–モリス–プラット法」の記事については、「クヌース–モリス–プラット法」の概要を参照ください。
- この検索アルゴリズムの実施例のページへのリンク
