[Boyer-Moore] 문자열 탐색 ! 보이어-무어 알고리즘(feat.cpp)

 

 

목차

• 문자열 탐색
• 생략 테이블
• 구현
• 전체 코드
• 끝맺음

 

문자열 탐색

 

보이어 무어 알고리즘은 KMP 알고리즘과 같이 대표적인 문자열 탐색 알고리즘입니다.

 

문자열을 탐색할 시 고지식한 알고리즘(완전 탐색 알고리즘)을 사용할 시 상당한 길이가 짧은 문자열일 경우에는 상관없지만 그의 길이가 길어질수록 상당한 시간이 소요됩니다.

 

그러한 시간 복잡도 문제를 해결하기 위한 대표적인 알고리즘 두 개가 KMP 알고리즘과 이번에 알아볼 보이어-무어 알고리즘입니다.

KMP 알고리즘과 보이어-무어 알고리즘은 보이어-무어 알고리즘은 상당히 비슷한 메커니즘을 갖고 있습니다.

고지식한 알고리즘은 다음 인덱스로 한 칸씩 이동하는 반면 KMP 알고리즘과 보이어-무어 알고리즘은 미리 정의해둔 테이블을 참조하여 다음에 비교할 위치로 건너뛰어 버립니다.

이러한 행위는 반복 횟수를 상당히 줄일 수 있습니다.

그렇다면 보이어-무어 알고리즘은 어떤 방식으로 문자열을 건너뛰게 되는지 이제부터 알아가 보겠습니다.

 

 

보이어-무어 알고리즘

 

기존 고지식한 알고리즘과, KMP 알고리즘 혹은 지금까지 봐왔던 알고리즘들은 대부분 처음부터 비교해 나갈 것입니다.

하지만 보이어-무어 알고리즘은 뒤에서부터 비교해나갑니다.

뒤에서부터 비교를 진행해 나가다 비교 값이 서로 다를 시 테이블을 참조해 나아갑니다.

아래는 보이어-무어 알고리즘으로 비교해 나아가는 이미지입니다.

 

index	0	1	2	3	4	5	6	7	8
m	a	b	c	a	b	a	b	c	d
n	a	b	c	d

뒤에서 비교하다 index 3번이 다르다는 것을 확인 후 테이블을 참조합니다.

테이블을 참조 후 다음 비교할 위치로 건너뜁니다.

 

index	0	1	2	3	4	5	6	7	8
m	a	b	c	a	b	a	b	c	d
n				a	b	c	d

 

그다음 값을 보면 index 5, 6번이 다르지만 보이어-무어 알고리즘은 뒤에서부터 비교하므로 테이블 참조 시 index 6번에 대한 값을 참조하여 다음 비교 위치로 넘어갑니다.

 

index	0	1	2	3	4	5	6	7	8
m	a	b	c	a	b	a	b	c	d
n						a	b	c	d

 

총 2번의 이동만으로 원하는 값을 찾아냈습니다.

만약 고지식한 알고리즘이었다면 2번 이동했을 때쯤 index 2번에 n의 문자열이 위치했습니다.

그럼 아까부터 언급하고 계속 참조했던 테이블에 대하여 알아보겠습니다.

 

생략 테이블

 

생략 테이블은 제가 설명하기 쉽게 붙인 이름입니다.

 

패턴 문자열을 찾기 위해 패턴 문자열에 대해 생략 테이블이 2개가 필요합니다.

첫 번째로는 Bad Character Heuristica 방식으로 테이블을 생성합니다.

영어 그대로 일치하지 않는 본문 문자에 대해 참조하는 테이블입니다.

하지만 이러한 테이블 만으로는 정상적으로 동작하는 것을 기대하기 어렵기 때문에 두 번째 방식인  Good Suffix Heuristica 방식으로 테이블을 생성합니다.

이 방식은 KMP 알고리즘과 약간의 유사성이 있습니다. 

Suffix, 접미사와 대칭이 되는 것 을 찾아 테이블을 생성하는 방식입니다.

 

1. Bad Character Heuristica

 이 방법은 패턴 문자에 대하여 순서대로 번호를 붙여준다 생각하시면 됩니다. 

즉, 비교가 실패하였을 때 만약 그 틀린 본문 문자가 패턴 문자 내에 어딘가에 존재한다면 그곳으로 위치를 변경하는 것입니다. 

아래는 패턴 문자열에 각각의 번호를 붙여준 모양입니다.

(얘 시가 순서대로 돼있지만 중복된 문자가 나올 경우 후에 나온 번호가 뒤집어쓰기 때문에 값이 달라집니다. 이해가 안 가시는 분들은 이 글을 읽다 보시면 코드로 구현한 부분에서 좀 더 설명드리겠습니다.)

 

pattern string	a	b	c	d
special value	0	1	2	3

 

그렇다면 위의 테이블을 참조하여 다음의 비교를 진행해보겠습니다.

 

index	0	1	2	3	4	5	6	7	8
m	a	b	c	a	b	a	b	c	d
n	a	b	c	d

 

패턴 문자와 본문 문자가 일치하지 않는 부분이 존재합니다.

일치하지 낳는 본문 문자는 a 문자이지만 이 문자를 패턴 문자열 내에서 본 적이 있는 거 같습니다.

그래서 테이블을 확인해 보니 0번에 존재한다는군요.

그럼 다음과 같은 연산을 진행하여 현재의 다음 비교할 위치를 구합니다.

 

다음 위치 = 본문 문자열 내 현재 INDEX + (패턴 문자열 내의 현재 위치 - 테이블에서 참조한 값)

 

대입한 결과 : 3 = 0 + (3 +0) 

index	0	1	2	3	4	5	6	7	8
m	a	b	c	a	b	a	b	c	d
n				a	b	c	d

 

그다음에도 일치하지 않는 내용이 발생했습니다.

다음 테이블은 직접 계산해 보고 그려보시는 편이 이해하시는데 도움이 될 거 같습니다.

 

저희는 첫 번째 방식인 Bad Character Heuristica을 알아봤습니다.

하지만 이와 같은 방식으로만 동작하기에는 정상적으로 동작하지 않는 경우도 발생합니다. 

그리고 한 가지 테이블을 더 사용하여 두 테이블 중 더 큰 값으로 넘어간다면 좀 더 반복 횟수를 줄일 수 있을 것입니다.

 

2. Good Suffix Heuristica

이 방식은 접미사와 같은 문자열이 패턴 문자열 내에 존재하는지 를 검사합니다.

여기서 잠깐 접미사란 문자열 내에서 시작이 어디든 항상 끝까지 나타낸 문자열을 뜻합니다.

 

아래는 ababcabc에 대한 접미사를 나열한 모습을 보여줍니다.

 

ababcabc	접미사
	c
	bc
	abc
	cabc
	bcabc
	abcabc
	babcabc
	ababcabc

 

그렇다면 접미사와 일치한다는 문자열이란 아래와 같습니다.

 

접미사	일치한 문자열
c	ababcabc
bc	ababcabc
abc	ababcabc

 

접미사와 같은 문자열이 무엇인 지 알았으니 아래 테이블은 위의 내용을 테이블로 만든 내용입니다.

 

index	0	1	2	3	4	5	6	7
pattern	a	b	a	b	c	a	b	c
value	8	8	5	6	7	8	8	8

 

접미사와 같았던 문자열이 접미사를 가리키고 있는 것을 확인할 수 있습니다.

하지만 이것만으로 부족합니다. 그 이유는 보이어-무어 알고리즘은 뒤에서부터 비교를 해 나아가기 때문에 저 뒤의 접미사 부분이 바꿉니다. 

 

index	0	1	2	3	4	5	6	7
pattern	a	b	a	b	c	a	b	c
value	8	8	8	8	8	3	8	8

 

나머지 값이 패턴 문자열의 길이인 이유는 보이어-무어는 뒤에서부터 비교하기 때문에 틀리면 패턴의 문자열만큼 과감하게 건너뛸 수 있습니다.

위의 테이블은 접미사의 인덱스를 나타냈지만 지금 테이블은 다음 인덱스를 얼마큼 더해서 시작할지를 알려줍니다.

위와 같은 내용으로 c++ 언어로 구현해 보면서 부족한 설명을 해보겠습니다.

 

구현

 

1. Bad Character에 대한 테이블을 정의합니다.

Bad Table 은 위에서 설명한 바로 각 문자에 대해 순서대로 번호를 붙여준다고 했습니다. 

 

const int MAX_SIZE = 256;

vector<int> make_to_bad_character_tb(const string pattern){
    const int p_size = pattern.size();
    vector<int> bc_tb(MAX_SIZE, p_size);
    
    for(int i = 0; i < p_size; ++i)
        bc_tb[(int)pattern[i]] = i;
    
    return bc_tb;
}

 

이 테이블의 문제점은 중복된 문자가 나올 시 기존의 값을 덮어쓴 다했습니다. 

반복문 내용을 보시면 받은 문자를 int형으로 바꾼 위치에 값을 저장하는 모습을 볼 수 있을 것입니다.

 

2. Good Suffix에 대한 테이블을 만듭니다.

vector<int> make_to_gs_tb(const string pattern){
    const int p_size = pattern.size();
    
    int pattern_point = p_size;
    int suffix_point = pattern_point + 1;
    
    // 접미사와 동일한 문자열 체크하는 테이블
    vector<int> suf_tb(p_size + 1, 0);
    suf_tb[pattern_point] = suffix_point;
    // 생략할 테이블 
    vector<int> skip_tb(p_size + 1, 0);
    
    while(pattern_point > 0){
        // 접미사가 일치하는 순간 몇개가 일치하는지 카운팅
   	    while(suffix_point <= p_size &&
              pattern[pattern_point - 1] != pattern[suffix_point -1]){
            if(skip_tb[suffix_point] == 0)
                skip_tb[suffix_point] = suffix_point - pattern_point;
            suffix_point = suf_tb[suffix_point];
        }
        // 접미사와 동일한 단어가 접미사인덱스를 가르키도록 설정
        suf_tb[--pattern_point] = --suffix_point;
    }
    ...
}

 

위의 코드는 접미사와 동일해질 때 카운트를 시작하여 그에 맞게 배열에 넣어주는 코드입니다.

코드가 한눈에 안 들어와 저도 많이 보고 또 보았습니다. 

접미사와 동일한 문자들이 접미사의 인덱스를 가르치도록 만드는 작업이 이루어지는 작업과 일치한 접미사를 찾았을 때 그 얼마큼 스킵할지 저장합니다.

그러면 아래와 같은 테이블이 만들어집니다.

 

index	0	1	2	3	4	5	6	7	8
pattern	a	b	a	b	c	a	b	c
suf_tb	8	8	5	6	7	8	8	8	9
skip_tb	0	0	0	0	0	3	0	0	0

 

위에서 본 테이블과 많이 비슷해졌습니다. 

하지만 아직 생략 테이블은 나머지 문자에 대해서 어떻게 스킵해야 할지 모릅니다.

그렇다면 여기서 한 가지 더 설명드리겠습니다.

suf_tb의 목록을 보시면 일치한 값들이 보입니다.  이 값들은 패턴 문자열의 사이즈와 같으면 그 자릿수만큼 생략이 가능하다는 것입니다. 그리고 이 값은 앞자리부터 채워줍니다.

 

vector<int> make_to_gs_tb(const string pattern){
    const int p_size;
    
    int pattern_point = p_size;
    int suffix_point = pattern_point + 1;
    
    // 접미사와 동일한 문자열 체크하는 테이블
    vector<int> suf_tb(p_size + 1, 0);
    // 생략할 테이블 
    vector<int> skip_tb(p_size + 1, 0);
    
    ...
    
    suffix_point = suf_tb[0];
    while(pattern_point < p_size){
        if(skip_tb[pattern_point] == 0)
            skip_tb[pattern_point] = suffix_point;
        if(pattern_point++ == suffix_point)
            suffix_point = suf_tb[suffix_point];
    }
    
    return skip_tb;
}

 

index	0	1	2	3	4	5	6	7	8
pattern	a	b	a	b	c	a	b	c
suf_tb	8	8	5	6	7	8	8	8	9
skip_tb	8	8	8	8	8	3	8	8	0

 

그리고 이렇게 나온 값으로 원하는 문자열 검색을 합니다.

그렇다면 테이블 두 개를 어떠한 방식으로 참조하느냐도 중요합니다.

테이블을 참조하여 가장 큰 값을 택한다 생각하시면 됩니다.

 

int search(const vector<int> bc_tb, const vector <int> gs_tb,
           const string H, const string pattern){
    const int h_size = H.size();
    const int p_size = pattern.size();
    
    int begin = 0;
    
    if(h_size < p_size) return -1;
    
    while(begin <= h_size - p_size){
        int matched = p_size;
        
        while(matched > 0 && pattern[matched - 1] == H[begin + (matched - 1)]){
            --matched;
        }
        
        if(matched == 0) return begin;
        
        if(bc_table[H[begin + matched]] != p_size){
            begin += max(matched - bc_tb[H[begin + matched]],
                         gs_tb[matched]);
        }else{
            begin += max(gs_tb[matched], matched);
        }
    }
    
    return -1;
}

 

전체 코드

 

#include <iostream>
#include <vector>

using namespace std;

const int MAX_SIZE = 256;
vector<int> make_to_bad_character_tb(const string pattern)
{
    const int p_size = pattern.size();
    vector<int> bc_tb(MAX_SIZE, p_size);

    for (int i = 0; i < p_size; ++i)
        bc_tb[(int)pattern[i]] = i;

    return bc_tb;
}

vector<int> make_to_gs_tb(const string pattern)
{
    const int p_size = pattern.size();

    int pattern_point = p_size;
    int suffix_point = pattern_point + 1;

    // 접미사와 동일한 문자열 체크하는 테이블
    vector<int> suf_tb(p_size + 1, 0);
    suf_tb[pattern_point] = suffix_point;
    // 생략할 테이블
    vector<int> skip_tb(p_size + 1, 0);

    while (pattern_point > 0)
    {
        cout <<'h'<<endl;
        // 접미사가 일치하는 순간 몇개가 일치하는지 카운팅
        while (suffix_point <= p_size &&
               pattern[pattern_point - 1] != pattern[suffix_point - 1])
        {
            if (skip_tb[suffix_point] == 0)
                skip_tb[suffix_point] = suffix_point - pattern_point;
            suffix_point = suf_tb[suffix_point];
        }
        // 접미사와 동일한 단어가 접미사인덱스를 가르키도록 설정
        suf_tb[--pattern_point] = --suffix_point;
    }

    suffix_point = suf_tb[0];
    while (pattern_point < p_size)
    {
        if (skip_tb[pattern_point] == 0)
            skip_tb[pattern_point] = suffix_point;
        if (pattern_point++ == suffix_point)
            suffix_point = suf_tb[suffix_point];
    }
    for(auto & suf : suf_tb)
        cout << suf << ", ";
    cout << endl;
    for(auto & skip : skip_tb)
        cout << skip << ", ";
    cout << endl;
    return skip_tb;
}

int search(const vector<int> bc_tb, const vector<int> gs_tb,
           const string H, const string pattern)
{
    const int h_size = H.size();
    const int p_size = pattern.size();

    int begin = 0;

    if (h_size < p_size)
        return -1;

    while (begin <= h_size - p_size)
    {
        int matched = p_size;

        while (matched > 0 && pattern[matched - 1] == H[begin + (matched - 1)])
        {
            --matched;
        }

        if (matched == 0)
            return begin;

        if (bc_tb[H[begin + matched]] != p_size)
        {
            begin += max(matched - bc_tb[H[begin + matched]],
                         gs_tb[matched]);
        }
        else
        {
            begin += max(gs_tb[matched], matched);
        }
    }

    return -1;
}
int main()
{
    const string h = "abaabaababbabababcabccaabcabcabcbcabcbacba";
    const string pattern = "abbab";
    const int p_size = pattern.size();

    const vector<int> bc_table = make_to_bad_character_tb(pattern);
    const vector<int> gs_table = make_to_gs_tb(pattern);

    cout << search(bc_table, gs_table, h, pattern) << endl;

    return 0;
}

 

끝맺음

 

보이어-무어 알고리즘은 타 알고리즘에 비해 저도 이해하는데 상당히 오래 걸렸습니다.

지금도 긴가 민가 하는 부분도 종종 생깁니다. 

이렇게 한번 정리를 했어도 저 또한 제 글을 또다시 찾아 읽어보고 좀 더 쉽게 설명할 방안이 없나 생각을 더 해봐야 할거 같습니다.

틀린 부분이 있다면 과감히 지적해주시면 감사하겠습니다. 

긴 글 읽어주셔서 감사합니다.