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

참고도서: 자료구조와 함께 배우는 알고리즘 입문 (자바편), Bohyoh Shibata 지음

 

Boyer-Moore알고리즘은 패턴의 마지막 문자부터 역순으로 검사를 진행하면서 일치하지 않는 문자가 나타나면 미리 준비된 표(skip table)에 따라 건너뛸 위치를 정한다.

아래는 알고리즘의 검색과정을 단순화해서 표현한 엑셀 표이다. 찾고있는 패턴 ABAC는 원본의 마지막에 위치해있다.

그림1. Boyer-Moore 알고리즘의 수행과정 예시

ABCXDEZCACACABAC 라는 원본 문자열에서 ABAC 패턴을 검색해 찾는 과정이다. 검색에 성공하기 까지 총 5회의 이동을 수행했다. 이 알고리즘의 핵심은 건너뛸(skip) 거리를 어떻게 정의하는가이다.

원본의 문자열 길이가 총 16인데, 요소를 하나씩 비교하지 않고 어떤 경우에는 4칸씩 건너 뛴 것을 볼 수 있다. 이런 스킵 과정 덕분에 이 알고리즘은 매우 적은 횟수로 검색을 수행할 수 있다. 위의 전체 과정을 좀 더 자세히 보자.

 

그림2. 첫 비교 후 패턴의 이동 과정

앞에서 언급한 것 처럼 이 알고리즘은 역순으로 비교를 수행한다. 따라서 패턴의 마지막 요소인 C를 원본의 X와 비교한다. 일치하지 않으므로 나머지 요소를 비교할 필요가 없다. 그럼 이동해야 한다. 그런데 중요한 것은 X는 패턴 안에 들어있지 않은 문자라는 점이다. 이럴 경우 나머지 요소인 A, B, A또한 X와 비교할 필요가 없으니 패턴의 위치를 X 다음 위치로 이동하면 불필요한 연산을 생략할 수 있다. 여기서 기억해야할 점은 패턴 안에 어떤 문자가 있고 어떤 문자는 없는지를 검사를 수행하기 전에 미리 알고 있어야 한다는 것이다. 그러면 이제 이동해서 다시 패턴의 마지막 요소인 C부터 비교할 차례이다.

그림3. 첫 번째 이동 후 비교 과정

C는 일치하는 것을 확인했다(파란색으로 표시). 그 다음은 패턴의 왼쪽을 검사한다. A는 Z와 일치하지 않는다. 그러니 나머지 요소도 더이상 비교할 필요가 없다. 그런데 이번에도 Z는 패턴에 없는 요소이다. 그럼 이번에는 얼마나 건너뛰어야 할까? 이전의 경우처럼 네 칸을 건너뛰면 안된다. 왜 그런지 아래와 같은 경우를 생각해보자.

그림4. 참고 예시 (잘못된 경우)

만약 위와 같은 경우에 네 칸을 건너뛰면 문제가 생긴다. 패턴이 일치하는 위치인 (7, 8, 9, 10)를 건너뛰어버리고 ACCB와 비교하게 된다. 어떻게 해야 될까? 이 경우 네 칸이 아닌 세 칸을 이동하면 검색에 성공한다. 

 

다시 돌아가서 그림3을 보자. 패턴 전체가 네 칸을 이동하지 않고 세 칸만 이동했다. 그런데 패턴의 끝이 아닌 현재 검사를 수행하고 있는 위치인 6을 기준으로 봤을 때에는 네 칸을 이동한 것으로 볼 수 있다. 즉 비교를 수행하는 과정에서 패턴에 존재하지 않는 요소를 만나면 해당 위치를 기준으로 패턴의 요소 수 만큼 이동하면 된다.

이제 다음 이동한 위치에서 다시 패턴의 마지막 요소부터 비교를 할 차례이다. (그림5)

그림5. 두 번째 이동 후 비교

첫 요소인 C와 A가 일치하지 않기 때문에 더이상 볼 필요가 없다. 그러면 이동해야 한다. A는 패턴 안에도 있는 요소이다. 이 경우 A를 원본의 A와 맞춘 후에 다시 비교를 수행해야 한ㄷ. 그러려면 오른쪽으로 한 칸만 이동하면 된다. 

그림6. 세 번째 이동 후 비교

이번에는 두 요소는 일치했으나 세 번째 요소인 B와 C가 일치하지 않는다. C는 이미 앞에서 비교를 했고, 패턴 안에는 더이상 다른 C가 남아있지 않다. 이런 경우에는 원본의 C는 패턴의 어떤 요소하고도 더 이상 비교할 필요가 없기 때문에 건너뛰면 된다. 따라서 원본의 C 위치인 9를 기준으로 패턴을 네 칸 이동한다. 여기서 네 칸을 이동하는 이유는 완전히 건너뛰기 위함이다. 4는 요소의 개수이다.

그림7. 네 번째 이동 후 비교

첫 요소부터 불일치한다. 이동해야 한다. 원본의 요소 B는 패턴 안에 존재하고 아직 검사를 하지 않았다. 그렇기 때문에 패턴의 B와 위치를 맞추기 위해서는 두 칸을 이동해야 한다.

그림8. 다섯 번째 이동 후 검색 성공

비로소 모든 요소가 일치한다. 다섯 번의 이동 후 검색에 성공했다. 알고리즘이 어떻게 작동하는지에 대한 과정을 단순하게 엑셀표로 표현했다. 그렇다면 위와 같은 이동거리를 어떻게 식으로 표현할 수 있을까?

 

# 패턴에 없는 문자를 만났을 때 이동할 거리 = n

우선 패턴 문자열의 길이를 n이라고 하자. 이동거리가 n인 경우는 원본 문자열의 요소가 패턴에 들어있지 않은 경우이다. 이 때 현재 검사를 수행중인 위치를 기준으로 n만큼의 거리에서 다시 검사를 수행하면 된다.

그림9. 패턴에 존재하지 않는 요소를 만났을 때

위에서 살펴본 과정을 다시 보자. 패턴의 A와 원본의 Z가 일치하지 않는데, Z는 패턴에 들어있지 않은 요소이다. 이때 현재 검사하고 있는 위치는 6이고 패턴의 길이 n는 4이다. 6을 기준으로 4만큼 이동한 위치는 10이다. 10에서부터 다시 검사를 수행한다면 위와 같은 모습이 된다.

 

# 패턴에 들어있는 문자를 만났을 때 이동할 거리

1. 패턴 안에 하나만 존재하면서 마지막 위치에 있는 문자를 만났을 때 이동거리 = n

그림10. C가 일치하지 않아서 위치 2를 기준으로 4만큼의 거리에 있는 6으로 패턴이 이동한다. 

위의 경우를 살펴보자. 패턴의 요소 C, B는 검사결과 일치하지만 A는 불일치한다. 원본의 문자는 C이다. C는 패턴에서 마지막에 위치해 있으면서 하나만 존재한다. 이럴 경우 해당 위치를 기준으로 n만큼 이동한다.

 

2. 그 외에 패턴 안에 존재하는 문자를 만났을 때 이동거리 = n - k - 1

k는 패턴 안에서 문자의 위치이다. 만약 문자가 두 개 이상 존재할 경우 가장 뒤쪽에 있는 문자의 위치로 한다. <그림5>가 이 경우에 해당한다. 이 때 만난 문자 A는 패턴 안에 두 개가 존재한다. 그 중 뒤 쪽에 있는 A의 배열상 위치는 2이다. n은 4이기 때문에 4 - 2 -1 = 1이 된다.

 

* 만약 패턴 안에 두 개의 문자가 존재하는데 그 중 하나가 마지막에 위치해있는 경우 (아래)

그림11.

이럴 경우 k는 는 3이 아닌 1이 된다. 두 개의 A중 뒤쪽에 있는 A가 마지막에 위치해있다. 이럴 경우에는 마지막에 위치한 A를 제외하고 그 다음 마지막에 위치한 A의 위치를 k로 한다. 따라서 n - k - 1 = 4 - 1 - 1, 즉 2가 된다.

패턴에서 마지막에 위치한 문자는 이동거리를 계산할 때 고려하지 않는다고 보면 된다.

 

그럼 이제 이 식을 코드로 표현할 차례이다. 코드로 스킵 테이블을 먼저 만들어야 한다. 그래야 검색을 하면서 불일치하는 문자를 만났을 때 테이블을 참고해서 몇 칸을 이동할 지 알 수 있다.

int pt;                     // txt 커서
int pp;                     // pat 커서
int txtLen = txt.length();  // txt의 문자 개수
int n = pat.length();  // pat의 문자 개수
int[] skip = new int[Character.MAX_VALUE + 1]; //  skip table (건너뛰기 표)

// 건너뛰기 테이블(skip table) 만들기
for (pt = 0; pt <= Character.MAX_VALUE; pt++) skip[pt] = n;
for (pt = 0; pt < n - 1; pt++) {
    skip[pat.charAt(pt)] = n - pt - 1; // pt == patLen - 1
}

 위 코드를 보면 skip 표를 구성하는 코드는 단 두 줄의 for문으로 이루어져있다. 첫 번째 for문에서는 skip[]의 모든 요소에 n을, 즉 패턴의 길이를 넣어준다. 두 번째 for문은 패턴에 들어있는 문자에 해당하는 요소만 skip[]에서 선택하여 값을 넣어준다. 단순화 시켜보면 두 번째 for문에서 새로 값을 지정해주는 문자를 제외하고는 skip[]의 모든 값은 n이다.

 

그런데 두 번째 for문을 자세히 보면 pt의 증가 범위가 n - 1보다 작아야 한다고 되어 있다. skip[n - 1]의 요소는 새로 값을 넣어주지 않기 때문에 해당 요소의 값은 첫 번째 for문에서 지정한 n이 될 것이다. 그러나 해당 요소(n-1)가 한 개 이상 더 존재할 경우에는 n - 1위치의 요소를 제외하고 가장 오른쪽에 있는 요소의 위치를 기준으로 값이 저장될 것이다. 예를 들어 패턴의 요소가 {A, B, C, B}와 같은 경우 스킵테이블에서 B의 값은 n-k-1의 식에 따라 2이다. 하지만 {A, A, C, B}와 같을 경우 스킵테이블에서 B의 값은 n의 값인 4이다. 설명이 복잡했지만 코드는 단순하다. 

 

이제 skip[]에 들어있는 값들은 앞으로 비교연산을 수행할 때 두 개의 문자가 불일치할 경우 오른쪽으로 얼마만큼 이동할지를 참고하는 표의 역할을 수행할 것이다.

 

아래는 메서드의 전체 코드다.

static int bmMatch(String txt, String pat) {
    int pt;                     // txt 커서
    int pp;                     // pat 커서
    int txtLen = txt.length();  // txt의 문자 개수
    int n = pat.length();       // pat의 문자 개수
    int[] skip = new int[Character.MAX_VALUE + 1]; //  skip table (건너뛰기 표)

    // 건너뛰기 테이블(skip table) 만들기
    for (pt = 0; pt <= Character.MAX_VALUE; pt++) skip[pt] = n; 
    for (pt = 0; pt < n - 1; pt++) skip[pat.charAt(pt)] = n - pt - 1; 

    //검색
    while (pt < txtLen) {
        pp = n - 1;

        while (txt.charAt(pt) == pat.charAt(pp)) {
            if (pp == 0) return pt; // 검색 성공
            pp--;
            pt--;
        }
        pt += (skip[txt.charAt(pt)] > n - pp) ? skip[txt.charAt(pt)] : n - pp;
    }
    return -1; // while 문이 종료되면 검색 실패
}