Boyer-Moore 법 (문자열 검색 알고리즘)

Boyer-Moore법은 브루트 포스법을 개선한 KMP법 보다 효율이 더 우수하기 때문에 실제로 문자열 검색에 널리 사용되는 알고리즘이다.

R.S Boyer과 J.S Moore가 만든 Boyer-Moore법은 KMP법보다 효율이 더 좋은데, 

원리는 텍스트와 패턴을 비교할때, 패턴의 마지막 문자부터 앞으로 검사를 진행하며, 일치하지 않는 문자가 있으면 미리 준비한 Skip table 에 따라서 패턴을 옮길 크기를 정하는 것이다.

 

Boyer-Moore 법은 두 접근 방식의 결합이다.

(1) Bad Character Heuristic

(2) Good Suffix Heuristic

위 두 방법은 텍스트에서 패턴을 찾는데 있어 독립적으로 사용될 수 있다. 

두 독립적인 접근 방법이 어떻게 Boyer Moore알고리즘에서 작동하는지 알아보자.

브루트포스법에서는 O(MN)으로 하나씩 돌면서 검사했다. KMP법에서는 pi배열을 기반으로 suffix와 prefix가 같은 곳 만큼 jump하여 비교하였다. Boyer Moore 알고리즘 또한 마찬가지로 pi배열 처럼 전처리를 pattern에 하는 것 처럼, 패턴을 이용해 위 두개의 heuristic에 대한 서로 다른 두 배열을 만든다. 그리고 그 배열을 이용해 건너 뛰는 것이다.

 

(1) Bad Character Heuristic

Bad Character 휴리스틱의 아이디어는 간단한데, text의 문자와 현재 패턴의 문자가 일치하지 않을때, text의 문자를 bad character라고 한다. 불일치시, pattern을 이동시키는데, 

1) 불일치가 일치 될때 까지 이동하거나,

2) Pattern P가 불일치한 문자를 건너뛴다.

 

Case 1 - 불일치가 일치 될때 까지 이동

패턴에서 일치하지 않는 문자가 마지막으로 발생한 위치는 찾는다. 그리고 만약 패턴안에 불일치된 문자가 준재한다면, 텍스트의 그 불일치된 문자에 Pattern에 존재하는 불일치 문자를 정렬하도록 pattern을 이동시킨다.

출처 : geeksforgeeks.org

위 예시를 본다면, 3번 위치에서 불일치가 발생했을때, 불일치 문자는 "A"이다. 그리고 이때, 패턴에서 불일치 문자인 "A"가 마지막으로 나타나는 곳을 찾는다. 패턴에서 "A"가 1번에 위치하기 하고, 마지막으로 나타나기 때문에, 패턴을 2칸 이동시켜 텍스트의 "A"와 패턴의 "A"가 일치 하도록 정렬 한다.

 

Case 2 - Pattern이 불일치한 문자를 건너뛴다.

패턴에서 일치하지 않는 문자가 마지막으로 나타난 위치를 찾을때, 문자가 패턴에 존재하지 않는다면, 패턴을 그 불일치 문자 다음으로 건너 뛴다.

출처 : geeksforgeeks.org

위 예시에서, 7번위치에서 불일치가 발생했다. 불일치 문자 "C"는 패턴에 존재하지 않기 때문에 패턴을 7번 다음으로 이동시킨다. (7번 이전의 이동은 불일치가 발생할 것이고 의미가 없기 때문이다.)

이러한 것을 통해서, 패턴을 전처리하고 매 문자의 마지막 발생하는 위치를 패턴의 길이와 같은 배열을 만들어 저장한다.

그리고 불일치 문자가 패턴에 존재하지 않으면, 패턴의 길이 만큼 이동한다. 따라서 Bad Character heuristic은 가장 좋은 경우 O(N/M)의 시간복잡도를 가진다. 텍스트와 패턴의 모든 문자가 다를경우에는 pattern의 길이(N)만큼 계속 건너뛸 것이기 때문에 O(N/M)일 것이다. 반면 최악의 경우, O(MN)의 시간복잡도를 가진다. 이 경우는 텍스트의 모든 문자와 패턴의 모든 문자가 동일할 경우, 예를들어 text = "AAAAAAAAAAA" 와 pattern = "AAAA" 일경우일 것이다.

 

/* Java Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
 
 
class AWQ{
     
     static int NO_OF_CHARS = 256;
      
    //A utility function to get maximum of two integers
     static int max (int a, int b) { return (a > b)? a: b; }
 
     //The preprocessing function for Boyer Moore's
     //bad character heuristic
     static void badCharHeuristic( char []str, int size,int badchar[])
     {
 
      // Initialize all occurrences as -1
      for (int i = 0; i < NO_OF_CHARS; i++)
           badchar[i] = -1;
 
      // Fill the actual value of last occurrence
      // of a character (indices of table are ascii and values are index of occurrence)
      for (int i = 0; i < size; i++)
           badchar[(int) str[i]] = i;
     }
 
     /* A pattern searching function that uses Bad
     Character Heuristic of Boyer Moore Algorithm */
     static void search( char txt[],  char pat[])
     {
      int m = pat.length;
      int n = txt.length;
 
      int badchar[] = new int[NO_OF_CHARS];
 
      /* Fill the bad character array by calling
         the preprocessing function badCharHeuristic()
         for given pattern */
      badCharHeuristic(pat, m, badchar);
 
      int s = 0;  // s is shift of the pattern with
                  // respect to text
       //there are n-m+1 potential alignments
      while(s <= (n - m))
      {
          int j = m-1;
 
          /* Keep reducing index j of pattern while
             characters of pattern and text are
             matching at this shift s */
          while(j >= 0 && pat[j] == txt[s+j])
              j--;
 
          /* If the pattern is present at current
             shift, then index j will become -1 after
             the above loop */
          if (j < 0)
          {
              System.out.println("Patterns occur at shift = " + s);
 
              /* Shift the pattern so that the next
                 character in text aligns with the last
                 occurrence of it in pattern.
                 The condition s+m < n is necessary for
                 the case when pattern occurs at the end
                 of text */
              //txt[s+m] is character after the pattern in text
              s += (s+m < n)? m-badchar[txt[s+m]] : 1;
 
          }
 
          else
              /* Shift the pattern so that the bad character
                 in text aligns with the last occurrence of
                 it in pattern. The max function is used to
                 make sure that we get a positive shift.
                 We may get a negative shift if the last
                 occurrence  of bad character in pattern
                 is on the right side of the current
                 character. */
              s += max(1, j - badchar[txt[s+j]]);
      }
     }
 
     /* Driver program to test above function */
    public static void main(String []args) {
         
         char txt[] = "ABAAABCD".toCharArray();
         char pat[] = "ABC".toCharArray();
         search(txt, pat);
    }
}

(2) Good Suffix Heuristic

Bad Character Heuristic과 마찬가지로, pattern을 전처리 하여 배열을 만드는 것이 필요하다. 

텍스트 T의 부분문자열(substring)과 패턴 P의 substring과 일치하는 텍스트 T와 일치하는 부분문자열을 t라고 할때, 패턴을 이동시키는 것이

1) 패턴 P에서의 t가 다른부분에 존재하는 곳이 텍스트(T)의 t에 일치할때 까지 패턴을 이동시키거나

2) 패턴 P의 prefix가 t의 suffix와 일치 할때 까지 패턴을 이동시키거나

3) 패턴 P가 t를 지날때 까지 패턴을 이동시킨다.

 

Case 1 - 패턴 P에서의 다른 부분에 존재하는 t가 텍스트 T의 t에 일치할 때 까지

패턴 P에서 t가 여러번 존재 할 수도 있다. 이러한 경우에는, 텍스트 T의 t와 패턴이 정렬 되게끔 패턴을 이동한다.

 

 

출처 : geeksforgeeks.org

위 예시를 본다면, 인덱스 2에서 불일치가 일어나기 전까지 t는 "AB"가 된다. (녹색) 

그리고 t인 "AB"를 패턴 P에서 찾는다. 그리고 1번위치 (노란색 배경)에서 t와 동일한 부분을 찾았다. 그래서 패턴을 P의 t와 T의 t를 정렬해 주기 위해서 2칸 이동한다.이것은 original Boyer Moore의 weak rule이고 그렇게 효과적이지 못하다. Strong Good Suffix rule을 뒤에 다룰 것이다.

 

Case 2 - 패턴 P의 prefix가 텍스트 T 안의 t의 suffix와 일치 할때 까지 패턴을 이동

항상 패턴 P안에 t가 있진 않을 수 있다. 전혀 없을 수도 있는데, 이러한 경우 패턴 P의 prefix와 일치하는 t의 suffix를 검색해서 P를 이동해서 정렬 할 수도 있다.

출처 : geeksforgeeks.org

위 예시의 경우, 불일치가 일어나기 전까지인 t는 "BAB" (녹색)이며 2~4번 인덱스에 위치한다. 하지만 P에 t와 동일한 것이 없기 때문에, t의 suffix와 일치하는 패턴 P의 prefix를 찾을 것이다. 노란색 배경으로 칠해져 있는 "AB" prefix를 0~1번 인덱스에서 찾았다. 이는 t랑 전체 동일하지는 않지만, 인덱스 3번부터인 "AB:", suffix of t와 일치한다. 

그리고 나서 3칸을 이동해 prefix와 suffix가 일치하도록 패턴을 이동시킨다.

 

Case 2 - 패턴 P가 t를 지날때 까지 패턴을 이동

위 두 조건이 만족되지 않는다면, 패턴이 t를 지나도록 이동시킨다.

출처 : geeksforgeeks.org

위 예시에서 볼수 있듯이, 첫째로 t인 "AB"가 패턴 P에 없다. 둘째로 또한 t의 suffix와 일치하는 패턴 P의 prefix 또한 없다. 이러한 경우 인덱스 4번까지 일치하는 것을 찾을수 없기 때문에 t 다음으로 패턴 P를 이동시킨다. (인덱스 5로)

 

* Strong Good Suffix Heuristics

텍스트 T의 t와 일치하는 패턴 P의 부분을 q (P[i to n]라 하고, 일치하지 않는 문자를 c (P[i-1])이라고 했을때, case 1과 다르게, c가 앞에 존재하지 않는 t를 패턴 P에서 검색한다. 가장 가까운 곳에서 발생하는 곳에 텍스트 T의 t와 일치하도록 패턴 P를 움직인다.

출처 : geeksforgeeks.org

예를들어, q = P[7 to 8]가 텍스트 T에서 t랑 일치한 패턴의 부분이다. 

c ( P[6] )인 "C"가 불일치 문자이다.

패턴 P에서 t를 검색해보면, 4번 인덱스에서 처음 등장한다. 하지만 c와 동일한 문자 "C"가 앞서 존재하기에, 이것을 건너뛰고 다시 찾는다. 인덱스 1번 자리에서, 노란색 배경의 t가 등장하는데, A가 앞에 존재하기 때문에(c와 동일하지 않은), 패턴을 6번 옮겨 텍스트 T의 t와 패턴 P의 t가 일치하도록 올긴다. 이렇게 하는 이유는, t인 "AB"앞에 c인 문자 "C"가 존재한다면 이미 불일치 한것을 알기 때문이다. 따라서 c다음에 어떠한 t가 오더라도 t와 정렬하면 불일치 될것이기에, 건너 뛰는 것이다.

 

* Good Suffix Heuristics를 위한 전처리

전처리 과정에 있어서 shift라는 배열이 만들어 진다. 각 shift[i]는 i-1 위치에서 불일치가 발생했을때 패턴이 이동하는 거리를 저장한다. 즉, 이말은 i-1 위치에서 불일치가 발생했을 때, 패턴의 suffix가 i부터 시작해서 끝까지라는 말이다. 

전처리는 strong good suffix와 case 2 따로 분리되어 진행된다.

 

1) Strong Good Suffix에 대한 전처리

전처리 하기에 앞서서, 경계의 개념에 대해서 말해보자. 경계(border)는 적절한 suffix와 적절한 prefix를 둘다 가진 부분문자열 substring이다. 예를들어 "ccacc"에서 "c"와 "cc"가 경계라 할 수 있다. (prefix == suffix)

bpos(border position)배열이 전처리 과정의 일부로서 계산된다. bpos[i]는 suffix의 경계의 시작점의 인덱스를 포함하고 있으며 패턴 P에서 인덱스 i로 싲가한다.

m위치에서 시작하는 suffix  φ 는 경계(border)가 없기때문에 bpos[m]은 m+1로 설정된다. (m은 패턴의 길이)

shift position은 더이상 왼쪽으로 확장 될 수 없는 경계로 얻어진다.

public class GoodSuffix {
    static void preprocess_strong_suffix(int []shift, int []bpos, char []pat, int m) {
        // m is the length of pattern
        int i = m, j = m + 1;
        bpos[i] = j;

        while(i > 0)
        {
        /*if character at position i-1 is not 
        equivalent to character at j-1, then
        continue searching to right of the
        pattern for border */
            while(j <= m && pat[i - 1] != pat[j - 1])
            {
            /* the character preceding the occurrence of t
            in pattern P is different than the mismatching
            character in P, we stop skipping the occurrences
            and shift the pattern from i to j */
                if (shift[j] == 0)
                    shift[j] = j - i;

                // Update the position of next border
                j = bpos[j];
            }
        /* p[i-1] matched with p[j-1], border is found.
        store the beginning position of border */
            i--; j--;
            bpos[i] = j;
        }
    }
}

 예를들어 패턴 P =“ABBABAB”, m = 7

인덱스 5부터 시작하는 "AB"경우, 경계는 없기 때문에 φ(nothing) bpos[5] = 7

bpos[2] = 4이다.

 

2) Case 2에대한 전처리

//Preprocessing for case 2
static void preprocess_case2(int []shift, int []bpos,
                             char []pat, int m)
{
    int i, j;
    j = bpos[0];
    for(i = 0; i <= m; i++)
    {
    /* set the border position of the first character
    of the pattern to all indices in array shift
    having shift[i] = 0 */
        if(shift[i] == 0)
            shift[i] = j;

    /* suffix becomes shorter than bpos[0],
    use the position of next widest border
    as value of j */
        if (i == j)
            j = bpos[j];
    }
}

전처리와 코드에 대한 내용은 아래 reference를 참고 해 보도록 하자. (힘들다) 

 

Reference: 

Do it! 자료구조와 함께 배우는 알고리즘 입문 자바편 (이지스 퍼블리싱)

https://www.geeksforgeeks.org/boyer-moore-algorithm-for-pattern-searching/

Boyer Moore Algorithm for Pattern Searching - GeeksforGeeks

https://www.geeksforgeeks.org/boyer-moore-algorithm-good-suffix-heuristic/

Boyer Moore Algorithm | Good Suffix heuristic - GeeksforGeeks

https://bblackscene21.tistory.com/4?category=911534 

[알고리즘 공부] 보이어 무어 알고리즘 Boyer-Moore Algorithm(문자열 검색 알고리즘)(2)

 

 

https://bblackscene21.tistory.com/3

[알고리즘 공부] 보이어 무어 알고리즘 Boyer-Moore Algorithm(문자열 검색 알고리즘)(1)