문자열 검색 알고리즘 : Boyer Moore - Bad Character Heuristic 알아보기
boyer-moore 알고리즘은 문자열 검색 알고리즘으로써 패턴의 전처리로 얻은 정보를 가지고 패턴을 가능한 많이 이동시켜 텍스트와 비교 횟수를 줄입니다.
boyer-moore 알고리즘은 보통 상황에서 문자열은 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용합니다.
그래서 기존 패턴 검색 알고리즘과 달리 boyer moore 알고리즘은 역방향 접근 방식을 사용합니다.
패턴의 마지막 문자부터 시작하여 오른쪽에서 왼쪽으로 비교를 시작합니다.
이동 위치를 정하기 위해 boyer-moore 알고리즘은 두 가지 휴리스틱을 사용합니다.
- Bad Character Heuristic
- Good Suffix Heuristic
불일치 시 이 두 휴리스틱에서 제공하는 오프셋 중 가장 큰 오프셋을 사용해 패턴을 이동시킵니다.
이번 글에서는 Bad Character Heuristics을 알아보도록 하겠습니다.
Bad Character Heuristics
Bad Character는 패턴의 현재 문자와 일치하지 않는 텍스트의 문자를 말합니다.
Bad Character Heuristics은 Bad Character 발생 시 패턴을 이동시키기 위한 오프셋을 제공합니다.
Bad Character 발생 시 두 가지 상황이 있고 Bad Character Heuristics는 각 상황에 맞는 오프셋을 제공합니다.
Case 1. Bad Character가 패턴에 존재할 때
Bad Character와 같은 패턴 문자 중 가장 오른쪽 문자에 맞춰지도록 패턴을 이동합니다. (그림 1)
Bad Character와 같은 패턴 문자 중 가장 오른쪽에 있는 문자가 Bad Character보다 뒤에 있다면 뒤로 이동하는 일이 발생하게 됩니다.
이런 경우 한 칸만 이동시켜 줍니다. (그림 2)
Case2. Bad Character가 패턴에 존재하지 않을 때
패턴을 bad character 다음 위치로 이동합니다.
구현
구현에는 전처리 단계와 검색 단계로 나뉩니다.
전처리 (preprocessing) 단계
Bad Character 발생 시 스킵을 위한 오프셋을 저장하고 있는 badChar[] 배열을 만들기 위한 전처리 작업이 필요합니다.
badChar[]는 모든 알파벳에 대한 위치 정보를 저장하고 있는 테이블입니다.
패턴 P에 존재하지 않는 문자들에 대해서는 -1을 저장하며 중복되는 문자들에 대해서는 가장 오른쪽에 있는 문자의 위치정보를 저장합니다.
#define ALPH_LEN 256
void badCharHeuristic(int badchar[], char pat[], int patLen){
int i = 0;
for(i = 0; i < ALPH_LEN; ++i){
badChar[i] = -1; // -1 로 초기화
}
for(i = 0; i < patLen; ++i){
badChar[(int)pat[i]] = i; // 중복되는 문자들에 대해서는 가장 오른쪽에 있는 문자를 저장
}
}
패턴 AABDB에 대한 badChar [] 테이블을 만들면 다음과 같습니다.
badChar[] 테이블은 bad charater 발견 시 패턴을 이동시키는 데 사용됩니다.
문자열 검색 단계
문자열 검색은 오른쪽에서 왼쪽으로 패턴과 비교합니다.
패턴을 찾았다면 패턴이 이동한 정보를 출력하고 텍스트에 남아있는 패턴을 찾기 위해 패턴을 이동시킵니다.
패턴을 찾지 못했다면 Bad Character Heuristics에서 제공하는 오프셋만큼 패턴을 이동시킵니다.
#define ALPH_LEN 256
void search (char txt[], char pat[]) {
int m = strlen(pat);
int n = strlen(txt);
int badchar[ALPH_LEN];
// 전처리 단계
badCharHeuristi(badchar, pat, m);
int s = 0 // 텍스트에 대한 패턴을 이동시키기 위한 변수
// 문자열 검색 단계
while(s <= (n - m)) {
int j = m - 1;
// 텍스트와 패턴을 오른쪽에서 왼쪽으로 비교
while (j >=0 && pat[j] == txt[s+j])
j--;
// 텍스트에서 패턴을 발견했다면
if (j < 0) {
printf("pattern occurs at shift = %d\n", s);
// 비교할 텍스트가 남아있다면 다음 위치로 패턴을 이동시킴
if (s+m < n)
s += m - badchar[txt[s+m]]
else // 모든 텍스트와 비교했다면 종료 (while문을 빠져나오기 위해 1을 더함.)
s += 1
}
else { // 텍스트에서 패턴을 발견하지 못했다면
// skip하기 위한 offset을 가져옴
int skip = j - badchar[txt[s+j]];
if (skip < 0) {
// bad character와 일치하는 패턴 문자중 가장 오른쪽에 있는 문자의 위치가
// bad character 뒤에 있다면 한칸만 이동 (그림 2)
s += 1;
}
else {
// bad character와 일치하는 패턴이 없거나 (그림 3)
// 일치하는 패턴 문자중 가장 오른쪽에 있는 문자의 위치가 bad character 앞에 있다면 (그림 1)
// offset 만큼 이동
s += skip
}
}
}
}Input & Output
Input:
txt[] = "ABAAABCD"
pat[] = "ABC"
Output:
pattern occurs at shift = 4성능
m : 패턴 길이, n: 텍스트 길이
Worst case
Bad Character Heuristic의 worst case는 모든 텍스트의 문자가 패턴과 일치할 때 발생하고 O(mn) 시간이 걸립니다.
ex)
txt[] = "AAAAAAAA"
pat[] = "AAA"
Best case & Average case
평균적으로 O(n/m) 시간이 걸리고, 종종 m만큼 이동하는 경우가 있기 때문입니다. (그림 3)
best case는 텍스트와 패턴의 모든 문자가 다를 때 발생합니다.
ex)
txt[] = "AAAAAAAA"
pat[] = "BBB"
