|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 法 ： [ほう] 1. (n,n-suf) Act (law: the X Act)
クヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列） Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。このアルゴリズムは1977年、ドナルド・クヌースと Vaughan Pratt および（単独で）J. H. Morris が発明し、3人共同で発表した。 本項目では文字列を表すにあたって、0 からインデックスを開始する配列を用いる。従って（後述の）単語 W 内の文字 'C' は W と表される。==KMP法== ===この検索アルゴリズムの実施例=== 実際にこのアルゴリズムがどのように動作するかを見てみよう。このアルゴリズムの状態は二つの整数 m と i で表される。m はテキスト S 内の文字の位置であり、単語 W にマッチする可能性のある位置でもある。i は、その時点で照合中の W 内の文字の位置を示す。検索開始時点の状態は以下のように表される。m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456 まず、上記の状態で W の先頭と S の先頭から照合していく。この例では4文字目の照合で S が空白、W = 'D' となるため、不一致となる。W 内でそこまでに照合された範囲で 'A' が 0 番目にしかないことから、そこまで照合した S の範囲内に 'A' が出現しないことは明らかである。つまり、S から S までは W とマッチすることはない。そのため、次の照合を単純に S から開始するのではなく、m = 4 および i = 0 として次の照合を開始する。m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456 ここで、 "ABCDAB" までマッチすることがわかるが、W (S) で不一致となる。しかし、前回の不一致とは異なり、"AB" が2回出現していることに注意が必要である。この範囲での2回目の "AB" は W の先頭ともマッチするので、ここでは m = 8 および i = 2 として照合を再開する。これにより S の事前にマッチした文字列の照合を省くだけでなく、W 内の照合済み文字列の照合も省略している。m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456 今回の照合は即座に失敗し、次の照合は m = 11 および i = 0 として再開する。m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456 ここでも "ABCDAB" までマッチしていることが明らかとなるが、次の一文字は 'C' であり、W 内の次の文字 'D' と不一致となる。前述の場合と同様 "AB" が2回マッチしているので、m = 15 および i = 2 として検索を行う。m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456 ここで完全に照合でき、その際の最初の文字の位置は S となる。抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「クヌース–モリス–プラット法」の詳細全文を読む スポンサード リンク
|