본문 바로가기

자료구조 & 알고리즘/문자열 매칭 알고리즘

[박혜웅] Boyer-Moore

  •  Boyer-Moore의 특징

    • 윈도우는 왼쪽에서 오른쪽으로 이동하며, 패턴내에서 오른쪽에서 왼쪽으로 검사한다.
    • 문자열이 불일치 할 때 대상 text에서 다음 비교를 위해서 이동할 위치를 최대화한 알고리즘이다.
    • 성능

      • 전처리시 공간복잡도 : O(m+sigma)
      • 검색시 시간복잡도: O(mn)
      • 최악의 경우 비교회수: 3n
      • 최상의 경우 비교회수: O(n/m)

 

 

  • Boyer-Moore의 설명

    • 일치하지 않는 문자가 나왔을 때  good-suffix shift 또는 bad-character shit 중 큰 값으로 윈도우를 이동한다.

    •  good-suffix shift

      • 텍스트와 일치하는 문자열이 패턴에 2개이상 존재하는 경우
      •  
      • 텍스트와 일치하는 문자열이 패턴에 1개만 존재하는 경우
      •  

         

    • bad-character shit

      • 텍스트와 다른 문자가 패턴에 2개이상 존재하는 경우

      • 텍스트와 다른 문자가 패턴에 1개만 존재하는 경우
      •  

 

 


  • Boyer-Moore의 실행

 http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140


 

  • Boyer-Moore의 소스
  1. void preBmBc(char *x, int m, int bmBc[]) {
       int i;

       for (i = 0; i < ASIZE; ++i)
          bmBc[i] = m;
       for (i = 0; i < m - 1; ++i)
          bmBc[x[i]] = m - i - 1;
    }


    void suffixes(char *x, int m, int *suff) {
       int f, g, i;

       suff[m - 1] = m;
       g = m - 1;
       for (i = m - 2; i >= 0; --i) {
          if (i > g && suff[i + m - 1 - f] < i - g)
             suff[i] = suff[i + m - 1 - f];
          else {
             if (i < g)
                g = i;
             f = i;
             while (g >= 0 && x[g] == x[g + m - 1 - f])
                --g;
             suff[i] = f - g;
          }
       }
    }

    void preBmGs(char *x, int m, int bmGs[]) {
       int i, j, suff[XSIZE];

       suffixes(x, m, suff);

       for (i = 0; i < m; ++i)
          bmGs[i] = m;
       j = 0;
       for (i = m - 1; i >= 0; --i)
          if (suff[i] == i + 1)
             for (; j < m - 1 - i; ++j)
                if (bmGs[j] == m)
                   bmGs[j] = m - 1 - i;
       for (i = 0; i <= m - 2; ++i)
          bmGs[m - 1 - suff[i]] = m - 1 - i;
    }


    void BM(char *x, int m, char *y, int n) {
       int i, j, bmGs[XSIZE], bmBc[ASIZE];

       /* Preprocessing */
       preBmGs(x, m, bmGs);
       preBmBc(x, m, bmBc);

       /* Searching */
       j = 0;
       while (j <= n - m) {
          for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
          if (i < 0) {
             OUTPUT(j);
             j += bmGs[0];
          }
          else
             j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
       }
    }