カテゴリー:
探索アルゴリズム
閲覧数:337 配信日:2017-02-25 09:22
アルゴリズムの状態
・二つの整数 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 |
・ここで、"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 | 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
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法の違い
文字列の検索
文字列アルゴリズムの学びかた
・終了後→文字列探索