![ラビンカープ法
● 例[再])
長い数字列(文)から、ある数字列(パターン)を見つ
けることを考える
パターン: 358 H(p)=55
p
文: 11235813...
t=112,H(t)=9
t
● パターンを格納する整数をp=358とする
● 文中の今見ている範囲(下線部)を格納する整数を
t(最初t=112)とする
● ハッシュ関数をH(x)=x % 101とする](https://image.slidesharecdn.com/20130306-130306004214-phpapp02/85/-51-320.jpg)
![ラビンカープ法
● 例[再])
長い数字列(文)から、ある数字列(パターン)を見つ
けることを考える
パターン: 358 H(p)=55
p
文: 11235813...
t=123,H(t)=22
t
● パターンを格納する整数をp=358とする
● 文中の今見ている範囲(下線部)を格納する整数を
t(最初t=112)とする
● ハッシュ関数をH(x)=x % 101とする](https://image.slidesharecdn.com/20130306-130306004214-phpapp02/85/-52-320.jpg)
![ラビンカープ法
● 例[再])
長い数字列(文)から、ある数字列(パターン)を見つ
けることを考える
パターン: 358 H(p)=55
p
文: 11235813...
t=235,H(t)=33
t
● パターンを格納する整数をp=358とする
● 文中の今見ている範囲(下線部)を格納する整数を
t(最初t=112)とする
● ハッシュ関数をH(x)=x % 101とする](https://image.slidesharecdn.com/20130306-130306004214-phpapp02/85/-53-320.jpg)
![ラビンカープ法
● 例[再])
長い数字列(文)から、ある数字列(パターン)を見つ
けることを考える
H(p)=55
パターン: 358 t=358,H(t)=55
p
文: 11235813... H(p)=H(t)となり一致!
t
● パターンを格納する整数をp=358とする
● 文中の今見ている範囲(下線部)を格納する整数を
t(最初t=112)とする
● ハッシュ関数をH(x)=x % 101とする](https://image.slidesharecdn.com/20130306-130306004214-phpapp02/85/-54-320.jpg)
More Related Content
What's hot (20)
Recently uploaded (8)
文字列検索のいろいろ
- 1. 2013-03-06 大阪府立大学工業高等専門学校プログラミング研究会 部内勉強会発表 文字列検索アルゴリズム @kyuridenamida
- 2. 文字列検索って？ ● パターンと呼ばれる文字列が 文中のどこに存在するかを見つける手法 ←パターン 文 ※某有名パクツイボット
- 4. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑
- 5. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑ 最初の文字で不一致した。
- 6. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑
- 7. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑
- 8. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑
- 9. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑
- 10. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑4文字目で不一致だった。
- 11. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑
- 12. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑
- 13. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑
- 14. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑
- 15. Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑ 一致した！
- 16. Bruteforce(力まかせ)の計算量 ● 文字列の長さをNをパターンの長さをLとして、 – 始点はN箇所ある – パターンの比較はそれぞれの始点について最大L回 ∴最悪計算量はO(NL) (※最悪でN×L回の比較が実行されると解釈してよい。) ● これは使い物にならないくらい遅い！(?)
- 17. 手法②． KMP法
- 18. KMP法 ● クヌースさん,モリスさん,プラットさんが発表した ● パターンのどの位置で不一致したかでずらす量を 決める 例) パターン : ababc a b a b c 文 : abcadababc 何文字目で失敗した？ 始点ずらす量 次何文字目から見るか 1 +1 1 2 +2 1 3 +3 1 4 +2 2 5 +2 3 a b c a d a b a b a b c
- 19. KMP法 ● クヌースさん,モリスさん,プラットさんが発表した ● パターンのどの位置で不一致したかでずらす量を 決める 例) パターン : ababc 文 : abcadababc 何文字目で失敗した？ 始点ずらす量 次何文字目から見るか 1 +1 1 2 +2 1 3 +3 1 4 +2 2 5 +2 3 a b c a d a b a b a b c a b a b c ↑
- 20. KMP法 ● クヌースさん,モリスさん,プラットさんが発表した ● パターンのどの位置で不一致したかでずらす量を 決める 例) パターン : ababc 文 : abcadababc 何文字目で失敗した？ 始点ずらす量 次何文字目から見るか 1 +1 1 2 +2 1 3 +3 1 4 +2 2 5 +2 3 a b c a d a b a b a b c a b a b c ↑ 3文字目で不一致
- 21. KMP法 ● クヌースさん,モリスさん,プラットさんが発表した ● パターンのどの位置で不一致したかでずらす量を 決める 例) パターン : ababc 文 : abcadababc 何文字目で失敗した？ 始点ずらす量 次何文字目から見るか 1 +1 1 2 +2 1 3 +3 1 4 +2 2 5 +2 3 a b c a d a b a b a b c a b a b c ↑
- 22. KMP法 ● クヌースさん,モリスさん,プラットさんが発表した ● パターンのどの位置で不一致したかでずらす量を 決める 例) パターン : ababc 文 : abcadababc 何文字目で失敗した？ 始点ずらす量 次何文字目から見るか 1 +1 1 2 +2 1 3 +3 1 4 +2 2 5 +2 3 a b c a d a b a b a b c a b a b c ↑ 2文字目で不一致
- 23. KMP法 ● クヌースさん,モリスさん,プラットさんが発表した ● パターンのどの位置で不一致したかでずらす量を 決める 例) パターン : ababc 文 : abcadababc 何文字目で失敗した？ 始点ずらす量 次何文字目から見るか 1 +1 1 2 +2 1 3 +3 1 4 +2 2 5 +2 3 a b c a d a b a b a b c a b a b c ↑
- 24. KMP法 ● クヌースさん,モリスさん,プラットさんが発表した ● パターンのどの位置で不一致したかでずらす量を 決める 例) パターン : ababc 文 : abcadababc 何文字目で失敗した？ 始点ずらす量 次何文字目から見るか 1 +1 1 2 +2 1 3 +3 1 4 +2 2 5 +2 3 a b c a d a b a b a b c a b a b c ↑ 5文字目で不一致
- 25. KMP法 ● クヌースさん,モリスさん,プラットさんが発表した ● パターンのどの位置で不一致したかでずらす量を 決める 例) パターン : ababc 文 : abcadababc 何文字目で失敗した？ 始点ずらす量 次何文字目から見るか 1 +1 1 2 +2 1 3 +3 1 4 +2 2 5 +2 3 a b c a d a b a b a b c a b a b c ↑
- 26. KMP法 ● クヌースさん,モリスさん,プラットさんが発表した ● パターンのどの位置で不一致したかでずらす量を 決める 例) パターン : ababc 文 : abcadababc 何文字目で失敗した？ 始点ずらす量 次何文字目から見るか 1 +1 1 2 +2 1 3 +3 1 4 +2 2 5 +2 3 a b c a d a b a b a b c a b a b c ↑ 一致した～
- 27. KMP法の特徴?計算量 ● 矢印の位置が後戻りしない！ ● 最悪計算量は？ – 後戻りしない – 一回の操作で必ず1つ矢印が進む よって、比較はO(N)回 – 表の構築はO(L)で可能。 全体で O(N+L)
- 28. 力まかせ法との比较 ●力まかせ法は、 最悪計算量O(NL) ● KMP法は、 ● 最悪計算量O(N+L) これは最悪計算量の議論である。
- 29. 実は.... ● 実用上はＫＭＰ法より、力任せ法の方が速い！ – なぜならば、力まかせ法が遅いのは恣意的なケース ● パターン: aaaaa 文:aaaaaaaaaaaaaaaaaaaa... – 自然言語の場合、 ほとんど最初の数文字で不一致する。 – 使われている文字の種類が多ければ不一致率高い – つまり、力まかせ法は実用上で計算量O(N)として扱える – しかも実装がシンプルなので定数倍が少ない。
- 30. 実は.... ● KMPは実用上遅い – 最良の場合でも、必ずO(N)回は比較をする – 複雑な処理をしているため、定数倍が大きい ● 理論上優れているということが重要 – 後戻りがしないところが良い
- 31. そこで ● 理論上優れていて、実用上も優れているアルゴリ ズム... それがあってもおかしくない！
- 32. あるんです！
- 33. 手法③． BM法
- 34. BM法 ● ボイヤーさん,ムーアさんが開発した ● パターン比較時、後ろの文字から比較していく ● 失敗した文字種類に応じてずらす量決める 例) a b a b c パターン : ababc 文 : abcacdbabc 不一致したときの文中の文字 着目点をずらす量 次何文字目から見るか a Max(+2,一致文字数+1) 5 b Max(+1,一致文字数+1) 5 c +5 5 それ以外 +5 5 a b c a c d b a b a b c a b a b c ↑
- 35. BM法 ● ボイヤーさん,ムーアさんが開発した ● パターン比較時、後ろの文字から比較していく ● 失敗した文字種類に応じてずらす量決める 例) a b a b c パターン : ababc 文 : abcacdbabc 不一致したときの文中の文字 着目点をずらす量 次何文字目から見るか a Max(+2,一致文字数+1) 5 b Max(+1,一致文字数+1) 5 c +5 5 それ以外 +5 5 a b c a c d b a b a b c a b a b c ↑ 'a'で不一致, 1文字一致した後失敗した
- 36. BM法 ● ボイヤーさん,ムーアさんが開発した ● パターン比較時、後ろの文字から比較していく ● 失敗した文字種類に応じてずらす量決める 例) a b a b c パターン : ababc 文 : abcacdbabc 不一致したときの文中の文字 着目点をずらす量 次何文字目から見るか a Max(+2,一致文字数+1) 5 b Max(+1,一致文字数+1) 5 c +5 5 それ以外 +5 5 a b c a c d b a b a b c a b a b c ↑ 着目点(↑)を2文字ずらした
- 37. BM法 ● ボイヤーさん,ムーアさんが開発した ● パターン比較時、後ろの文字から比較していく ● 失敗した文字種類に応じてずらす量決める 例) a b a b c パターン : ababc 文 : abcacdbabc 不一致したときの文中の文字 着目点をずらす量 次何文字目から見るか a Max(+2,一致文字数+1) 5 b Max(+1,一致文字数+1) 5 c +5 5 それ以外 +5 5 a b c a c d b a b a b c a b a b c ↑ 'd'で不一致,5文字ずらす
- 38. BM法 ● ボイヤーさん,ムーアさんが開発した ● パターン比較時、後ろの文字から比較していく ● 失敗した文字種類に応じてずらす量決める 例) a b a b c パターン : ababc 文 : abcacdbabc 不一致したときの文中の文字 着目点をずらす量 次何文字目から見るか a Max(+2,一致文字数+1) 5 b Max(+1,一致文字数+1) 5 c +5 5 それ以外 +5 5 a b c a c a b a b a b c a b a b c ↑
- 39. BM法 ● ボイヤーさん,ムーアさんが開発した ● パターン比較時、後ろの文字から比較していく ● 失敗した文字種類に応じてずらす量決める 例) a b a b c パターン : ababc 文 : abcacdbabc 不一致したときの文中の文字 着目点をずらす量 次何文字目から見るか a Max(+2,一致文字数+1) 5 b Max(+1,一致文字数+1) 5 c +5 5 それ以外 +5 5 a b c a c a b a b a b c a b a b c ↑ 'b'で不一致,1文字ずらす
- 40. BM法 ● ボイヤーさん,ムーアさんが開発した ● パターン比較時、後ろの文字から比較していく ● 失敗した文字種類に応じてずらす量決める 例) a b a b c パターン : ababc 文 : abcacdbabc 不一致したときの文中の文字 着目点をずらす量 次何文字目から見るか a Max(+2,一致文字数+1) 5 b Max(+1,一致文字数+1) 5 c +5 5 それ以外 +5 5 a b c a c a b a b a b c a b a b c ↑
- 41. BM法 ● ボイヤーさん,ムーアさんが開発した ● パターン比較時、後ろの文字から比較していく ● 失敗した文字種類に応じてずらす量決める 例) a b a b c パターン : ababc 文 : abcacdbabc 不一致したときの文中の文字 着目点をずらす量 次何文字目から見るか a Max(+2,一致文字数+1) 5 b Max(+1,一致文字数+1) 5 c +5 5 それ以外 +5 5 a b c a c a b a b a b c a b a b c ↑ 一致した！
- 42. BM法の特徴?計算量 ● KMP法よりテーブルの構築がシンプル ● 一回の比較で、最大でパターンの長さLだけ 比較省略可能 ● 計算量は？ – 実用上はO(N/L)とかいう最強 (文字の種類が多いことが条件で、ビット列(0と1)とかだとあ んまり意味ない) – どれか1つ一致を見つけるだけでよいなら最悪O(N+L) – ただし、一致する文字列が何度もある場合最悪O(NL) はやい！
- 43. 手法④． ラビン?カープ法
- 44. ラビンカープ法 ● ラビンさん?カープさんが開発した ● ハッシュを用いた探索アルゴリズム ● ハッシュ関数は、n進数法っぽいことをするとよい ● 応用が広い ハッシュを用いない簡単化された例) 数字列(文)から、ある数字列(パターン)を見つける ことを考える パターン: 358 文: 11235813...
- 45. ラビンカープ法 ● 例) 長い数字列(文)から、ある数字列(パターン)を見つ けることを考える パターン: 358 p 文: 11235813... t ● パターンを格納する整数をp=358とする ● 文中の今見ている範囲(下線部)を格納する整数を t(最初t=112)とする
- 46. ラビンカープ法 ● 例) 長い数字列(文)から、ある数字列(パターン)を見つ けることを考える パターン: 358 p t=112 → t' = 123 = (t - 1 * 100) * 10 + 3 文: 11235813... t ● パターンを格納する整数をp=358とする ● 文中の今見ている範囲(下線部)を格納する整数を t(最初t=112)とする
- 47. ラビンカープ法 ● 例) 長い数字列(文)から、ある数字列(パターン)を見つ けることを考える パターン: 358 p t=123 → t' = 235 = (t - 1 * 100) * 10 + 5 文: 11235813... t ● パターンを格納する整数をp=358とする ● 文中の今見ている範囲(下線部)を格納する整数を t(最初t=112)とする
- 48. ラビンカープ法 ● 例) 長い数字列(文)から、ある数字列(パターン)を見つ けることを考える パターン: 358 t=235 → t' = 358 = (t - 2 * 100) * 10 + 8 p 文: 11235813... p=tとなり一致! t ● パターンを格納する整数をp=358とする ● 文中の今見ている範囲(下線部)を格納する整数を t(最初t=112)とする
- 49. ラビンカープ法 ● 64bitまでの整数演算はO(1) ● スライドさせる操作は1回にO(1) ● よって、全体では、 O(N) ● ただし、これは64bit整数の範囲でのみ成り立つ
- 50. ラビンカープ法 重要! 64bitまでの整数演算はO(1) ● 大きい数字になりそうなとき、 適当な値で余りを取ることを考える ● 余りを取った値が一様に分散している場合、 衝突する確率は天文学的に小さい ● 2つの値が一致している? 余りを取った値も一致 (逆が偶然成り立つ確率は超小さい) ● これを利用してみよう。
- 51. ラビンカープ法 ● 例[再]) 長い数字列(文)から、ある数字列(パターン)を見つ けることを考える パターン: 358 H(p)=55 p 文: 11235813... t=112,H(t)=9 t ● パターンを格納する整数をp=358とする ● 文中の今見ている範囲(下線部)を格納する整数を t(最初t=112)とする ● ハッシュ関数をH(x)=x % 101とする
- 52. ラビンカープ法 ● 例[再]) 長い数字列(文)から、ある数字列(パターン)を見つ けることを考える パターン: 358 H(p)=55 p 文: 11235813... t=123,H(t)=22 t ● パターンを格納する整数をp=358とする ● 文中の今見ている範囲(下線部)を格納する整数を t(最初t=112)とする ● ハッシュ関数をH(x)=x % 101とする
- 53. ラビンカープ法 ● 例[再]) 長い数字列(文)から、ある数字列(パターン)を見つ けることを考える パターン: 358 H(p)=55 p 文: 11235813... t=235,H(t)=33 t ● パターンを格納する整数をp=358とする ● 文中の今見ている範囲(下線部)を格納する整数を t(最初t=112)とする ● ハッシュ関数をH(x)=x % 101とする
- 54. ラビンカープ法 ● 例[再]) 長い数字列(文)から、ある数字列(パターン)を見つ けることを考える H(p)=55 パターン: 358 t=358,H(t)=55 p 文: 11235813... H(p)=H(t)となり一致! t ● パターンを格納する整数をp=358とする ● 文中の今見ている範囲(下線部)を格納する整数を t(最初t=112)とする ● ハッシュ関数をH(x)=x % 101とする
- 55. ラビンカープ法 ● これを文字列比較へ応用しよう ● 10進数 : 0-9までの10文字を使った位取り記数法 ● アルファベットを含めた、 もっと大きい257進数とかでも同じことができそう！ (基数は文字数よりでっかい素数ならなんでもよい) ● アスキーコードをそのまま値に使うとよい ' ' = 32 , '0' = 48 , 'A' = 65 , 'a' = 97 , etc... ● 実際に一致している保障がないと困る場合、 ハッシュ値一致したときだけ力まかせに確認
- 56. ラビンカープ法の特徴 ● 連想配列(平衡二分木)と併用すると、 “長さが同じパターンの数”がM個のとき、 O(N log M)で複数パターンの検索が可能！ これはレポートコピペ検出とかに応用できる。 ● 二次平面上の二次元パターンのマッチングにも応 用できる。 ● 恣意的に衝突を発生させるのはほぼ不可能なた め、最悪ケースとか考えなくて良い。
- 58. SuffixArray ● アルゴリズム？ ● とにかく、なんかすごい ● ある位置から接尾までの部分文字列をソートしたも のを考える ex) 文: ababa ソートしたあと – “ababa”(0) – “a”(4) – “baba”(1) – “aba”(2) – “aba”(2) – “ababa”(0) – “ba”(3) – “ba”(3) – “a”(4) – “baba”(1)
- 59. SuffixArray ● パターン”ab”を探すことを考える ● ソート済なので、二分探索でabが出現する位置が 分かる。いくつ出現するかもうまく処理をすると分か る。 ソートしたあと – “a”(4) – “aba”(2) – “ababa”(0) – “ba”(3) – “baba”(1)
- 60. SuffixArrayを用いた検索の計算量 ● 文の長さをNとして、前処理は、 – N個の文字列をソートする比較回数はO(N log N) – 一回比較するのにだいたいO(N) – O(N^2 log N) ● 爆遅！しかし、比較を巧みに行うと、 – O(N log N) これは現実的な速度。 ● 長さLのパターン検索は、 – 一回の比較O(L) – 二分探索なので、log N回行う – O( L log N ) ← パターン長が小さければ超はやい！
- 62. Aho-Corasick法 ● エイホさんとコラシックさんが開発しました ● なんとなくしか知らない。複数パターン検索にかな り強力らしい。 ● 巧みだけど、実装もそんなに大変じゃないらしい。 ● 名前がよくネタにされるので取り扱ってみました。