テクノロジー編26: アルゴリズム

文字列の中から特定のパターンが出現するか、あるいはどこに出現するかを調べる問題。

ここでは、探す元の文字列を「テキスト T」、探すパターンを「パターン P」と呼び、それぞれの文字列の長さを n, m とする。

文字列の先頭から順にパターンと比較していく方法。
もし一致しなければ、次の文字に移動して再度比較をおこなう。
O(nm)

for (int i = 0; i <= n - m; i++) {
  boolean found = true;
  for (int j = 0; j < m; j++) {
    if (T.charAt(i + j) != P.charAt(j)) {
      found = false;
      break;
    }
  }
  if (found) {
    System.out.println("パターンが見つかりました: " + i);
  }
}

パターンのハッシュ値を計算し、テキストの部分文字列のハッシュ値と比較することで、パターンの出現位置を特定する。
文字列の比較をハッシュ値の比較に置き換えることで、計算量を削減している。
ハッシュの衝突が発生した場合は実際に文字列を比較する必要がある。

// ハッシュを計算する関数
int hash(String s) { ... }

for (int i = 0; i <= n - m; i++) {
  if (hash(T.substring(i, i + m)) == hash(P)) {
    // ハッシュが一致した場合、実際に文字列を比較する
    boolean found = true;
    for (int j = 0; j < m; j++) {
      if (T.charAt(i + j) != P.charAt(j)) {
        found = false;
        break;
      }
    }
    if (found) {
      System.out.println("パターンが見つかりました: " + i);
    }
  }
}

上記のコードのように、毎回部分文字列からハッシュを計算すると計算量が O(n^2) 程度になる。
ローリングハッシュという手法を用いると、衝突が発生しない場合、計算量を O(n + m) に抑えることができる。

パターンの部分一致を利用して、テキストの比較を効率化するアルゴリズム。
クヌース、モリス、プラットによって提案された。
計算量は O(n + m)。

まずパターンの部分一致テーブルを作成する。
この値は、パターンの先頭からの部分文字列と、パターンの i-1 番目までの部分文字列がどれだけ一致しているかを示す。

// 部分一致テーブルの作成
int[] table = new int[m + 1];
// table[0], table[1] は固定
table[0] = -1; table[1] = 0;
int table_idx = 2;  // テーブルのインデックス
int pat_idx = 0;  // パターンのインデックス
while (table_idx <= m) {
  // 一致部分を伸ばせる
  if (P.charAt(table_idx - 1) == P.charAt(pat_idx)) {
    table[table_idx] = pat_idx + 1;
    table_idx++; pat_idx++;
  }
  // 伸ばせないが、前の部分一致を利用できる
  else if (pat_idx > 0) {
    pat_idx = table[pat_idx];
  }
  // それ以外
  else {
    table[table_idx] = 0;
    table_idx++;
  }
}

int txt_idx = 0;  // テキストのインデックス
pat_idx = 0;  // パターンのインデックス
while (txt_idx + pat_idx < n) {
  if (P.charAt(pat_idx) == T.charAt(txt_idx + pat_idx)) {
    pat_idx++;
    if (pat_idx == m) {
      System.out.println("パターンが見つかりました: " + txt_idx);
      txt_idx += pat_idx - table[pat_idx];
      if (pat_idx > 0) {
        pat_idx = table[pat_idx];
      }
    }
  }
  else {
    txt_idx += pat_idx - table[pat_idx];
    if (pat_idx > 0) {
      pat_idx = table[pat_idx];
    }
  }
}

パターンの後ろから前に向かって比較をおこなうアルゴリズム。
特に、テキストが長くパターンが短い場合に有効。
不一致文字規則と一致接尾辞規則という 2 つの規則を用いて、パターンをずらす量を決定する。

不一致文字規則: 文字ごとにどれだけずらすべきか決定する規則。
一致接尾辞規則: パターンの後ろから前にチェックしていくとき、どのくらいずらせば、すでにチェックした部分とピッタリ重なるかを決定する規則。

// 不一致文字規則のテーブルを作成
int[] badChar = new int[256];  // ASCII の文字数
for (int i = 0; i < 256; i++) {
  badChar[i] = m;  // デフォルトはパターンの長さ
}
for (int i = 0; i < m - 1; i++) {
  badChar[P.charAt(i)] = m - 1 - i;  // 最後の出現位置を記録
}

// 一致接尾辞規則のテーブルを作成
int[] goodSuffix = new int[m + 1];
int lastPrefixPosition = m;
for (int i = m - 1; i >= 0; i--) {
  // P[i+1 ...] と P の接頭辞が一致するか
  boolean isPrefix = true;
  for (int j = 0; j < m - i - 1; j++) {
    if (P.charAt(i + j + 1) != P.charAt(j)) {
      isPrefix = false;
      break;
    }
  }
  if (isPrefix) {
    lastPrefixPosition = i + 1;
  }
  // まず P の先頭が P の末尾後に来るようなシフト量を計算
  goodSuffix[i] = lastPrefixPosition - i + (m - 1);
}
// その後、接尾辞が何度も出現する場合にピッタリ重なるシフト量を計算
for (int i = 0; i < m - 1; i++) {
  // P[...i] と P の接尾辞が一致する長さ
  int suffixLength = 0;
  for (int j = 0; j < i - 1; j++) {
    if (P.charAt(m - 1 - j) != P.charAt(i - j)) {
      break;
    }
    suffixLength++;
  }
  // その直前の文字が異なっていれば更新
  if (P.charAt(i - suffixLength) != P.charAt(m - 1 - suffixLength)) {
    goodSuffix[m - 1 - suffixLength] = m - 1 - i + suffixLength;
  }
}

// ボイヤー-ムーア法の実装
int txt_idx = m - 1;
while (txt_idx < n) {
  int pat_idx = m - 1;
  while (P.charAt(pat_idx) == T.charAt(txt_idx)) {
    if (pat_idx == 0) {
      System.out.println("パターンが見つかりました: " + txt_idx);
      break;
    }
    pat_idx--;
    txt_idx--;
  }
  // 規則に従ってシフト量を計算
  txt_idx += Math.max(badChar[T.charAt(txt_idx)], goodSuffix[pat_idx]);
}