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

Xeno's Life Blog (http://xenostudy.tistory.com)
- 글쓴이 : Xeno
- 원본출처 : 본문에 없으면 직접작성.
- 기타사항 :
   * 틀린사항 및 문의사항은 댓글달아주세요.
   * 퍼가실땐 댓글달아주시고, 출처는 밝혀주세요.ㅎ



- 기타사항 : doc로 작성한걸 html로 바꾸려니 빡시네여;; 틀린사항은 댓글로 달아주세여~

Edit by Xeno!!

< Boyed-Moor Algorithm >

1. bad character

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

1-1-1) 예제

0

1

2

3

4

5

6

7

G

C

A

G

A

G

A

G

<비교문자열 I>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G

C

A

G

A

A

B

C

D

E

F

G

A

T

G

C

A

G

A

G

A

G

Process1

G

C

A

G

A

G

A

G

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Process2

 

 

 

 

 

 

G

C

A

G

A

G

A

G

 

 

 

 

 

 

 

 

Process3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G

C

A

G

A

G

A

G

< 문자열 GCAGAABCDEFGATGCAGAGAG 와 비교>

뒤에서 부터 비교하는 순서에 의해 I[7]부터 비교를 시작한다..

Process1 : 7 인덱스에 ‘C’ 온다고 가정하자. 그럼.. 비교 문자열 I 2 인덱스까지 C 없으므로 2 인덱스 까지 SKIP 가능하다.

Process2 : 7 인덱스에 ‘T’ 온다고 가정하자. 그럼 비교문자열 I 내에는 T 없으므로 바로 문자열 길이만큼 skip 가능

 

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

G

C

A

나머지 문자열

2

6

1

8

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

 

1-1-2) 구현

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

 

2-1-1) 접미사 정의

비교 문자열 내에 중복되는 접미, 접두사를 구하면 위의 bad character와 같은 특성을 이용할 수 있다. , boyer-moor 특성상 뒤에서부터 비교를 하게 되므로 일치하는 접미사를 찾거나(case1), 완벽하게 대칭되는 접미, 접두사(case2)를 찾으면 나머지 문자열에 대해 skip할 수 있다.

0

1

2

3

4

5

6

7

G

C

A

G

A

G

A

G

<비교문자열 I>

case 1. 공통된 접미사
case 2. 완벽 대칭되는 접미, 접두사.

 

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

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

G

C

A

G

A

G

A

G


의 접미사 구하기.

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

길이1 : Case2

접두 접미사가 완벽하게 일치한다.

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

길이2 :

접두, 접미사 없음

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

길이3 :

접두, 접미사 없음

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

길이4 : case1

A G => 접미사

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

길이5:

접두, 접미사 없음

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

길이6: case1

G A G => => 접미사

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

길이7:

접두, 접미사 없음

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

길이8: case2

접두 접미사가 완벽하게 일치한다

위의 정보를 배열 suffix 나타내면..

0

1

2

3

4

5

6

7

1

0

0

2

0

4

0

8

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

s[3] (case1)

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

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

s[0] (case2)

G

C

A

G

A

G

A

G

G

C

A

G

A

G

A

G

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

 

2-1-3) 접미사(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;
      }
   }
}

 

2-2-1) Good-suffix 정의

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

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

 

전제 사항

 

0

1

2

4

5

6

7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G

C

A

T

A

G

A

G

D

E

F

G

A

T

G

C

A

G

A

G

A

G

Process1

G

C

A

G

A

G

A

G

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

0

1

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G

C

A

T

A

G

A

G

D

E

F

G

A

T

G

C

A

G

A

G

A

G

Process1

G

C

A

G

A

G

A

G

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Process2

 

 

 

 

G

C

A

G

A

G

A

G

 

 

 

 

 

 

 

 

 

 

case 1. 공통된 접미사

 

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

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

 

2-2-1) Good-suffix 구성

 

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

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

G

G

A

G

A

C

G

G

G

G

A

G

A

G

G

G

 좌측 표와 같은경우 최대 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;  // 초기화 재 설정

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

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

index

0

1

2

3

4

5

6

7

 

 

 

 

 

G

C

A

T

A

G

A

G

D

E

F

G

Process 1

G

C

A

G

A

G

A

G

 

 

 

 

비교순서

 

 

 

 

 

3

2

1

 

 

 

 

Process 2

 

 

 

 

G

C

A

G

A

G

A

G

비교순서

 

 

 

 

 

 

 

 

 

 

 

4

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

2-2-2) 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 &#8211; 2 이면.. 1칸을 옮기게 된다. 1;
      bmGs[m - 1 - suff[i]] = m - 1 - i;
         /* 접미,접두사가 있는경우 (suff[i] 값이 있는경우 ) 해당 인덱스 i 만큼 옮긴다.
          자세한 설명은 윗 그림과 설명을 참고하기 바란다. */

}

 

3. Boyed-Moor Algorithm

 

3-1-1) 설명

뒤에서부터 비교를 시작을 하게 되므로 접미 접두사, bad-character 모두 적용이 가능하다.
하지만 때에 따라서 bad-charater shift 거리가 멀때도, 접두접미사를 이용한 shift 거리가 멀때도 있다그럼.. 위에서 구한 두개의 방식중에 효율적으로 이동하도록 (shift 거리가 큰쪽으로) 함수를 작성하여 적용한다.

 

3-2-1) Bad-Charater 이동

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

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

3-2-2) Suffix 이동

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

 

3-3-1) 구현

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 한다. */                              
   }
}

 

 


TAGS.

Comments 8