나쁜 문자 휴리스틱(Bad Character Heuristic): 보이어-무어 문자열 검색 알고리즘의 핵심 기법

나쁜 문자 휴리스틱(Bad Character Heuristic)은 보이어-무어(Boyer-Moore) 알고리즘을 구성하는 두 가지 접근 방식 중 하나입니다. 다른 하나는 좋은 접미사 휴리스틱(Good Suffix Heuristic)입니다. 이 방법에서는 메인 문자열에서 패턴과 일치하지 않는 문자, 즉 '나쁜 문자(bad character)'를 찾습니다. 불일치가 발생하면 해당 위치가 일치하게 될 때까지 패턴 전체를 이동시키고, 그럴 수 없다면 패턴을 나쁜 문자를 지나쳐 이동시킵니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 최선의 경우 O(m/n), 최악의 경우 O(mn)입니다. 여기서 n은 텍스트의 길이, m은 패턴의 길이를 의미합니다.

입력 및 출력 예시

입력:
메인 문자열: "ABAAABCDBBABCDDEBCABC", 패턴: "ABC"
출력:
패턴 발견 위치: 4
패턴 발견 위치: 10
패턴 발견 위치: 18

알고리즘

1. badCharacterHeuristic(pattern, badCharacterArray)

입력: 검색할 패턴과 위치를 저장할 나쁜 문자 배열

출력: 이후 사용을 위해 나쁜 문자 배열을 채웁니다.

Begin
    n := 패턴 길이
    badCharacterArray의 모든 항목에 대해 반복:
        모든 항목을 -1로 설정
    done

    패턴의 모든 문자에 대해 반복:
        각 문자의 마지막 위치를 badCharacterArray에 저장
    done
End

이 단계에서는 배열을 먼저 -1로 초기화한 뒤, 패턴 내 각 문자가 마지막으로 등장하는 인덱스를 기록합니다. 이렇게 하면 검색 과정에서 특정 문자가 패턴에 존재하지 않거나 마지막 출현 위치만 활용하여 효율적으로 이동 거리를 계산할 수 있습니다.

2. searchPattern(pattern, text)

입력: 검색할 패턴과 메인 텍스트

출력: 패턴이 발견된 위치들

Begin
    patLen := 패턴 길이
    strLen := 텍스트 길이
    badCharacterHeuristic(pattern, badCharacterArray) 호출
    shift := 0

    while shift <= (strLen - patLen), do
        j := patLen - 1
        while j >= 0 이고 pattern[j] = text[shift + j], do
            j를 1 감소
        done
        if j < 0, then
            shift 위치에서 매칭 성공을 출력
            if shift + patLen < strLen, then
                shift := shift + patLen – badCharacterArray[text[shift + patLen]]
            else
                shift를 1 증가
        else
            shift := shift + max(1, j - badCharacterArray[text[shift+j]])
    done
End

검색은 패턴의 끝에서부터 앞쪽으로 비교를 진행합니다. 모든 문자가 일치하면(j < 0) 매칭이 성공한 것이며, 중간에 불일치가 발생하면 나쁜 문자 배열을 참조해 이동 거리를 계산합니다. 이때 max(1, ...) 처리를 통해 이동량이 최소 1은 되도록 보장하여 무한 루프를 방지합니다.

C++ 구현 예제

#include<iostream>
#define MAXCHAR 256
using namespace std;

int maximum(int data1, int data2) {
    if(data1 > data2)
        return data1;
    return data2;
}

void badCharacterHeuristic(string pattern, int badCharacter[MAXCHAR]) {
    int n = pattern.size();              // 패턴 길이 계산
    for(int i = 0; i<MAXCHAR; i++)
        badCharacter[i] = -1;            // 모든 문자 거리를 -1로 초기화

    for(int i = 0; i < n; i++) {
        badCharacter[(int)pattern[i]] = i;   // 배열에 문자의 위치 저장
    }
}

void searchPattern(string mainString, string pattern, int *array, int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int badCharacter[MAXCHAR];           // 나쁜 문자 위치 저장용 배열 생성
    badCharacterHeuristic(pattern, badCharacter);   // 나쁜 문자 배열 채우기
    int shift = 0;

    while(shift <= (strLen - patLen)) {
        int j = patLen - 1;
        while(j >= 0 && pattern[j] == mainString[shift+j]) {
            j--;    // 패턴과 메인 문자열의 문자가 일치하면 j 감소
        }

        if(j < 0) {
            (*index)++;
            array[(*index)] = shift;

            if((shift + patLen) < strLen) {
                shift += patLen - badCharacter[mainString[shift + patLen]];
            }else {
                shift += 1;
            }
        }else {
            shift += maximum(1, j - badCharacter[mainString[shift+j]]);
        }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int index = -1;
    searchPattern(mainString, pattern, locArray, &index);

    for(int i = 0; i <= index; i++) {
        cout << "Pattern found at position: " << locArray[i]<<endl;
    }
}

실행 결과

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

위 실행 결과를 보면 패턴 "ABC"가 메인 문자열 "ABAAABCDBBABCDDEBCABC" 내에서 세 번 발견되었음을 확인할 수 있습니다. 나쁜 문자 휴리스틱은 불일치 정보를 활용해 한 번에 여러 칸씩 건너뛸 수 있기 때문에, 단순 완전 탐색 방식보다 실질적으로 더 빠른 문자열 검색 성능을 제공합니다.