クヌース–モリス–プラット法

アルゴリズム探索アルゴリズム

クヌース–モリス–プラット法とは?

 状態:-  閲覧数:1,340  投稿日:2017-02-22  更新日:2017-03-28  
文字列検索アルゴリズムの一種
・検索ワードのどの位置で不一致になったかを把握することによって、どこから比較再開すればよいか予め決定するアルゴリズム

特徴
・無駄な比較を軽減するため、「パターン照合の再開位置を決定するテーブル」を予め作成してから検索を行う
・予め「テーブル作成」した上で、「テーブルを参照した探索」を行う
※テーブル作成方法は色々ある

正式名称
・Knuth–Morris–Pratt algorithm
・略記して、KMP法とも呼ばれる

1977年
・「D.E.Knuth(ドナルド・クヌース)と Vaughan.R.Pratt 」及び「(単独で)J. H. Morris」が発明し、3人共同で発表
・3人(Knuth,Morris, Pratt)の名前をとってKMP法 と呼ばれる

基本的な考え方 / 理論的には?

 閲覧数:240 投稿日:2016-11-09 更新日:2017-03-25 

基本的な考え方


テキスト(探索対象文字列)と パターン(探索文字列)
・「テキスト」から「単語で指定されたパターン」を探すにあたり、「不一致となった位置」と「単語自身の情報から次に照合を試すべき位置」を決定することで検索を効率化する

前処理
・「パターンに含まれる各文字」について、「その文字で不一 致になった際パターンをどれだけずらせばよいか」を調べて表にしておく

探索を行う
・上記表をもとにパターンをずらしていく

計算量
・O(n)


理論的には?


力任せ法よりも高速なアルゴリズム
・テキストとパターンの照合において後戻りは発生しないため、力任せ法(Brute Force Search)よりも高速なアルゴリズムとなる


現実的には?


問題点
・テーブルを作成するための前処理が複雑
・アルゴリズムが複雑な分だけオーバーヘッドが大きくなってしまう

短い文字列の場合
・結果的に力任せ法の方が効率が良いケースもある

考え方例1

 閲覧数:237 投稿日:2016-11-09 更新日:2017-03-14 

例1


6文字パターンREDRED」を探索


1文字目が不一致


スタート
テキスト
パターン R E D R E D
1文字目が不一致の場合
・「テキスト」位置情報を1つ進める
・「パターン」を1つ右へずらす
・「パターン」先頭から比較
テキスト
パターン - R E D R E D


2文字目が不一致


スタート
・この時点では「デキスト」と「パターン」の1文字目が一致している
テキスト R
パターン R E D R E D
2文字目が不一致の場合
・「パターン」を1つ右へずらす
・「パターン」先頭から比較
※「テキスト」を指すポインタ位置は 変わらないことに注意
テキスト R
パターン - R E D R E D


3文字目が不一致


スタート
・この時点では「デキスト」と「パターン」の1〜2文字目が一致している
テキスト R E
パターン R E D R E D
3文字目が不一致の場合
・「パターン」を2つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」先頭から比較
テキスト R E
パターン - - R E D R E D


4文字目が不一致


スタート
・この時点では「デキスト」と「パターン」の1〜3文字目が一致している
テキスト R E D
パターン R E D R E D
4文字目が不一致の場合
・「パターン」を3つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」先頭から比較
テキスト R E D
パターン - - - R E D R E D


5文字目が不一致


スタート
・この時点では「テキスト」と「パターン」の1〜4文字目が一致している
・テキストの1文字目と4文字目は同じ文字Rになっている
テキスト R E D R
パターン R E D R E D
パターンを4つずらすと?
・テキスト4文字目のRを 見逃してしまう
テキスト R E D R
パターン - - - - R E D R E
5文字目が不一致の場合
・「パターン」を3つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」2文字目から比較を続行
テキスト R E D R
パターン - - - R E D R E D


6文字目が不一致


スタート
・この時点では「デキスト」と「パターン」の1〜5文字目が一致している
テキスト R E D R E
パターン R E D R E D
6文字目が不一致の場合
・「パターン」を3つずらす(パターンを1文字ずらしても、1文字目が一致しないことは明らかなため)
・「パターン」3文字目から比較
テキスト R E D R E
パターン - - - R E D R E D



考え方


パターンの i 文字目で失敗した
・0 から i - 1 文字はテキストとパターンが一致している 

ポイント
・パターンの i 文字目で失敗した時に、何文字ずらして再開するか

例1の場合
・1文字目で失敗 => ずらし数 next[0] = 1
・2文字目で失敗 => ずらし数 next[1] = 1
・3文字目で失敗 => ずらし数 next[2] = 2
・4文字目で失敗 => ずらし数 next[3] = 3
・5文字目で失敗 => ずらし数 next[4] = 3
・6文字目で失敗 => ずらし数 next[5] = 3


計算量
・O(n)



文字列検索(直感的な文字列検索とKMP法)

考え方例2

 閲覧数:219 投稿日:2017-02-25 更新日:2017-03-27 
アルゴリズムの状態
・二つの整数 m と i で表される

m
・テキスト S 内の文字の位置
・単語 W にマッチする可能性のある位置

i
・その時点で照合中の W 内の文字の位置

検索開始時点の状態
・W の先頭と S の先頭から照合していく
・この例では4文字目の照合で S[3] が-、W[3] = 'R' となるため、不一致となる
・W 内でそこまでに照合された範囲で 'R' が 0 番目にしかないことから、そこまで照合した S の範囲内に 'R' が出現しないことは明らか
・具体的には、S[1] から S[3] までは W[0] とマッチすることはない
・そのため、次の照合を単純に S[1] から開始するのではなく、m = 4 および i = 0 として次の照合を開始する
m 0 1 2 3 4 5 6 7 8 9 0
S B L U - B L U E B L -
W B L U E B L E
i 0 1 2 3 4 5 6
m = 4 および i = 0 として次の照合を開始
・ここで、"BLUEBL" までマッチすることがわかる
・W[6] (S[10]) で不一致となる。但し、前回の不一致とは異なり、"BL" が2回出現していることに注意が必要
・この範囲での2回目の "BL" は W の先頭ともマッチするので、ここでは m = 8 および i = 2 として照合を再開する
m 0 1 2 3 4 5 6 7 8 9 0
S B L U - B L U E B L -
W - - - - B L U E B L E
i - - - - 0 1 2 3 4 5 6
m = 8 および i = 2 として照合を再開
m 0 1 2 3 4 5 6 7 8 9 0
S B L U - B L U E B L -
W - - - - B L U E B L E
i - - - - 0 1 2 3 4 5 6
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456





コーディングに役立つ! アルゴリズムの基本(7):文字列の中から効率良くキーワードを探し出せ
文字列検索のアルゴリズム①(KMP法)
http://yamweb.comp.ae.keio.ac.jp/japanese/2011-A%E8%AB%96/9before%EF%BC%88%E6%96%87%E5%AD%97%E5%88%97%E6%8E%A2%E7%B4%A2+%E3%83%90%E3%83%83%E3%82%AF%E3%83%88%E3%83%A9%E3%83%83%E3%82%AF).pdf
文字列探索のKMP法を考えた人すごいと思う。



文字列探索

単純法、KMP法、BM法の違い
文字列の検索


文字列アルゴリズムの学びかた


・終了後→文字列探索


文字列探索

Morris-Pratt algorithm

コメント投稿(ログインが必要)



週間人気ページランキング / 6-24 → 6-30
順位 ページタイトル抜粋 アクセス数
1 Flash Video | コンテナフォーマット | プログラミング用語 306
2 curl | HTTPクライアント(ネットワーク) | プログラミング用語 286
3 ルーター | ネットワーク | プログラミング用語 281
3 ユースケース | 開発 | プログラミング用語 281
4 ベクトル | 数学 | プログラミング用語 236
5 デーモン | Linux | プログラミング用語 227
6 正規表現 | プログラミング | プログラミング用語 194
7 YouTube | API | プログラミング用語 171
8 チェックアウト | バージョン管理システム(開発) | プログラミング用語 117
9 分かち書き | 形態素解析 | プログラミング用語 63
10 Linux | プログラミング用語 57
11 リバースエンジニアリング | 開発 | プログラミング用語 54
12 ネットワークアドレス | ネットワーク | プログラミング用語 50
13 PowerShell | スクリプト | プログラミング用語 44
14 クローラ | 検索エンジン | プログラミング用語 31
14 可搬性 | プログラミング | プログラミング用語 31
15 Subversion | バージョン管理システム(開発) | プログラミング用語 27
16 アンチパターン | プログラミング | プログラミング用語 11
17 プログラミング用語 9
18 deflate | ネットワーク | プログラミング用語 8
2022/7/1 1:01 更新