• Shift-Or 의 특징

    • 비트병렬성을 기반으로, 머신의 처리단위(워드) 내부에서 비트연산 이용
    • 머신의 처리 단위보다 패턴의 길이가 짧다면 효과적임
    • 성능

      • 전처리 시간,공간복잡도: O(m + sigma)
      • 검색시 시간복잡도: O(n)

 

  • Shift-Or 기본 개념

    •  

 

 

  • Shift-Or 설명

    • bit-mask table

      • 가로: 패턴
      • 세로: 패턴에 나타나는 문자종류
      • 패턴에 해당하는 문자가 나타나는 곳만 0으로 세팅.
      •  

 

 

  • Shift-Or 실행
  •     

 

  • Shift-Or 소스
  1. int preSo(char *x, int m, unsigned int S[]) {
        unsigned int j, lim;
        int i;
        for (i = 0; i < ASIZE; ++i)
          S[i] = ~0;
        for (lim = i = 0, j = 1; i < m; ++i, j <<= 1) {
          S[x[i]] &= ~j;
          lim |= j;
        }
        lim = ~(lim>>1);
        return(lim);
      }

      void SO(char *x, int m, char *y, int n) {
        unsigned int lim, state;
        unsigned int S[ASIZE];
        int j;
        if (m > WORD)
          error("SO: Use pattern size <= word size");

        /* Preprocessing */
        lim = preSo(x, m, S);

        /* Searching */
        for (state = ~0, j = 0; j < n; ++j) {
          state = (state<<1) | S[y[j]];
          if (state < lim)
            OUTPUT(j - m + 1);
        }
      } 

 

'자료구조 & 알고리즘 > 문자열 매칭 알고리즘' 카테고리의 다른 글

[박혜웅] Shift-Or  (0) 2010.03.27
[박혜웅] Knuth-Morris-Pratt(KMP)  (0) 2010.03.27
[박혜웅] Karp-Rabin  (0) 2010.03.27
[박혜웅] Brute Force(BF)  (0) 2010.03.27
[박혜웅] Boyer-Moore-Horspool  (0) 2010.03.27
[박혜웅] Boyer-Moore  (0) 2010.03.27
Posted by 바게 BAGE