오늘은 문자열 검색에서 제일 효율적인 Boyer-Moore법에 대해 알아보자.

📘 Boyer-Moore법

R. S. Boyer와 J. S. Moore가 만든 Boyer-Moore법은 KMP법보다 효율이 더 좋다.
이 알고리즘은 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정한다.

📜 Boyer-Moore의 원리

텍스트 "ABCXDEZCZBZCABAC"에서 패턴 "ABAC"를 검색하는 경우를 예로 들어보자.

위의 그림처럼 텍스트와 패턴의 첫 번째 문자를 위, 아래로 겹치고 패턴의 마지막 문자 'C'를 검사한다. 텍스트의 'X'는 패턴에 없다. 이 문자는 패턴에 아예 없는 문자이기 때문에 b ~ d처럼 패턴을 1~3칸씩 옮겨도 문자열 "ABCX"와 패턴 안의 문자는 일치하지 않는다는 것을 알 수 있다.

이와 같이 텍스트 안에서 패턴이 들어 있지 않은 문자를 찾으면 해당 위치까지의 문자는 건너 뛸 수 있다. 이 방법을 사용하면 b ~ d의 비교는 생략하고 패턴을 단숨에 4칸 뒤로 옮겨 아래의 그림처럼 된다. 이 상태는 패턴의 마지막 문자 'C'와 텍스트의 'C'가 일치하기 때문에 패턴을 1칸 옮길 수 있다.

패턴의 문자 'A'는 텍스트의 'Z'와 다르기도 하지만 패턴에 없는 문자이다. 따라서 b,c처럼 패턴을 1,2칸 옮겨도 패턴과 일치하지 않는다는 것을 알 수 있다. 다음엔 패턴을 한꺼번에 3칸을 옮기면 된다. 이런식의 방법으로 찾는 것이 Boyer-Moore법이다.

📜 표 만들기

Boyer-Moore 알고리즘도 각각의 문자를 만났을때 패턴을 옮길 크기를 저장할 표(건너뛰기 표)를 미리 만들어야 한다. 패턴 문자열의 길이가 n일 때 옮길 크기는 아래의 방법으로 정한다.

패턴에 들어 있지 않은 문자를 만난 경우
1. 패턴을 옮길 크기는 n이다. 맨 처음 그림을 예로 들면 'X'는 패턴에 들어 있지 않으므로 4만큼 옮긴다.

패턴에 들어 있는 문자를 만난 경우
1. 마지막에 나오는 위치의 인덱스가 k이면 패턴을 옮길 크기는 n - k - 1이다.
2. 같은 문자가 패턴 안에 중복해서 들어 있지 않다면 패턴을 옮길 크기는 n이다.

📜 Boyer-Moore 코드

메서드로 한번 알아보자.

	// Boyer-Moore법으로 문자열 검색
    static int boyerMoore(String text, String pattern) {
        int pt;                 // text 커서
        int pp;                 // pattern 커서
        int textLen = text.length();       // text의 문자 개수
        int patternLen = pattern.length(); // pattern의 문자 개수
        int[] skip = new int[Character.MAX_VALUE + 1]; // 건너뛰기 표

        // 건너뛰기 표 만들기
        for (pt = 0; pt <= Character.MAX_VALUE; pt++)
            skip[pt] = patternLen;
        for (pt = 0; pt < patternLen; pt++)
            skip[pattern.charAt(pt)] = patternLen - pt - 1;

        // 검색
        while (pt < textLen) {
            pp = patternLen - 1;        // pattern의 끝 문자에 주목

            while (text.charAt(pt) == pattern.charAt(pp)) {
                if (pp == 0) return pt; // 검색 성공
                pp--;
                pt--;
            }
            pt += (skip[text.charAt(pt)] > patternLen - pp) ? skip[text.charAt(pt)] : patternLen - pp;
        }
        return -1;
    }

위의 코드는 Boyer-Moore법을 사용한 프로그램이다.

이때 패턴에 존재할 수 있는 모든 문자의 옮길 크기를 계산하고 저장해야 하기 때문에 건너뛰기 표의 요소 개수는 Character.MAX_VALUE+1 이다.