보이어 무어 알고리즘
보다 빠르게 텍스트 안에서 주어진 패턴의 문자열을 찾는 데는 많은 연구가 이루어져 왔습니다. 가장 직관적으로는 반복문 2개를 이용해 텍스트의 인덱스 하나하나마다 패턴과 일치하는지 찾는 방법이 있습니다. 이 경우 의 큰 복잡도를 가집니다. 따라서 실제 문자열 패턴을 찾기 위해서는 KMP, 보이어 무어 등 보다 효율적인 알고리즘을 이용합니다. 이 포스트에서는 그 중 보이어 무어 알고리즘을 알아보고 직접 C 코드로 작성해보겠습니다.
보이어 무어 알고리즘은 텍스트에 대해 패턴의 오른쪽부터 일치여부를 탐색합니다. 아래 그림은 오른쪽부터 탐색한다는 것이 어떤 의미인지를 보여주고 있습니다.
불일치 지점으로부터 패턴을 얼마나 이동시킬지가 알고리즘의 효율을 결정짓습니다. 보이어 무어 알고리즘은 다음 두 방법을 통해 이동거리를 정합니다. heuristics 은 영어로 발견법을 의미합니다.
- Bad character heuristics
- Good suffix heuristics
Bad character heuristics
Bad character heuristics 는 각 character에 대해 character 가 패턴에 포함되어 있다면 포함된 위치 중 가장 오른쪽 인덱스를 저장해서 이동에 사용하는 방법입니다. 예를 들면 패턴 cabab 는 다음과 같이 저장할 수 있습니다.
| a | b | c | d | ... |
|---|---|---|---|---|
| 3 | 4 | 0 | -1 | -1 |
위 테이블에서 알파벳 a, b, c 는 각각의 패턴 속 가장 오른쪽 인덱스와 매칭되고 있습니다. 그리고 패턴에서 발견할 수 없는 character 는 모두 -1 로 저장합니다. 이는 이동거리를 계산하는데 이용됩니다. 위 테이블을 이용해 패턴의 이동을 직접 살펴보겠습니다.
위 그림에서 패턴의 이동거리는 2입니다. 이는 불일치 지점의 인덱스 4 에서 오른쪽으로부터 처음으로 b가 나오는 인덱스 2 를 뺀 값입니다. 만약 패턴에 텍스트의 character 가 없다면 해당 인덱스로 부터 -1 를 뺌으로서 패턴 전체를 불일치 지점 다음 위치로 이동시킵니다. 1바이트 character 하나 하나의 일치 여부를 판단해 이동하므로 유니코드에 대해서도 똑같이 적용됩니다.
텍스트의 , 패턴의 번째 인덱스에서 불일치가 발생했을 때 텍스트의 번째 character 가 패턴의 보다 큰 지점, 즉 패턴의 오른쪽에 위치한다면 패턴이 뒤로 후퇴하는 일이 발생합니다. 아래 그림은 후퇴하는 상황을 보여주고 있습니다. 이동거리는 불일치 지점의 인덱스 2 에서 b 의 가장 오른쪽 인덱스 4 를 뺀 -2 입니다.
위와 같은 이유로 보이어 무어 알고리즘은 Bad character heuristics 와 Good suffix heuristics 를 혼합해서 사용합니다.
Good suffix heuristics
Good suffix heuristics 은 대칭이 있는 위치를 기억해두고 이동거리를 결정합니다. 이 때 다음 두가지 상황을 고려합니다.
- 완벽하게 같은 대칭이 있는 위치로 이동
- 부분적으로 같은 대칭이 있는 위치로 이동
패턴 내의 대칭에 대해 간단히 살펴 보겠습니다. 문자열 bab 는 인덱스 0과 2가 대칭입니다. 문자열 abcab 는 인덱스 0~1 과 3~4 가 대칭입니다. 문자열 babab 는 인덱스 0~2 와 2~4 가 대칭입니다. 문자열 cbabab 는 인덱스 1~3 와 3~5 가 대칭입니다.
아래 그림은 완벽하게 같은 대칭이 있는 위치까지 이동하는 경우를 보여주고 있습니다.
만약 알고리즘이 Bad character heuristics 만 사용했다면 위와 같은 이동을 바랄 수 없었습니다. 만약 같은 대칭이 없는 경우 다음과 같이 패턴의 길이만큼 이동합니다.
이번에는 부분적으로만 같은 대칭이 있는 경우를 생각해보겠습니다.
만약 불일치 지점 이후의 문자열 bab 의 대칭이 없어 패턴의 길이만큼 이동한다면 알고리즘이 실패했을 것입니다.
C 코드
이제 Bad character heuristics 와 Good suffix heuristics 를 위해 패턴에 대한 전처리 과정을 코드로 작성해보겠습니다. 먼저 Bad character heuristics 입니다.
void make_bc_table(size_t *table, const char *pat, size_t len)
{
size_t i;
i = 0;
while (i < CHARACTER_TABLE_SIZE)
// 원래는 -1 이 할당되어야 하나 size_t 타입을 맞추기 위해 len 으로 설정
table[i++] = len;
i = 0;
while (i < len)
{
table[(size_t)(pat[i])] = i;
i++;
}
}Bad character heuristics 에 대한 전처리 과정은 간단합니다. 우선 테이블의 모든 요소에 대해 값을 len 으로 초기화합니다. 이 때 테이블의 사이즈를 결정하는 매크로 CHARACTER_TABLE_SIZE 는 1 바이트에서 담을 수 있는 수의 개수인 256 입니다. 초기화를 마친 뒤 패턴 pat 의 각 character 의 인덱스를 테이블에 저장합니다. 이 때 패턴의 왼쪽부터 반복문이 시작되므로 가장 오른쪽 character 의 인덱스가 최종적으로 저장됩니다. 한편 초기화 시에 -1 을 저장해야 맞으나 table 어레이의 특성상 패턴의 인덱스의 최대값인 패턴의 길이 - 1 만큼의 8바이트 size_t 타입을 저장하게 되므로 size_t 에서 다룰 수 없는 -1 대신 패턴의 인덱스를 넘어서는 특수한 수 len 을 저장하였습니다.
Good suffix heuristics 의 전처리 과정은 코드로 작성했을 때 다소 직관적이지 않으므로 직접 코드를 따라가보며 변수에 할당되는 값들을 적어보는게 좋습니다. 변수 pos_table 은 대칭 문자열이 시작되는 인덱스를 저장합니다. 변수 shift_table 은 실제 탐색과정에서 쓰게 될 이동거리를 저장합니다.
void make_gs_table(size_t *shift_table, const char *pat, size_t len)
{
size_t pos_table[len];
size_t i;
size_t j;
i = len;
j = i + 1;
pos_table[i] = j;
while (i > 0)
{
while (j <= len && pat[i - 1] != pat[j - 1])
{
if (shift_table[j] == 0)
shift_table[j] = j - i;
j = pos_table[j];
}
pos_table[--i] = --j;
}
j = pos_table[0];
while (i <= len)
{
if (shift_table[i] == 0)
shift_table[i] = j;
if (i++ == j)
j = pos_table[j];
}
}위 코드의 첫번째 반복문은 완벽하게 같은 대칭에 대한 전처리 과정입니다. 패턴 cabab 에 대해 첫번째 반복문을 마친 뒤 다음과 같은 결과를 얻습니다.
| c | a | b | a | b | |
|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 |
| pos_table | 5 | 3 | 5 | 5 | 5 |
| shift_table | 2 |
인덱스 3의 문자 a 에 대응하는 shift_table 의 값 2가 패턴 내 대칭까지의 이동거리를 말해줍니다. 두번째 반복문 이후엔 다음 값들을 얻습니다.
| c | a | b | a | b | |
|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 |
| pos_table | 5 | 3 | 5 | 5 | 5 |
| shift_table | 5 | 5 | 5 | 2 | 5 |
shift_table 의 값은 이전의 character 가 불일치 지점일 때 이동해야할 거리를 알려줍니다. 예를 들어 인덱스 2의 문자 b 가 텍스트와 불일치 했다면 2만큼 패턴을 이동시킵니다.
아래는 패턴 abcab 에 대한 결과 입니다.
| a | b | c | a | b | |
|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 |
| pos_table | 3 | 4 | 5 | 5 | 5 |
| shift_table | 3 | 3 | 3 | 3 | 5 |
위의 예시는 특히 인덱스 1 지점에서 불일치 했을 때 3만큼 이동함으로서 부분적으로 같은 대칭이 있는 지점의 정보를 이용합니다.
두 개의 heuristics 를 이용한 탐색
보이어 무어 알고리즘에 대한 두 개의 탐색법을 모두 살펴보았습니다. 아래 코드는 텍스트와 패턴이 불일치했을 때 두 방법이 제시하는 이동거리 중 더 큰 값을 선택함을 보여줍니다.
char *search(const char *text, const char *pat,\
size_t *bc_table, size_t *shift_table)
{
size_t i;
size_t j;
size_t text_len;
size_t pat_len;
text_len = strlen(text);
pat_len = strlen(pat);
i = 0;
if (text_len < pat_len)
return (NULL);
while (i <= text_len - pat_len)
{
j = pat_len;
while (j > 0 && pat[j - 1] == text[i + (j - 1)])
j--;
if (j == 0)
return ((char *)text + i);
if (bc_table[(size_t)(text[i + j])] != pat_len)
i += MAX(shift_table[j],\
j - bc_table[(size_t)(text[i + j])]);
else
i += MAX(shift_table[j], j);
}
return (NULL);
}
전체 코드는 아래와 같습니다.
#include <stdlib.h>
#include <string.h>
#define CHARACTER_TABLE_SIZE 256
#define MAX(a, b) ((a) > (b)) ? (a) : (b)
void make_bc_table(size_t *table, const char *pat, size_t len)
{
size_t i;
i = 0;
while (i < CHARACTER_TABLE_SIZE)
table[i++] = len;
i = 0;
while (i < len)
{
table[(size_t)(pat[i])] = i;
i++;
}
}
void make_gs_table(size_t *shift_table, const char *pat, size_t len)
{
size_t pos_table[len];
size_t i;
size_t j;
i = len;
j = i + 1;
pos_table[i] = j;
while (i > 0)
{
while (j <= len && pat[i - 1] != pat[j - 1])
{
if (shift_table[j] == 0)
shift_table[j] = j - i;
j = pos_table[j];
}
pos_table[--i] = --j;
}
j = pos_table[0];
while (i <= len)
{
if (shift_table[i] == 0)
shift_table[i] = j;
if (i++ == j)
j = pos_table[j];
}
}
void preprocess(size_t *bc_table, size_t *shift_table,\
const char *pat, size_t len)
{
make_bc_table(bc_table, pat, len);
make_gs_table(shift_table, pat, len);
}
char *search(const char *text, const char *pat,\
size_t *bc_table, size_t *shift_table)
{
size_t i;
size_t j;
size_t text_len;
size_t pat_len;
text_len = strlen(text);
pat_len = strlen(pat);
i = 0;
if (text_len < pat_len)
return (NULL);
while (i <= text_len - pat_len)
{
j = pat_len;
while (j > 0 && pat[j - 1] == text[i + (j - 1)])
j--;
if (j == 0)
return ((char *)text + i);
if (bc_table[(size_t)(text[i + j])] != pat_len)
i += MAX(shift_table[j],\
j - bc_table[(size_t)(text[i + j])]);
else
i += MAX(shift_table[j], j);
}
return (NULL);
}
char *boyer_moore(const char *text, const char *pat)
{
size_t pat_len;
size_t bc_table[CHARACTER_TABLE_SIZE];
size_t *shift_table;
char *loc;
loc = NULL;
pat_len = strlen(pat);
shift_table = memalloc(sizeof(size_t) * (pat_len + 1));
if (shift_table == NULL)
return (NULL);
preprocess(bc_table, shift_table, pat, pat_len);
loc = search(text, pat, bc_table, shift_table);
free(shift_table);
return (loc);
}
