文字列の中から効率良くキーワードを探し出せ：コーディングに役立つ！アルゴリズムの基本（7）（3/4 ページ）

» 2009年02月04日 00時00分公開

[山下寛人，オイシックス株式会社]

前のページへ 1|2|3|4 次のページへ

BM法

　力任せ法、KMP法のどちらのアルゴリズムも、検索ワードの先頭から比較をしていました。逆に、末尾から比較をすることで効率を上げるのがBM法です。BM法も考案した人の名前（Boyer-Moore）の頭文字です。

　末尾の文字が不一致であれば、検索ワード全体としても不一致になります。そこで、次のマッチングでは検索ワードの文字数分全部ずらしてしまってもよさそうです。このように一気にジャンプできるので効率がよさそうです。

　ただし、不一致になったとき、文字列側の文字が検索ワードに含まれる文字だった場合、全部ずらしてはいけません。途中でマッチする可能性があります。

不一致になったとき、文字列側の文字が検索ワードに含まれる文字だった場合、全部ずらしてはいけない

　従って、不一致になったときの文字の種類ごとに、検索ワードを何文字シフトするかをあらかじめ計算しておきます。

　シフト文字数は次のようになります。

検索ワードに含まれる文字の場合（末尾の文字除く）→検索ワードの末尾から見て何番目にあるか
検索ワードに含まれない文字の場合→検索ワードの文字数

　下図に示した例では、'a'=2、'b'=1、それ以外は5になります。シフトした後、文字列のポインタがあった場所の文字と検索ワードの文字が一致することに注目してください。

BM法の実装

　先ほどのプログラムの49行目、「末尾2」というコメントがある行の下に以下のプログラムを追加してください。

<script type="text/javascript">
function BMSkip(str) {
  var skip_offset = new Array();
 
  for (var i = 0; i < str.length-1; i++) {
    skip_offset[str.charCodeAt(i)] = str.length - i - 1;
  }
 
  this.skip = function(text, pos) {
    var offset = skip_offset[text.charCodeAt(pos)];
    return (offset != undefined) ? offset : str.length;
  }
}
 
String.prototype.findBM = function(str) {
  var bm_skip = new BMSkip(str);
  var last = str.length-1;
  for(var pos = last; pos < this.length; pos += bm_skip.skip(this,pos)) {
    var i = pos;
    var j = last;
    while (j >= 0) {
      if (this.charAt(i) != str.charAt(j)) { break; }
      i--;
      j--;
    }
    if(j < 0) { return i+1; }
  }
  return null;
}
function findTextAreaBM(text_id, search_id) {
  var text = getStringById(text_id);
  var search = getStringById(search_id);
  alert(text.findBM(search));
}
</script>
<input type="button" onClick="findTextAreaBM('area1','search');" value="findBM">
<!-- 末尾3 -->

　プログラムを解説します。

2～13行目

文字ごとのシフト文字数を計算する関数です。BMSkipはオブジェクト的に使うようになっています。引数strには検索ワードが入ります。

3行目

シフト文字数を格納する配列を定義しています。

5～7行目

検索ワードのそれぞれの文字について、後ろから何文字目かを計算して入れています。検索ワードの文字に重複がある場合、後から計算したもので上書きされます。つまり、後ろの方の文字が優先されます。

9～12行目

実際の探索を行っているときにシフト文字数を取得する関数です。skip_offsetに値が設定されていればその文字数を返し、なければ検索ワードの文字数を返します。

15～29行目

BM法の文字列探索を行う関数です。

16行目