Rubyで遊ぶよ

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

02:02

• ボイヤー-ムーア文字列検索アルゴリズム - Wikipedia

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

目標

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

文字	シフト
D	0
B	1
A	2
C	4

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

表2

N	パターン	シフト
0	''	1
1	D	3
2	BD	7
3	ABD	7
4	DABD	7
5	CDABD	7
6	BCDABD	7

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
}