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

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

보이어-무어 알고리즘은 문자열 검색에 사용되는 알고리즘이다.

 

보이어-무어 알고리즘은 일반적인 상황에서 문자열은 앞부분보다 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다. 때문에 오른쪽 끝부터 비교하게 된다.

 

보이어 무어 알고리즘은 다음과 같이 이동할 칸의 개수를 저장해 놓은 테이블을 미리 만들어 저장해 놓는다.

 

 

오른쪽 끝과 일치하지 않는 경우

오른쪽 끝 문자가 일치하지 않는다면, 패턴에 해당 문자가 존재하는지 검사한다.

 

만약 패턴에 존재하지 않는다면, 패턴의 길이만큼 패턴을 이동시킨다.

 

만약 패턴에 존재한다면, 패턴의 오른쪽 끝에서부터 그 문자까지의 칸 수를 세서, 해당 칸수만큼 이동시킨다.

 

오른쪽 끝과 일치하는 경우

오른쪽 끝 문자가 일치했을 경우 차례대로 문자를 검사하게 된다.

 

여기서 중간에 문자가 다르다면 다시 일치하지 않는 경우를 적용하여 패턴에서 비교 문자 뒤에 해당 문자가 있는지 체크하고 해당 칸수만큼 문자를 이동시킨다.

여기선 패턴에 P가 없으므로 원래 P의 포인터에서 패턴 길이만큼 이동시켰다. 즉, 그 다음 포인터는 TARGET의 마지막 T에 있는 것이다.

 

만약 TARGET에서 A를 P로 변경하여 TPRGET이라고 해보자.

그러면 현재 문자에서의 포인터는 G가 되어 다음과 같이 이동한 것으로 됐을 것이다.

 

모든 문자가 일치했을 경우 검색이 완료된다.

만약 뒤에 더 존재할 경우, 검색 완료 후에도 패턴 길이만큼 이동해서 검색을 진행한다.

 

코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BoyerMoore {

    public static void main(String[] args) {
        String text = "동해물과 백두산이 마르고 닳도록 하느님이 보우하사 우리나라 만세 무궁화 삼천리 화려강산 대한사람 대한으로 길이 보전하세";

        List<Integer> indices = search(text, "대한");
        for (int i : indices) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    
    public static List<Integer> search(String text, String keyword) {
        List<Integer> indices = new ArrayList<>();

        Map<Character, Integer> skipTable = createSkipTable(keyword);

        int textPointer = keyword.length() - 1;
        while (textPointer > 0 && textPointer <= text.length()) {
            int keywordPointer = keyword.length() - 1;

            while (keywordPointer >= 0 && text.charAt(textPointer) == keyword.charAt(keywordPointer)) {
                textPointer--;
                keywordPointer--;
            }

            // 모두 일치했다면
            if (keywordPointer < 0) {
                indices.add(++textPointer);
                textPointer += keyword.length() + (keyword.length() - 1);
                continue;
            }

            // 일치하지 않았다면
            textPointer += skipTable.getOrDefault(text.charAt(textPointer), keyword.length());
        }

        return indices;
    }

    public static Map<Character, Integer> createSkipTable(String keyword) {
        Map<Character, Integer> skipTable = new HashMap<>();
        int count = keyword.length() - 1;
        for (char ch : keyword.toCharArray()) {
            skipTable.put(ch, count--);
        }
        return skipTable;
    }
}