Hatena::Grouprubyist

Rubyで遊ぶよ

 | 

2010-06-04

Boyer-Moore 文字列検索アルゴリズムをやってみる

02:02

解説読んでもよくわからなかたので、自分で書いてみる。


目標

ABC ABCDAB ABCDABCDABDE

という文字列 (s とする) を、

ABCDABD

という文字列 (w とする) で split する。

こうなるはず。

ABC ABCDAB ABCD
ABCDABD
E

方針

  1. まず、開始位置を 0 とする。
  2. s の開始位置から w.length-1 だけ右の文字を見る。s の終端に逹っしている場合は終了。
  3. その文字が w の中に含まれていない場合、s の開始位置から w.length-1 文字が w に一致することはないので、開始位置をw.length 文字シフトして 2 に戻る。
  4. その文字が w の最後の文字と一致する場合、そこから逆に見ていって、w の末尾と一致する部分を出来るだけ長く集める。
  5. もし w と完全に一致したら、開始位置を記憶。
  6. w の末尾と部分的に一致したら、表2のシフト数を見る。
  7. 1 または 3 の後、現在の文字は w の中に含まれるはずなので、表1で該当する文字のシフト数を見る。
  8. 4 と 6 のシフト数を比べて、大きなほうだけ開始位置をシフトし、1 に戻る。

表1

文字シフト
D0
B1
A2
C4

これはつまり、各文字が w = 'ABCDABD' の後ろから数えて何文字目に出てくるかということ。


表2

Nパターンシフト
0''1
1D3
2BD7
3ABD7
4DABD7
5CDABD7
6BCDABD7

N=0 が使われることはないはず。

二列目は、w = 'ABCDABD' の中で 'D' が出てくる (そしてその前に 'B' が出てきてない) のは、後ろから数えて3つめだから。

もう一つルールがあって、パターンの文字の終端の部分と w の始端が重なったところがあれば、そこをシフトとすること。

分かりにくいので ANPANMAN の例 を見たほうがいい。


コード

# 準備
s = "ABC ABCDAB ABCDABCDABDE"
w = "ABCDABD"
 
# 表1を作る
table1 = {}
w.split('').reverse.each.with_index {|c, i|
  table1[c] ||= i
}

# 表2を作る
table2 = []
rev = w.split('').reverse
i = 0

while i < rev.length + 1
  j = 0

  while i + j < rev.length
    break if rev[i+j] != rev[j]
    j += 1
  end

  if i + j < rev.length # 途中で break された → 通常ルール
    table2[j] ||= i
  else # パターンの文字の終端の部分と w の始端が重なったところがある
    while j < rev.length
      table2[j] ||= i
      j += 1
    end
  end

  i += 1
end

# 検索
positions = []

i = 0
while i < s.length - w.length
  j = w.length - 1
  while w[j] == s[i + j]
    if (j == 0)
      positions.push(i)
      break
    end
    j -= 1
  end

  i += [ table2[w.length - j - 1], table1[ s[i + j] ] || w.length ].max
end

# split
positions.push(s.length).inject(0) {|a, b|
  puts s.slice!(0, b-a)
  puts s.slice!(0, w.length)
  b
}

結果。

ABC ABCDAB ABCD
ABCDABD
E


かなり面倒だけど、実は表2は使わなくてもあまり速さは落ちないらしい。

その場合はこれだけ。

s = "ABC ABCDAB ABCDABCDABDE"
w = "ABCDABD"
 
table1 = {}
w.split('').reverse.each.with_index {|c, i|
  table1[c] ||= i
}

positions = []

i = 0
while i < s.length - w.length
  j = w.length - 1
  while w[j] == s[i + j]
    if (j == 0)
      positions.push(i)
      break
    end
    j -= 1
  end

  i += table1[ s[i + j] ] || w.length
end

positions.push(s.length).inject(0) {|a, b|
  puts s.slice!(0, b-a)
  puts s.slice!(0, w.length)
  b
}

ShuichiroShuichiro2013/09/19 10:34It's posts like this that make surfing so much pluesare

RaviRavi2013/09/20 10:45Thanks for being on point and on <a href="http://rklnciy.com">tagert!</a>

KevinKevin2013/09/20 23:09Most help articles on the web are inaccurate or incnreheot. Not this! http://klpbrq.com [url=http://tgmlhxrj.com]tgmlhxrj[/url] [link=http://hvxxikusr.com]hvxxikusr[/link]

OlgaOlga2013/09/21 05:48This does look <a href="http://mnkmrsbmpro.com">prinmsoig.</a> I'll keep coming back for more.

BibaBiba2013/09/23 15:49I have been so bewiederld in the past but now it all makes sense! http://qtlckrgdvd.com [url=http://hhazfkzkh.com]hhazfkzkh[/url] [link=http://fwlpongdyo.com]fwlpongdyo[/link]

トラックバック - http://rubyist.g.hatena.ne.jp/edvakf/20100604
 |