보이어-무어 알고리즘 (Boyer-Moore)

• 보이어-무어 (Boyer-Moore)

 보이어-무어 알고리즘은 문자열 검색 알고리즘의 하나이다. 이전 글에서 봤던 것까지 생각해보면 문자열 검색 알고리즘은 다음 3가지가 있다.

 

1. 브루트포스

2. KMP

3. 보이어-무어

 

 문자열의 길이가 n, 패턴 문자열의 길이가 m일때 각각의 알고리즘의 시간복잡도를 비교해보면 다음과 같다.

1. 브루트포스는 가장 단순한 알고리즘이지만 시간복잡도가 O(mn)으로 3개 중에 가장 느린 알고리즘이다.

2. KMP는 최악의경우에도 시간복잡도가 O(n)으로 매우 빠르지만 패턴안에 반복하는 요소가 없으면 효율이 떨어진다.

3. 보이어-무어는 최악의 경우 시간복잡도가 O(mn)이지만 평균적으로 O(n)보다 빠른 시간복잡도를 갖는다. 

 

 이번에 보이어-무어까지 배우고 각각의 장단점에 따라 필요한 알고리즘을 선택해서 쓰자!

 

보이어-무어 알고리즘에 대해 배워보자. 보이어-무어는 KMP알고리즘처럼 브루트포스의 쓸데없는 경우의수들을 생략하는 효율적인 알고리즘이다. 주어진 문자열을 dest라하고 그 안에서 찾아야할 문자열을 pattern이라 할때 다음과 같이 비교를 하면 진행을 한다.

 

dest : ABCPKAABT

pattern : ABT

 (1) dest_i = 2

	0	1	2	3	4	5	6	7	8
dest	A	B	C	P	K	A	A	B	T
pattern	A	B	T

 우선 pattern의 마지막 문자와 그 index와 같은 dest의 문자를 비교한다. 위의 예시에선 dest의 문자가 'C'인데 'C'는 'T'와 같지도 않고 pattern에 없는 문자이므로 바로 아래와 같이 단계를 넘어갈 수 있다.

 

(2) dest_i = dest_i + 3 = 5

	0	1	2	3	4	5	6	7	8
dest	A	B	C	P	K	A	A	B	T
pattern				A	B	T

 (1)에서 (2)로 Jump 할 수 있는 이유는 앞서 비교했던 dest.charAt(2)인 'C'가 pattern에 없는 문자이기 때문에 'C'가 pattern과 비교되는 경우의 수는 다 뛰어넘는 것이다. 그리고 (1)과 마찬가지로 pattern의 마지막 문자와 그 위치에 있는 dest의 문자를 비교한다. 이번에는 dest의 문자인 'A'가 pattern의 'T'와 다르지만 pattern에 있는 문자이므로 (2)와 다르게 Jump를 한다.

 

(3) dest_i = dest_i + 2 = 7

	0	1	2	3	4	5	6	7	8
dest	A	B	C	P	K	A	A	B	T
pattern						A	B	T

 이번에는 pattern의 글자 수 만큼 Jump했던 (2)와 달리 pattern 내의 'A'와 아까 찾은 dest의 문자인  'A'가 일치하는 곳까지만 Jump를 한다. 그리고 똑같이 pattern의 마지막 문자와 그 위치에 있는 dest의 문자를 비교한다. 이번에도 dest의 문자인 'B'가 pattern의 'T'와 다르지만 pattern에 있는 문자이므로 (3)과 같이 pattern 내의 'B'가 이번에 찾은 dest의 'B'와 일치하도록 Jump를 한다.

 

(4) dest_i = dest_i + 1 = 8

	0	1	2	3	4	5	6	7	8
dest	A	B	C	P	K	A	A	B	T
pattern							A	B	T

 이번엔 pattern의 마지막 문자인 'T'와 그 위치에 있는 dest의 문자 'T'가 같다. 따라서 서로 index를 -1씩 해주면서 끝까지 맞는지 확인을 한다. 이번 예제에서는 'A', 'B', 'T'가 모두 일치하므로 pattern을 dest내에서 찾았다고 할 수 있다.

 

 

 다음과 같이 브루트포스였으면 앞에서부터 1글자씩 확인하며 진행했을텐데 3번의 Jump만에 pattern을 찾는 것을 볼 수 있다. KMP를 공부했던 사람들은 이번 예시를 쭉 보면서 Table이 필요하다는 것을 알았을 것이다. 그 Table이란 것은 pattern의 마지막 문자와 그 위치에 있는 dest의 문자를 비교했을때 서로 다르면 Jump를 해야되는데 이때 얼만큼 Jump를 할지에 대해 미리 기록을 해놓는 배열을 의미한다. dest의 문자가 pattern에 없는 문자라면 pattern의 문자길이만큼, 그게 아니라 pattern내에 존재하는 문자라면 dest의 문자가 pattern내의 그 문자와 같은 위치에 있을 수 있을 만큼 Jump를 해야한다. 

 

 알고리즘이 어떻게 진행되는지 간단히 봤으니 코드를 보며 Table을 이해하고 전체적인 과정을 자세히 보자.

static int BoyerMoore(String dest, String pat)
{
    int dest_i;
    int pat_i;
    int dest_len = dest.length();
    int pat_len = pat.length();
    int[] table = new int[Character.MAX_VALUE + 1];

    // 배열의 요소 초기화
    for (int i = 0; i < table.length; i++)
        table[i] = pat_len;
    // pattern에 있는 문자에 대해 table 값 변경
    for (int i = 0; i < pat_len; i++)
        table[pat.charAt(i)] = pat_len - 1 - i;

    dest_i = pat_len - 1;
    while (dest_i < dest_len)
    {
        pat_i = pat_len - 1;
        //dest의 문자와 pattern의 문자가 같을 경우
        while (dest.charAt(dest_i) == pat.charAt(pat_i))
        {
            if(pat_i == 0)
                return dest_i;
            dest_i--;
            pat_i--;
        }
        //dest의 문자와 pattern의 문자가 다를 경우
        dest_i += (table[dest.charAt(dest_i)] > pat_len - pat_i) ? table[dest.charAt(dest_i)] : pat_len - pat_i;
    }
    return -1;
}

 첫번째, 두번째 for문은 table을 만드는 과정이고, 그 밑의 while문은 table을 통해 dest를 탐색을 하는 부분이다.

우선 table은 index에 해당 문자를 넣었을때 Jump값이 나와야하므로 배열의 크기를 모든 Character가 들어갈 수 있도록 만들어주고 배열의 모든 요소들을 pattern의 길이로 초기화해준다. pattern의 길이로 초기화 해준 이유는 다음 for문을 보면서 알아보자.

 두번째 for문에서는 pattern의 문자를 맨 앞부터 방문하면서 해당 문자에 대한 table 값을 바꿔준다. 아까 위의 예시 (2)에서 (3)으로 넘어갈때 dest의 문자인 'A'가 pattern내에 존재했던 경우를 보자. pattern 내의 'A'가 pattern의 마지막 문자인 'P'와  index가 2만큼 차이가 나서 2칸을 Jump 했다. 이처럼 pattern에 존재하는 문자를 만났을 때 Jump하기위해 그 문자와 pattern내의 마지막 문자의 index 차이를 table에 넣어준다.

[ pattern안 문자의 index = i ] 

[ pattern안 마지막 문자의 index = pat_len - 1 ]

그리고 pattern안에 없는 문자를 만난경우는 pattern의 길이만큼 Jump해야하므로 첫번째 for문에서 pat_len으로 초기해 주었다.

 

이제 table작성을 완료했으니 탐색을 시작해보자.

현재 dest의 index 위치를 dest_i 그리고 pattern의 index 위치를 pat_i로 선언하였다. 그리고 항상 둘다 pat_len - 1에서 시작을 한다. 그리고 while문을 들어가면 2가지의 경우의 수가 나온다. 

 

1. dest의 문자와 pattern의 문자가 같은 경우

2. dest의 문자와 pattern의 문자가 다른 경우

 

 1번의 경우에는 dest_i와 pat_i를 -1해가면서 계속 비교를 하고 다른경우 2번으로 빠져나간다. 하지만 dest_i = 0일 때까지 같으면 dest내의 pattern을 찾은 경우이므로 dest_i를 반환한다.(dest내의 pattern이 시작하는 index)

 만약 2번의 경우이면 dest_i에 위치한 dest의 문자를 보고 앞에서 미리 정해놓은 table의 값만큼 이동을 한다. 하지만 잘 보면 삼항연산자가 쓰여 pat_len - pat_i만큼 Jump하는 경우의 수가 추가되어있는 것을 볼 수 있다. 이는 코드를 좀 더 효율적으로 만들기 위해 적용해놓은 것으로 1번에서 같은 문자가 계속 나와서 dest_i가 계속 -1되다가 2번으로 왔는데 table의 값대로 Jump를 했을 때 처음 1번에 들어갔을 때보다 dest_i가 작아진 경우 굳이 한번 지나온 길을 다시 지나갈 필요가 없기 때문에 1번에 처음 들어갔을 때의 dest_i에 + 1을 해주는 것이다.

 위 2가지 경우의 수를 넘나들면서 dest내의 pattern을 찾으면 그 pattern이 시작되는 index를 반환하고 못찾고 while문을 빠져나온 경우 -1을 반환한다.

 

---

reference

 -https://devwooks.tistory.com/12