[Algorithm] C - Boyer-Moore 문자열 검색 알고리즘

요약

시간 복잡도 평균 : O(n / m) / 최악 : O(n)

• 검색하고자 하는 패턴의 마지막 문자부터 앞쪽으로 검사를 진행
• 일치하지 않는 문자가 있을 경우 Skip 표에 따라 패턴을 옮겨 가면서 검사
• 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표를 만들어야 함
• 문자열의 커서는 앞에서 뒤로, 패턴의 커서는 뒤에서 앞으로 역방향으로 검사

Boyer-Moore 알고리즘이란

Boyer-Moore 알고리즘이란 검색하고자 하는 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는
문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정하는 고리즘이다.

Booyer-Moore 법은 Brute-Froce나 KMP 보다 효율이 더 우수하기 때문에 널리 사용되는 문자열 검색 알고리즘이다.
R.S Boyer, J.s Moore가 만든 알고리즘으로 그의 이름을 따 만들어졌다.

아래 예제는 텍스트 "ABCXDEZCABACABAC"에서 패턴 "ABAC"를 검색하는 예제이다.

먼저 텍스트와 검색할 패턴의 첫 번째 문자를 겹쳐보고 검색할 패턴의 마지막 문자 'C'를 검사한다.
텍스트의 'X'는 패턴에 없으므로, 이 문자는 패턴에 아예 없는 문자이기 때문에 패턴을 한 칸씩 뒤로 옮겨도 일치하지 않는다.

이와 같이 텍스트 안에서 패턴에 들어 있지 않은 문자를 찾으면 해당 위치까지의 문자는 건너 뛸 수 있다.

만약 패턴을 옮기는 과정을 생략하면 아래와 같은 상태가 된다.
이 상태는 패턴의 마지막 문자 'C'와 텍스트의 'C'가 일치하기 때문에 패턴을 1칸 옮길 수 있다.

패턴의 마지막 문자 'C'는 텍스트와 일치하고 있다. 다시 'C'의 이전 문자 'A'를 검사하면 'Z'와 다른 문자임을 알 수 있다.

패턴을 1칸, 2칸 옮기더라도 텍스트의 'Z' 문자는 검사할 패턴의 문자열에 존재하지 않는 것을 확인할 수 있다.

이러면 또 다시 검색할 패턴을 한꺼번에 3칸 옮겨 다시 검사를 시작한다.

이렇게 패턴의 길이를 n이라고 할 때 현재 검사하고 있는 텍스트의 문자 위치로부터 다음에 검사할 패턴의 마지막 문자 위치가 n만큼 떨어질 수 있도록 패턴을 옮기면 된다. 이것이 Boyer-Moore 알고리즘을 적용하여 문자열을 검색하는 방법이다.

이렇게 옮긴 다음 다시 검사를 시작해도 텍스트의 'A'와 패턴의 마지막 문자 'C'를 비교한다.
하지만 문자 'A'는 패턴의 1, 3번째 인덱스에 들어있다.
이런 경우 두 번째 작업과 같이 패턴의 뒤쪽에 위치한 'A'가 텍스트와 위 아래로 겹치도록 패턴을 1칸만 옮긴다.

패턴의 검색은 문자 뒤에서부터 검색해야 하므로 만약 네 번째 작업과 같이 패턴을 3칸 옮기면 안된다.

결론적으로 패턴을 1칸만 옮기게 되면 아래 그림과 같은 상태가 되고, 패턴의 마지막 위치에서 순서대료 문자를 비교하면 모두 일치하므로 검색 성공이다.

Skip 표 만들기

Boyer-Moore 알고리즘도 KMP 알고리즘과 같이 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표를 만들어야 한다.
이 표를 Skip 표(건너뛰기 표)라고 한다.

패턴 문자열의 크기가 n일 때 옮길 크기는 아래와 같은 방법으로 결정한다.

패턴에 들어 있지 않은 문자를 만난 경우

1. 패턴을 옮길 크기는 n이며, 마지막 문자부터 처음 문자까지 하나하나 비교한다.
2. 텍스트의 문자('X')와 검색할 패턴의 문자("ABAC")가 일치하지 않으므로 패턴 4칸을 뒤로 옮긴다.

패턴에 들어 있는 문자를 만난 경우

1. 마지막에 나오는 위치의 인덱스가 k이면 패턴을 옮길 크기는 n - k - 1이다.
2. 검색할 패턴의 뒷 문자부터 일치하는 문자일 때까지 검사하여 마지막 인덱스를 기준으로 패턴을 옮긴다.
3. 같은 문자가 패턴 안에 중복해서 들어있지 않다면(예를 들어 "ABAC" 에서 C는 1개만 존재) 패턴을 옮길 크기는 N이다.

아래 표는 표 작성 규칙에 의해 만든 표다.

 

 

예제 코드

#include <stdio.h>
#include <string.h>

// #include <limits.h> 함수에도 정의되어 있음
#define UCHAR_MAX 255

int BoyerMoore(const char *text, const char *partition);

int main() 
{
    int index;
    
    // 검색할 문자열
    char s1[256];
    
    // 찾을 패턴
    char s2[256];
    
    printf("텍스트 : ");
    scanf("%s", s1);
    
    printf("패턴 : ");
    scanf("%s", s2);
    
    index = BoyerMoore(s1, s2);
    
    if(index == -1) {
        printf("텍스트에 패턴이 없습니다.\n");
    }
    else {
        printf("%d 번째 문자부터 동일합니다.\n", index + 1);
    }

    return 0;
}

int BoyerMoore(const char *text, const char *partition)
{
    // 검색할 텍스트 커서
    int textCursor;
    
    // 검색할 텍스트 문자열 길이
    int textLength = strlen(text);
    
    // 찾을 패턴 커서
    int partitionCursor;
    
    // 찾을 패턴 문자열 길이
    int partitionLength = strlen(partition);
    
    // Skip 표
    int skip[UCHAR_MAX + 1];
    
    // Skip 표 만들기
    for(textCursor = 0; textCursor <= UCHAR_MAX; textCursor++) {
        // Skip 표에 검색할 패턴 문자열 길이 할당
        skip[textCursor] = partitionLength;
    }
    
    for(textCursor = 0; textCursor < partitionLength - 1; textCursor++) {
        // 패턴 중 맨 마지막 패턴 제외 표 만듬
        skip[partition[textCursor]] = partitionLength - textCursor - 1;
    }

    // 마지막 문자열까지 검사
    while(textCursor < textLength) {
        // 검색할 패턴의 마지막 문자부터 검사하기 위해 마지막 인덱스 값 할당 (n - 1)
        partitionCursor = partitionLength - 1;
        
        // 비교하고 있는 문자열과 패턴이 동일할 때
        while(text[textCursor] == partition[partitionCursor]) {
            
            // 패턴의 맨 뒤에서 맨 앞까지 모두 검색을 끝났을 때
            if(partitionCursor == 0) {
                return textCursor;
            }
            
            // 앞 문자 비교
            partitionCursor--;
            textCursor--;
        }
        
        // 문자열 커서를 패턴의 일치 여부에 따라 뒤로 옮김
        textCursor += (skip[text[textCursor]] > partitionLength - partitionCursor) ? skip[text[textCursor]] : partitionLength - partitionCursor;
    }
    
    return -1;
}

 

실행 결과

텍스트 : ABEGWQWESDGEETT
패턴 : GEE
11 번째 문자부터 동일합니다.

 

 

https://github.com/JeHeeYu/Algorithm/tree/main/String/Boyer-Moore

GitHub - JeHeeYu/Algorithm: 알고리즘 개념 및 문제 풀이

 

 

 

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문: C 언어 편