보이어-무어 알고리즘 – 좋은 접미사 휴리스틱(Good Suffix Heuristic) 완벽 정리

보이어-무어(Boyer-Moore) 알고리즘에는 또 다른 접근 방식이 있으며, 이를 좋은 접미사 휴리스틱(Good Suffix Heuristic) 방법이라고도 부릅니다. 이 방식에서는 전처리 단계에서 접미사 테이블(suffix table) 형태의 전처리 테이블을 생성합니다.

이 절차에서는 패턴의 마지막 문자부터 부분 문자열 또는 패턴을 검색합니다. 메인 문자열의 부분 문자열이 패턴의 부분 문자열과 일치하면, 일치한 부분의 다른 출현 위치를 찾기 위해 이동합니다. 또한 패턴의 접두사가 메인 문자열의 접미사와 일치하는 경우에도 해당 위치로 이동할 수 있습니다. 어느 경우에도 해당하지 않는다면, 패턴의 전체 길이만큼 이동합니다.

이러한 좋은 접미사 휴리스틱은 나쁜 문자 휴리스틱(Bad Character Heuristic)과 함께 사용되며, 두 기법을 조합하면 단순 비교 방식보다 훨씬 적은 비교 횟수로 문자열을 검색할 수 있습니다. 최선의 경우 검색 속도는 O(n/m)에 도달할 수 있습니다.

입력과 출력

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

알고리즘

fullSuffixMatch(shiftArray, borderArray, pattern)

입력 − 시프트 위치를 저장할 배열, 보더 배열(border array), 검색할 패턴

출력 − 시프트 배열과 보더 배열을 채워 반환

Begin
    n := 패턴의 길이
    i := n
    j := n+1
    borderArray[i] := j

    while i > 0, do
        while j <= n AND pattern[i-1] ≠ pattern[j-1], do
            if shiftArray[j] = 0, then
                shiftArray[j] := j-i;
            j := borderArray[j];
        done

        i와 j를 각각 1씩 감소
        borderArray[i] := j
    done
End

partialSuffixMatch(shiftArray, borderArray, pattern)

입력 − 시프트 위치를 저장할 배열, 보더 배열, 검색할 패턴

출력 − 시프트 배열과 보더 배열을 채워 반환

Begin
    n := 패턴의 길이
    j := borderArray[0]

    for 패턴의 모든 문자 인덱스 'i', do
        if shiftArray[i] = 0, then
            shiftArray[i] := j
        if i = j then
            j := borderArray[j]
    done
End

searchPattern(text, pattern)

입력 − 검색 대상인 메인 텍스트와 패턴

출력 − 패턴이 발견된 인덱스 목록

Begin
    patLen := 패턴의 길이
    strLen := 텍스트의 크기

    for shiftArray의 모든 항목, do
        모든 항목을 0으로 설정
    done

    call fullSuffixMatch(shiftArray, borderArray, pattern)
    call partialSuffixMatch(shiftArray, borderArray, pattern)
    shift := 0

    while shift <= (strLen - patLen), do
        j := patLen - 1
        while j >= 0 and pattern[j] = text[shift + j], do
            j를 1씩 감소
        done

        if j < 0, then
            shift 위치에서 매칭 성공을 출력
            shift := shift + shiftArray[0]
        else
            shift := shift + shiftArray[j+1]
    done
End

예제 코드 (C++)

#include<iostream>
using namespace std;

// 전체 접미사 매칭으로 시프트 배열 계산
void fullSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
    int n = pattern.size();      // 패턴의 길이 구하기
    int i = n;
    int j = n+1;
    borderArr[i] = j;

    while(i > 0) {
        // (i-1)번째와 (j-1)번째 문자가 다르면 오른쪽 탐색 진행
        while(j <= n && pattern[i-1] != pattern[j-1] ) {
            if(shiftArr[j] == 0)
                shiftArr[j] = j-i;     // i에서 j로 패턴 이동
            j = borderArr[j];      // 보더 값 갱신
        }
        i--;
        j--;
        borderArr[i] = j;
    }  
}

// 부분 접미사 매칭 처리
void partialSuffixMatch(int shiftArr[], int borderArr[], string pattern) {
    int n = pattern.size();    // 패턴의 길이 구하기
    int j;
    j = borderArr[0];

    for(int i = 0; i<n; i++) {
        if(shiftArr[i] == 0)
            shiftArr[i] = j;       // 시프트가 0이면 보더 값으로 설정
        if(i == j)
            j = borderArr[j];     // 보더 값 갱신
    }
}

void searchPattern(string mainString, string pattern, int array[], int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int borderArray[patLen+1];
    int shiftArray[patLen + 1];

    for(int i = 0; i<=patLen; i++) {
        shiftArray[i] = 0;     // 시프트 배열을 모두 0으로 초기화
    }

    fullSuffixMatch(shiftArray, borderArray, pattern);
    partialSuffixMatch(shiftArray, borderArray, pattern);
    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;
            shift += shiftArray[0];
        }else {
            shift += shiftArray[j+1];
        }
    }
}

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 << "패턴을 찾은 위치: " << locArray[i]<<endl;
    }
}

실행 결과

패턴을 찾은 위치: 4
패턴을 찾은 위치: 10
패턴을 찾은 위치: 18