【アルゴリズム(JS実装)】Boyer Moore Algorithm

　どうも、わくばです！

最近は周りも国試を意識し始めて、少し焦りを感じてきました(笑)

Webサービスの開発もありますし、新入生も入ってきたし、なんか気持ち的にもかなり追い込まれてました（笑）

うまく両立していけるようにしないとです。

近況報告はこの辺にして、今回はBoyer Moore法を記事にしてみます。

まず言葉の整理をしておくと、テキストというのは検索対象の文字列、パターンは検索したい文字列を指します。例えばABCDEFGの中からDEFの文字列を検索する場合、ABCDEFGをテキスト、DEFをパターンと呼ぶことにします。

このアルゴリズムを理解する上でポイントとなるのは、ずらしテーブル(以下のコードにおいてはbadCharHeuristic関数が作成する配列のこと)の理解です。ずらしテーブルというのは簡単に言うと、テキストとパターンを比較していくなかでミスマッチが生じたとき、どのくらいシフトさせるかを定めた配列のことです。

ずらしテーブルの意味については以下の動画が非常にわかりやすいのでぜひ参考にしてみてください。

youtu.be

以下がずらしテーブルを作成するコードです。

const badCharHeuristic = string => {
  /*
  今回はアルファベットしか使わないので
  26文字ぶんの配列にしています。
  */
  const result = Array(26).fill(-1);
  const strArr = string.split('')
  for (let i = 0; i < strArr.length; i++) {
    /*
    -97はaの文字コードを0スタートにするため
    result配列のアルファベットの位置に、
    pattern文字列におけるindexを入れる
    たとえばABGFというpattern文字列の場合は
    [0, 1, -1, -1, -1, 3 , 2, -1, -1, ...-1が続く]
    となる
    */
    result[strArr[i].charCodeAt() - 97] = i 
  }
  return result;
}

console.log('avdgksg', badCharHeuristic('avdgksg'))

/*
avdgksg [
   0, -1, -1,  2, -1, -1,  6, -1,
  -1, -1,  4, -1, -1, -1, -1, -1,
  -1, -1,  5, -1, -1,  1, -1, -1,
  -1, -1
]
*/

同じ文字が出てきた場合はあとに出現した文字の位置をもとにテーブルを作成しています。このavdgksgパターンのずらしテーブルが意味するところは、たとえば文字sでミスマッチが生じた場合はavdgksgのindex5の位置まで戻すということです。

次に実際に検索するコードです。

const boyerMooreSearch = (text, pattern) => {

  const result = [];
  const tl = text.length,
        pl = pattern.length;
  
  //ずらしテーブル作成
  const badChar = badCharHeuristic(pattern, pl);

  let shift = 0;
  while (shift <= tl - pl) {
    //tailはpattern文字列の後ろから比較していくときのカーソル
    tail = pl - 1;

    /*
    textとpatternをpatternの末尾から比較していって
    ミスマッチが生じたらずらしターブルを参照してshiftを動かす
    全部マッチしたらtailは0未満まで行く
    */
    while ( tail >= 0 && pattern[tail] === text[shift + tail]) {
      tail --;
    }

    if (tail < 0) {
      /*
      tailが0未満までいってたら全部マッチなのでresultに追加して
      patternをまるごとずらす
      */
      result.push(shift);
      shift += pl
    } else {
      //途中でミスマッチがでたらずらしテーブルに則してずらす。
      shift += Math.max(1, tail - badChar[text[shift + tail].charCodeAt() - 97]); 
    } 
  } 
  return result;
}

console.log(boyerMooreSearch('abcddaabcdbbdcavbcdddbaccabcdcbddc', 'abcd'))

//[ 0, 6, 25 ]

最良のケースの時間計算量は\(O(テキストの長さ/パターンの長さ)\)になります。最良であればパターン文字列ぶんまるまるずらすからですね。

今回は以上です。誤植は質問等ありましたらお気軽にコメントください。では。