＠IT
アジャイル/DevOps
Coding Edge
文字列の中から効率良くキーワードを探し出せ：コー...

文字列の中から効率良くキーワードを探し出せ：コーディングに役立つ！アルゴリズムの基本（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 -->