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

1. 개념 📸

  보이어-무어(Boyer-Moore) 알고리즘은 skip이라는 것을 활용한 문자열 매칭 알고리즘이다. 여기서 skip이란 문자열을 비교할 때 불필요한 비교가 있다면 건너뛸 수 있도록 도와주는 것이다. (정확한 명칭은 아니지만 아래의 동작방식을 본다면 왜 skip이라고 불리는지 알 수 있을 것이다.)

  보이어-무어 알고리즘은 문자열을 비교할 때 일반적으로 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다. 그래서 비교할 문자열과 패턴을 앞부분부터 확인하는 것이 아닌 뒷부분부터 확인하게 된다.

 

2. 동작방식 🎬

  기본적인 동작방식은 일치하지 않은 문자를 만난 경우 패턴에서 일치하는 문자를 찾아서 이동한 후 비교를 다시 시작한다는 것이다. 본문은 'abphone' 패턴은 'phone'라고 하면 아래와 같이 동작한다.

  위와 같이 문자가 일치하지 않는 경우에(o != e) 패턴에서 o와 일치하는 문자를 찾아서 이동한 후 다시 비교를 하는 것이다. (패턴에 일치하는 문자가 없는 경우 패턴의 길이만큼 이동해야 한다.) 결국 '문자가 일치하지 않는 경우에 얼마만큼 이동해야 하는지'와 '비교 연산'만 수행하면 해당 알고리즘이 동작한다.

  이때, '얼마만큼 이동해야 하는지'를 알기 위해서 사용하는 것이 skip 배열이다. skip배열은 해당 문자가 패턴에서 뒤에서 몇 번째에 위치하는지 알려준다. skip의 값은 '패턴 문자열의 길이 - 각 패턴 문자의 인덱스 - 1'을 가진다.

문자	p	h	o	n	e	다른 모든 문자
skip 값	4	3	2	1	5	5

  일치하지 않는 문자를 발견했을 경우 위의 skip 배열을 활용한다면 즉시 몇 칸을 이동해야 하는지 알 수 있을 것이다. phone을 사용한 예제에서 o와 e가 일치하지 않았을 때 2칸을 이동한 이유가 skip 배열에서 'o'의 값(=2)을 참고하였기 때문이다.

  다음은 skip 배열을 사용해서 빠르게 패턴과 일치하는 문자열을 찾는 예제이다.

  주의해서 봐야 할 점은 skip값만큼 본문 포인터가 움직인다는 것이다. 패턴이 이동하는 칸의 개수가 아니다.

 

3. 구현 🎥

public class BoyerMoore {
	
	static int BoyerMooreMatch(String str, String pattern) {
		int strCursor = 0;
		int patternCursor = 0;
		int strLen = str.length();
		int patternLen = pattern.length();
		int[] skip = new int[Character.MAX_VALUE + 1];
		
		// 패턴에 존재하지 않는 경우 = 패턴의 길이
		// 패턴에 존재하는 경우 = skip해야 하는 칸수
		// 에 해당하도록 skip 배열 설정
		for(strCursor = 0; strCursor <= Character.MAX_VALUE; strCursor++) {
			skip[strCursor] = patternLen;
		}
		for(strCursor = 0; strCursor < patternLen - 1; strCursor++) {
			skip[pattern.charAt(strCursor)] = patternLen - strCursor - 1;
			System.out.println(pattern.charAt(strCursor) + " : " + (patternLen - strCursor - 1));
			
		}
		while(strCursor < strLen) {
			patternCursor = patternLen - 1;
			
			// 비교하는 문자열과 패턴이 뒤에서부터 계속 일치하여
			// cursor의 값을 줄이면서 계속 비교하는 과정
			while(str.charAt(strCursor) == pattern.charAt(patternCursor)) {
				if(patternCursor == 0) {
					// 패턴과 일치하는 문자열을 찾은 경우 시작 인덱스를 반환
					return strCursor;
				}
				patternCursor--;
				strCursor--;
			}
			
			strCursor += Math.max(skip[str.charAt(strCursor)], patternLen - patternCursor);
		}
		
		return -1;
	}
	
	public static void main(String[] args) {
		String str = "abcaneczbphone";
		String pattern = "phone";
	}
}

 

4. 시간복잡도 📼

  주어진 문자열의 길이가 N이고 패턴의 길이가 M이라고 할 때, 시간복잡도는 O(NM)이다. 본문이 AAAAAA이고 패턴이 BA일 수 있기 때문이다. 하지만 일반적으로는 O(N) 보다 대체로 작다. 

  평균적으로 보이어-무어 알고리즘은 KMP 알고리즘보다 빠른 성능을 보인다고 알려져 있고 그로 인해 가장 많이 쓰이는 알고리즘이기도 하다.

 

해당 글은
Chan 님의 '알고리즘 - 보이어-무어 알고리즘 : 문자열 검색을 위한 또다른 알고리즘',
야인코딩 님의 '보이어 무어(Boyer-Moore) 문자열 검색 알고리즘'
을 참고하였습니다.