二次元文字列検索 (Baker-Bird)

説明

サイズが (nx,ny) の二次元のテキスト T と，サイズが (mx,my) の二次元のパターン P が与えられたとき，T の中で P が出現する位置を検索する問題を二次元文字列検索，二次元マッチングなどという．

この問題に対する最も基本的なアプローチは，テキストもパターンも行単位で考えて，テキストの各行に対して，パターンの各列を検索することである．このとき複数のパターンを何度も検索することになるため，Aho-Corasick アルゴリズムを用いれば効率的に実行できると考えられる．これを Baker-Bird のアルゴリズムという．

具体的には，Baker-Bird のアルゴリズムは次のように記述される．

• パターン P を行単位で区切り，Aho-Corasick アルゴリズムを用いてパターンマッチングオートマトンを生成する．
• パターン P の各行を受理するオートマトンの状態番号を，列方向に読んだもの M を覚えておく．
• テキスト T を行単位で区切り，パターンマッチングオートマトンに流し込む．流し込んだときに現れた状態遷移のリストを束ねて新しいテキスト T' を作る．
• 新しいテキスト T' を列単位で区切り，列方向に M を Knuth Morris Pratt アルゴリズムで検索する．

これにより，計算量は O(N + |A| M) となる．ただし N はテキストの文字数，M はパターンの文字数，|A| はアルファベット集合のサイズである．

同じパターンを異なるテキストに対して何度も検索するような場合は，前処理は一度 O(|A| M) でやればよく，流し込む段階での計算量はテキストサイズ N_k に対して O(N_k) なので，やはり計算量は O(N + |A| M) となる．

以下の実装では，文字列系の問題は速度にシビアなので，グローバルに int [][] を置いている．おかげで結構読みづらくなってしまった．

計算量

• O(N + |A| M)，ただし N はテキストの総文字数，M はパターンの文字数．

使い方

int T[N][N], P[M][M]

グローバルにおいてあるテキストとパターン．型は int だが，char で入れる．

baker_bird(nx, ny, mx, my)

T[0..ny-1][0..nx-1] をテキスト，P[0..mx-1][0..my-1] をパターンと見て Baker Bird アルゴリズムを実行する．

ソースコード

const int N = 2000, M = 200;
const int A = 0x100, S = M*M*A;
int top, *next[S];
int T[N][N], P[M][M];
int add_node() {
  next[top] = new int[A];
  fill(next[top], next[top]+A, -1);
  return top++;
}
#define TRANSFORM(T, nx, ny) { \
  for (int q = 0; q < ny; ++q) { \
    int t = 0, len = nx; \
    for (int i = 0; i < len; ++i) { \
      int a = T[q][i]; \
      while (next[t][a] < 0) t = next[t][0]; \
      t = next[t][a]; \
      T[q][i] = t; \
    } \
  } \
}
int baker_bird(int nx, int ny, int mx, int my) {
  // Horizontal Aho-Corasick
  top = 0; add_node(); // initial state
  int acc[my]; memset(acc, 0, sizeof(acc));
  for (int i = 0; i < my; ++i) {
    int t = 0;
    for (int j = 0; j < mx; ++j) {
      char c = P[i][j];
      if (next[t][c] < 0) next[t][c] = add_node();
      t = next[t][c];
    }
    acc[i] = t;
  }
  queue<int> Q; // make failure links using BFS
  for (int a = 1; a <= 0xff; ++a) {
    if (next[0][a] >= 0) {
      next[ next[0][a] ][0] = 0;
      Q.push( next[0][a] );
    } else next[0][a] = 0;
  }
  while (!Q.empty()) {
    int t = Q.front(); Q.pop();
    for (int a = 1; a <= 0xff; ++a) {
      if (next[t][a] >= 0) {
        Q.push( next[t][a] );
        int r = next[t][0];
        while (next[r][a] < 0) r = next[r][0];
        next[ next[t][a] ][0] = next[r][a];
      }
    }
  }
  TRANSFORM(T, nx, ny); TRANSFORM(P, mx, my);

  // Vertical Knuth Morris Pratt
  int fail[my+1]; fill(fail, fail+my+1, -1);
  for (int i = 0, j = -1; i < my; ) {
    while (j >= 0 && P[i][mx-1] != P[j][mx-1]) j = fail[j];
    if (P[++i][mx-1] == P[++j][mx-1]) fail[i] = fail[j];
    else                              fail[i] = j;
  }
  int count = 0;
  for (int l = 0; l < nx; ++l) {
    for (int i = 0, k = 0; i < ny; ++i) {
      while (k >= 0 && P[k][mx-1] != T[i][l]) k = fail[k];
      if (++k >= my) {
        ++count; // match at (l, i) ... right-bottom corner
        k = fail[k];
      }
    }
  }
  return count;
}

Verified

• UVA 11019 (Matrix Matcher)

参考文献

• T.P.Baker, "A technique for extending rapid exact-match string-matching to arrays of more tha none dimensions", SIAM J.Comput. 7 1978.
• R.S.Bird, "Two-dimensional pattern-matching", Info. Proc. Lett. 6 1977