알고리즘 / 보이어무어알고리즘에 대한 고찰

SW 개발

알고리즘 / 보이어무어알고리즘에 대한 고찰

. . . 2009. 4. 14. 00:26

Boyed-Moor Algorithm

이전에 비트컴퓨터 과제로 제출했던 자료입니다 ㄷㄷ

1. bad character
- 문자열 비교
- 예제 1 의 구현
2. Suffix
3. Boyed-Moor Algorithm

1. bad character

BAD CHARACTER 란 비교할 문자열의 가장 마지막부터 비교를 시작할 때 나오는 특성을 이용한다.
마지막 문자를 비교 할 때 나오는 문자에 따라 나머지 문자열은 비교 안해도 되는 구간이 있다.

문자열 비교

위의 문자열에 대해 비교를 시작한다.

뒤에서 부터 비교하는 순서에 의해 I[7] 부터 비교를 시작한다..
- Process1 : 7번 인덱스에 C 가 온다고 가정하자. 그럼.. 비교 문자열 I는 2번 인덱스까지 C가 없으므로 2번 인덱스 까지 SKIP 이 가능하다.
- Process2 : 7번 인덱스에 T가 온다고 가정하자. 그럼 비교문자열 I 내에는 T 가 없으므로 바로 문자열 길이만큼 SKIP 이 가능

위와 같은 특징으로 표를만들면 다음과 같다.

이때 Bc 배열의 값은 적으로 이동가능한 shift거리가 아니다. 예를들면 C 가 2번째비교한 인덱스에 나온다면 이동거리는 6이 아니라 5가 될것이다. 이에 대한 설명과 구현은 마지막에 최종알고리즘에서 하는것으로한다.

예제 1 의 구현

다음의 코드로 구현이 가능하다구현

char x[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;
}

2. Suffix

접미사 정의

비교 문자열 내에 중복되는 접미, 접두사를 구하면 위의 bad character와 같은 특성을 이용할 수 있다.

단, boyer-moor 특성상 뒤에서부터 비교를 하게 되므로 일치하는 접미사를 찾거나(case1), 완벽하게 대칭되는 접미, 접두사(case2)를 찾으면 나머지 문자열에 대해 skip할 수 있다.

case 1. 공통된 접미사

case 2. 완벽 대칭되는 접미, 접두사.

접미사(suffix array)배열 구하기

가장 뒤의 인덱스부터 비교를 하기 때문에 공통된 접미사를 기준으로 구한다.

위의 기본 문자열의 접미사를 구한다.

길이 1 의 경우

길이1 : Case2 = 접두 접미사가 완벽하게 일치한다.

길이 2 의 경우

길이2 :
접두, 접미사 없음

길이 3 의 경우

길이3 :
접두, 접미사 없음

길이 4 의 경우

길이4 : case1
A G => 접미사

길이 5 의 경우

길이5:
접두, 접미사 없음

길이 6 의 경우

길이6: case1
G A G => => 접미사

길이 7 의 경우

길이7:
접두, 접미사 없음

길이 8 의 경우

길이8: case2
접두 접미사가 완벽하게 일치한다

위의 정보를 바탕으로, 배열을 suffix 로 나타내면 다음과 같다.

특징, 문자열이 정해진 길이는 인덱스 + 1이다.

s[3] (case1)

s[3]은 i[7] 부터 비교를 할 때 4개의 문자 비교를 하였고 앞의 4개 문자와 접미 접두사 관계이다. 단 일치하는 접미사의 개수는 2개이다.

s[0] (case2)

s[0]은 i[7] 부터 비교를 할 때 1개의 문자 비교를 하였고 앞의 1개인 접미접두사가 일치한다.

Case2 : s[i] = i+1

접미사(suffix array)배열 구현

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

Good-suffix 정의

위의 suffix 배열에서 비교문자열의 접미 접두사의 정보와 크기를 구했다면 Good-suffix배열에서는 suffix 배열을 이용해서 실제로 shift 시키는 거리를 알아낸다.

good suffix 는 오직 접미 접두사의 정보만으로 shift를 시킨다.

I[7] 부터 차례대로 비교를 하다가 틀려지는 지점 I[3]을 살펴보자. 비록 I[3]은 틀렸어도 I[4]~I[7]까지의 4개 스트링은 원본과 같음을 알수있다. 이 정보는 이미 위에서 구한 suffix array의 s[3]의 정보에서 알 수 있다. s[3]은 2개의 접미부를 갖고 있으므로 case1과 같이 shift 시킬 수 있다.

즉, case 로 나누면 다음과 같다.

배열로 구현 시 인덱스와 비교를 시작하는 위치는 숫자상으로 반대이므로 그 점에 유의하여 구현하도록 한다.

Good-suffix의 구성

phase 1

suff[]의 값이 0 이라는것은 접미 접두사가 없으므로 bad suffix에서 전혀 포함되지 않은 문자 같은 역할을 하게 된다. 즉, sizeof(i)으로 초기화.

for (i = 0; i < m; ++i)
  bmGs[i] = m;

단, 앞뒤가 완전히 같은 경우 최대로 옮길수있는거리는 해당 sizeof(i) - 접미사의 길이 이다.

위의 표와 같이 표현될 경우 최대 shift는 sizof( i ) ? 2 = 6

if (suff[i] == i + 1)                   // case2. 판별
     for (; j < m - 1 - i; ++j)         // case2. 중 완전일치 조건 제거
          if (bmGs[j] == m)
                  bmGs[j] = m - 1 - i;  // 초기화 재 설정

phase 2

suff[] 의 값이 있는 경우 즉, case1 의 경우 suff[i]의 값은 끝에서부터 접미사의 크기이다.

옮기는 입장에서는 그 접미사를 만났을 때 옮길 옮기게 된다. 접미사가 되는 인덱스의 조건은 sizeof(i) ? suff[] 그러나 확실히 문자열이 확정되는 전제조건을 참조하면 뒤에서부터 비교를 한다 했을 때 suff[] 보다 한번더 비교를 하여 틀린조건을 찾고 sizeof(i) - suff[i] -1 가 된다. 이때 i 의 인덱스는 앞쪽 접미사의 인덱스를 가르키게 된다. 앞쪽접미사의 인덱스를 뒤쪽접미사로 옮기면 된다.

즉.. 접미사가 발견된 경우 (siff[]에 값이 있는경우)는 sizeof(i) ? i ? 1 만큼 옮기면 된다.

코드로 표현하면...

Gs[m - 1 - suff[i]] = m - 1 - i;, Suff[3] = 2 일때.. Gs[5] = 4 이다.

Good-suffix-array 구현

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)
      /*  지금까지 확정된 문자열이 앞에 인덱스와 일치하는 경우!! Case2
      (즉, 처음으로 틀린위치 전이 앞의 문자열과 완벽히 일치!! )
          a b  . . . . . .  a b    */
      for (; j < m - 1 - i; ++j)
        if (bmGs[j] == m)
          bmGs[j] = m - 1 - i;
        /* suff[i]에서 i를 끝 인덱스부터 확인하기 때문에 case2에 해당하고 가장 긴
          접미사를 구하게 된다. 그때 최대이동거리는  sizeof(i) - 접미사의 길이 */
  for (i = 0; i <= m - 2; ++i)
    // 처음부터 틀렸으면.. 즉 i <= m – 2 이면.. 1칸을 옮기게 된다. 1;
    bmGs[m - 1 - suff[i]] = m - 1 - i;
      /* 접미,접두사가 있는경우 (suff[i] 값이 있는경우 ) 해당 인덱스 i 만큼 옮긴다.
      자세한 설명은 윗 그림과 설명을 참고하기 바란다. */
}

3. Boyed-Moor Algorithm

설명

뒤에서부터 비교를 시작을 하게 되므로 접미 접두사, bad-character 모두 적용이 가능하다.

하지만 때에 따라서 bad-charater가 shift 거리가 더 멀때도, 접두접미사를 이용한 shift 거리가 더 멀때도 있다. 그럼.. 위에서 구한 두개의 방식중에 더 효율적으로 이동하도록 (shift 거리가 더 큰쪽으로) 함수를 작성하여 적용한다.

Bad-Charater 이동

Bad-characte는 매번 해당 j[index] 와 비교하게 된다 => y[i + j]

단, Bc[] 값은 상대적인 값이다. Bc[y[i+j]] 가 처음비교할때나오면 Bc[]값 그대로 옮겨 지겠지만 중간에 나오면 그 이미 비교한 만큼 덜 이동하게 된다. 즉 비교문자열 i 내에서 상대적인 값이라 볼수있다.

Suffix 이동

Suffix 를 이용한 이동은 비교문자열 I 내에서 절대적으로 이동되기 때문에 Bad-character와 같은 연산은 필요치 않다. **

구현

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

  /* Preprocessing */
  preBmGs(x, m, bmGs); // Suffix 방식의 table 생성
  preBmBc(x, m, bmBc); // Bad-character 방식의 table 생성

  // 더 두개의 이동방식중 더 큰 것을 찾아서 해당인덱스만큼 이동 
  j = 0;
  while (j <= n - m) 
  {
    for (i = m - 1 ; i>=0 && x[i]==y[i + j] ; --i)
    {
      /* 가장 뒤쪽 인덱스 부터 비교 : i = m - 1 모두 비교가 끝났거나, 틀린부분이 최초로 발생하면 루프가 끝난다, 즉 최초로 틀린 부분이 발생한 곳의 인덱스를 반환해준다.*/
      /* 틀린 문자열이 발생한 곳에서 Gs 와 Bc 를 이용하여 더 이동거리가 큰 것을 선택 */
      if (i < 0)
      { 
        /* i > m 이므로…모두 같음. 최대 접미사의 크기였던 gs[0]만큼 이동한다. */
        OUTPUT(j);
        j += bmGs[0];
      }
      else
        j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);  
        /* Gs[] 문자열 내에 절대적으로 이동가능한 수치이다. 위의 그림 설명 참조 */
        /* Bc[] 의 경우 해당 문자열을 바로 비교하고, 이동거리 인덱스로 바꾸면..
        bmBc[y[i + j]] - m + 1 + I 와 같은 식이 성립한다. 위의 설명 참조 */
      /* 두개의 경우중에 MAX함수를 이용하여 큰 것을 반환하여 shift 한다. */ 
    }
  }
}

현재글알고리즘 / 보이어무어알고리즘에 대한 고찰

Xeno`s Study