보이어&무어법이란?
보이어&무어법이란? 브루트-포스법을 개선한 KMP법 보다도 효율이 더 좋기때문에 실제 문자열 검색 프로그램에서도 널리 사용하는 알고리즘이다.
보이어&무어법의 시간 복잡도
이 알고리즘의 시간 복잡도는 최악의 경우O(n), 평균적으로 O(n/m)으로 매우 빠른편에 속한다. 2개의 배열로 구현하는 보이어&무어법은 처리하기 복잡해 효과가 상쇄된다. 아래 예제코드에서는 간략한 보이어&무어법을 사용했는데 해당 코드로 검색해도 충분히 빠르게 검색 가능하다.
보이어&무어법 알아보기
Boyer와 Moore(무어의 법칙 무어아님)가 만든 보이어&무어법은 KMP법보다 이론과 실제 모두에서 더 우수한 알고리즘이다.
이 알고리즘은 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정하게 된다.
텍스트"ABCXDEZCABACABAC"에서 패턴 "ABAC"를 검색하는 경우를 예로 이 알고리즘을 살펴보자.
│ A │ B │ C │ X │ D │ E │ Z │ C │ A │ B │ A │ C │ A │ B │ A │ C │
l 일치x 텍스트의 'X'는 패턴에 없음
│ A │ B │ A │ C │
│ A │ B │ A │ C │
│ A │ B │ A │ C │
│ A │ B │ A │ C │ 텍스트와 패턴의 첫 번째 문자를 위아래로 겹치고 패턴의 마지막 문자인 'C'를 검사한다. 텍스트의 'X'는 패턴에 없다. 이 문자는 패턴에 아예 없기에 패턴을 한칸씩 1~3칸 옮긴다 해도 문자열 "ABCX"와 패턴이 일치하는 경우는 없다.
이처럼 비교 범위의 텍스트에 패턴에 없는 문자가 있다면 그 위치까지 건너뛸 수 있다. 그렇기에 패턴을 뒤로 3칸 옮기는 경우를 생략하고, 4칸 뒤부터 검사할 수 있다.
│ A │ B │ C │ X │ D │ E │ Z │ C │ A │ B │ A │ C │ A │ B │ A │ C │
l l 일치하기에 바로앞 패턴요소A검사.
│ A │ B │ A │ C │
하지만 일치하지 않음.패턴의 마지막 문자와 텍스트[7]은 서로'C'로 일치하나. 바로앞 패턴'A'와 텍스트[6]이 다르다. 심지어 텍스트[6]의 'Z'는 패턴에 없다. 따라서 패턴을 한꺼번에 3칸 옮겨 다음과 같은 상태를 만들어 준다.
이때 많이 착각하는 부분이 있다.
패턴의 길이를n이라하면 텍스트에서 패턴에 들어 있지 않은 문자를 만날 경우 패턴 자체를 n만큼 옮기면 안된다. 현재 검사하고 있는 텍스트 안의 문자 위치로부터 패턴이 n만큼 멀어지도록 패턴을 옮겨야 한다.
│ A │ B │ C │ X │ D │ E │ Z │ C │ A │ B │ A │ C │ A │ B │ A │ C │
l 일치x
│ A │ B │ A │ C │
│ A │ B │ A │ C │ - 한칸 옮기면 일치하는 문자 등장
│ A │ B │ A │ C │ - 2칸 옮겨도 문자가 다름
│ A │ B │ A │ C │ - 3칸 옮기면 안됨!!이렇게 옮긴 다음 텍스트의'A'와 패턴의 마지막 문자인'C'를 비교하나 일치하지는 않는다. 그런데 텍스트의 문자 'A'는 패턴의 0,2번째 인덱스에 들어있다. 이런 경우 일단 패턴의'C'와 가까운 2번째 'A'를 겹치게 만들어준다. (한칸 뒤로 옮김,여기서 'A'가 같다고 패턴의 1번째와 겹치게 만들면 안된다! 3칸 옮기면 안된다는 소리)
이렇게 한칸 뒤로 옮기면 ABAC가 모두 일치하기 때문에 검색 성공이다.
하지만 보이어&무어 알고리즘도 각각의 문자를 만났을 때 패턴을 옮긴 크기를 알려주는 건너뛰기 표가 필요하다(KMP법에서 처럼) 패턴 문자열의 길이가 n일 때 옮길 크기는 다음과 같은 방법으로 결정하게 된다.
패턴에 들어있지 않은 문자를 만날 경우
1. 패턴을 옮길 크기는 n이다. 위 예제의 'X'경우처럼, 패턴에 들어 있지는 않기 때문에, 패턴의 크기였던 4칸을 옮긴다.패턴에 들어 있는 문자를 만난 경우
1. 만난문자가 패턴 내에서 마지막 위치가 k이면 패턴을 옮길 크기는 'n-k-1'이다. 위의 예제에서 살펴봤듯 패턴 내에 겹치는 문자가 있을 수 있으므로 마지막 위치 인덱스를 사용해야 한다.
위의 예제처럼 'A'가 패턴의 두 곳에 들어있기에 마지막 인덱스를 선택해 패턴을 1만큼(4-2-1=1)만큼 옮긴다.
- 패턴의 마지막 문자가 패턴 안에 중복해서 들어 있지 않은 경우("ABAC"의 'C'는 패턴 안에 1개만 들어있음) 패턴을 옮길 크기를 n으로 한다.
위의 규칙을 적용해서 만든 건너뛰기표를 아래에서 볼 수 있는데, 이 표에 없는 모든 문자(숫자나 기호등)는 패턴에 없는 문자이므로 옮길 크기가 모두 4이다.
│ A │ B │ C │ D │ E │ F │ G │ H │ I │ J │ K │ L │ M │
│ 1 │ 2 │ 4 │ 4 │ 4 │ 4 │ 4 │ 4 │ 4 │ 4 │ 4 │ 4 │ 4 │
│ N │ O │ P │ Q │ R │ S │ T │ U │ V │ W │ X │ Y │ Z │
│
사실상 줄여보면 아래와 같음.
│ A │ B │ 나머지 │
│ 1 │ 2 │ 4 │ 건너뛰기 표의 요솟수는 Character.MAX_VALUE + 1이라고 할 수있겠다.
보이어&무어법 예제코드
※ 원래 보이어&무어법은 2개의 배열로 문자열을 검색하나 여기서는 간단하게 1개의 배열을 사용해서 만들었다.
public class BMMatch {
// 보이어&무어 검색법
static int bmMatch(String txt, String pat) {
int pt;
int pp;
int txtLen = txt.length();
int patLen = pat.length();
int[] skip = new int[Character.MAX_VALUE + 1];
// 건너뛰기 표 만들기
for (pt = 0; pt <= Character.MAX_VALUE; pt++) {
skip[pt] = patLen;
}
for (pt = 0; pt <= patLen - 1; pt++) {
skip[pat.charAt(pt)] = patLen - pt - 1; // pt == patLen - 1
}
// 검색하기
while (pt < txtLen) {
pp = patLen - 1; // pat의 마지막 문자에 주목
while(txt.charAt(pt) == pat.charAt(pp)) {
if (pp == 0)
return pt;
pp--;
pt--;
}
pt += (skip[txt.charAt(pt)] > patLen - pp) ? skip[txt.charAt(pt)]: patLen - pp;
}
return -1; // 검색 실패시 -1 반환
}
}