SW 개발

[알고리즘] 보이어무어 알고리즘 (예제코드)

. . . 2009. 4. 14. 00:17
반응형

비트컴퓨터에서 과제로 제출했던 코드.

실제 동작테스트 완료된 자료입니다.

예제코드

#if 0 

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);    // suffix 배열을 만든다. 

   for (i = 0; i < m; ++i)       
      bmGs[i] = m; 
      // good-suffix는 이동거리 정보를 갖게 되는데. 최대 이동거리는 문자열의 
      // 길이이므로 모든 배열의 요소를 strlen(m)으로 세팅 

   j = 0; 

   for (i = m - 1; i >= 0; --i) 
      // suffix 비교방식은 가장 뒤의 인덱스부터 비교하게 된다. 
      // m=8일 경우 7 6 5 4 3 2 1 순으로 비교 

      if (suff[i] == i + 1)     
         // 지금까지 확정된 문자열이 앞에 인덱스와 일치하는 경우!! 
         // 처음으로 틀린위치 전이 앞의 문자열과 완벽히 일치!! 
         // a b x x x x a b 

         for (; j < m - 1 - i; ++j) 
            // 뒤에서 부터 비교를 하기때문에..m - 1 - i는 
            // 즉.. 총 길이에서 확정된 길이 플러스 i+1만큼 옮기는게 가능. 
            // 단.. 나머지들은 비교를 하나마나 그만큼 옮기는게 가능하다?! 

            if (bmGs[j] == m) 
               bmGs[j] = m - 1 - i; 
            // 완전 같게 되는경우. 확정된 길이를 뺀만큼 옮기게 된다. 

   for (i = 0; i <= m - 2; ++i) 
      bmGs[m - 1 - suff[i]] = m - 1 - i; 
      // suffix로 움직이지 못하는 경우가 발생하면.. 
      // 즉 suffix[i]까지 왔지만 앞에 일치하는 접미사가 없어서 못움직이면.. 
      // bmgs[최대 인덱스] 는 한값으로 1으로 수렴하게 된다. 
      // 어떤경우던지 suff[최대 인덱스는]는 m이 되기때문이다. 

      // 일치하는 접미사가 중간에 위치하는 경우.. 
      // 그 접미사가 발견된 인덱스에 해당하는 gs 배열 세팅.. 
      // 최대 이동거리가 아아니라.. 그보다 작아지게 된다. 

      // gs는..  해당 인덱스 까지 비교한후.. suffix 배열의 정보.. 즉 앞에서 일치하게 되는 접미사 부분만큼 이동. 
} 


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); 
   } 
} 
#endif 

#include  
#include  

#define  OUTPUT(x)  printf("index:%2d\n",(x)) 
#define MAX(a,b)   (((a)>(b))?(a):(b)) 
#define ASIZE    256 
#define XSIZE    256 


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 >= -1; --i) 
      if (i == -1 || 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 preBmGs(char *x, int m, int bmGs[]) { 
   int i, j, suff[XSIZE]; 

   suffixes(x, m, suff);    // suffix 배열을 만든다. 

   for (i = 0; i < m; ++i)       
      bmGs[i] = m; 
      // good-suffix는 이동거리 정보를 갖게 되는데. 최대 이동거리는 문자열의 
      // 길이이므로 모든 배열의 요소를 strlen(m)으로 세팅 

   j = 0; 

   for (i = m - 1; i >= 0; --i) 
      // suffix 비교방식은 가장 뒤의 인덱스부터 비교하게 된다. 
      // m=8일 경우 7 6 5 4 3 2 1 순으로 비교 

      if (suff[i] == i + 1)     
         // 지금까지 확정된 문자열이 앞에 인덱스와 일치하는 경우!! 
         // 처음으로 틀린위치 전이 앞의 문자열과 완벽히 일치!! 
         // 일단 쭉~ 스캔하면서 완벽 일치의 경우만 뽑아본다. 
         // a b x x x x a b 

         for (; j < m - 1 - i; ++j) 
            // 뒤에서 부터 비교를 하기때문에..m - 1 - i는 
            // 즉.. 총 길이에서 확정된 길이 플러스 i+1만큼 옮기는게 가능. 
            // 단.. 나머지들은 비교를 하나마나 그만큼 옮기는게 가능하다?! 

            if (bmGs[j] == m) 
               bmGs[j] = m - 1 - i; 
            // 완전 같게 되는경우. 확정된 길이를 뺀만큼 옮기게 된다. 

   for (i = 0; i <= m - 2; ++i) 
      bmGs[m - 1 - suff[i]] = m - 1 - i; 
      // suffix로 움직이지 못하는 경우가 발생하면.. 
      // 즉 suffix[i]까지 왔지만 앞에 일치하는 접미사가 없어서 못움직이면.. 
      // bmgs[최대 인덱스] 는 한값으로 1으로 수렴하게 된다. 
      // 어떤경우던지 suff[최대 인덱스는]는 m이 되기때문이다. 

      // 일치하는 접미사가 중간에 위치하는 경우.. 
      // 그 접미사가 발견된 인덱스에 해당하는 gs 배열 세팅.. 
      // 최대 이동거리가 아아니라.. 그보다 작아지게 된다. 

      // gs는..  해당 인덱스 까지 비교한후.. suffix 배열의 정보.. 즉 앞에서 일치하게 되는 접미사 부분만큼 이동. 
} 



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); 
   } 
} 

int main() 
{ 
   char y[] = "acgagggaggputer"; 
   char x[] = "gcagagag"; 

   BM( x, strlen(x), y, strlen(y) );   
   return 0; 
} 
반응형