翻訳と辞書
Words near each other
・ クヌルフ
・ クヌース
・ クヌース-モリス-プラット法
・ クヌース–モリス–プラット法
・ クヌースのシャッフル
・ クヌースの矢印
・ クヌースの矢印表記
・ クヌースの矢印記号
・ クヌースの矢印記法
・ クヌース・ベンディックス完備化アルゴリズム
クヌース・モリス・プラット法
・ クヌース記法
・ クヌース賞
・ クヌーズ
・ クヌーズ (デンマーク王子)
・ クヌーズ1世 (デンマーク王)
・ クヌーズ3世 (デンマーク王)
・ クヌーズ5世
・ クヌーズ5世 (デンマーク王)
・ クヌーズオーエ・リスエア


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

クヌース・モリス・プラット法 : ミニ英和和英辞書
クヌース・モリス・プラット法[ほう]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [ちょうおん]
 (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法==

===この検索アルゴリズムの実施例===
実際にこのアルゴリズムがどのように動作するかを見てみよう。このアルゴリズムの状態は二つの整数 mi で表される。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)
ウィキペディアで「クヌース–モリス–プラット法」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.