보이어 • 무어법

지난 글 : [알고리즘/Do it 알고리즘] - KMP법

 

보이어 • 무어법 알아보기

보이어(R. S. Boyer)와 무어(J. S. Moore)가 만든 보이어 • 무어법은 KMP법보다 이론과 실제 모두에서 더 우수하다 한다. 이 알고리즘은 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하며 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정한다.

 

텍스트 "ABCXDEZCABACABAC"에서 패턴 "ABAC"를 검색하는 경우를 예로 알고리즘을 살펴보자. 아래의 a처럼 텍스트와 패턴의 첫 번째 문자를 위아래로 겹치고 패턴의 마지막 문자 'C'를 검사한다. 텍스트의 'X'는 패턴에 없다. 이 문자는 패턴에 아예 없으니 b ~ d처럼 패턴을 1 ~ 3칸 옮긴다 해도 문자열 "ABCX"와 패턴이 일치하는 경우는 없다.

	A	B	C	X	D	E	Z	C	A	B	A	C	A	B	A	C
a	A	B	A	C
b		A	B	A	C
c			A	B	A	C
d				A	B	A	C

이처럼 비교 범위의 텍스트에 패턴에 없는 문자가 있다면 그 위치까지 건너뛸 수 있다. 그러므로 b ~ d의 비교를 생략하고 패턴을 한번에 4칸 뒤로 옮겨 아래 상태가 된다.

A	B	C	X	D	E	Z	C	A	B	A	C	A	B	A	C
				A	B	A	C

위 상태는 패턴의 마지막 문자 'C'와 텍스트의 'C'가 일치하므로 패턴의 검사대상을 바로 앞쪽에 있는 'A'로 옮긴다. 계속해서 아래를 보자.

	A	B	C	X	D	E	Z	C	A	B	A	C	A	B	A	C
a					A	B	A	C
b						A	B	A	C
c							A	B	A	C

패턴의 문자 'A'는 텍스트의 'Z'와 다르다. 그리고 텍스트의 'Z'는 패턴에 없는 문자이므로 패턴을 1칸 또는 2칸 옮기는 b, c와도 일치하지 않는다. 패턴을 한번에 3칸 옮겨 아래 상태로 만든다.

	A	B	C	X	D	E	Z	C	A	B	A	C	A	B	A	C
a								A	B	A	C
b									A	B	A	C
c										A	B	A	C
d											A	B	A	C

이렇게 옮긴 후 텍스트의 'A'와 패턴의 마지막 문자 'C'를 비교한다(a). 하지만 문자 'A'는 패턴의 1, 3번째 인덱스에 들어 있다. 이런 경우 b와 같이 패턴의 뒤쪽에 위치한 'A'가 텍스트와 겹치도록 패턴을 1칸만 옮긴다. 이때 d처럼 패턴의 앞쪽에 위치한 'A'와 겹치도록 3칸을 옮기면 안된다. 패턴을 1칸만 옮기면 아래와 같은 상태가 된다.

A	B	C	X	D	E	Z	C	A	B	A	C	A	B	A	C
								A	B	A	C

패턴의 마지막 위치부터 순서대로 문자를 비교하면 모두 일치하므로 검색 성공이다. 

 

그런데 보이어 • 무어 알고리즘에서도 각각의 문자를 만났을 때 패턴을 옮길 크기를 알려주는 표(건너뛰기 표)를 미리 만들어 둬야 한다. 패턴 문자열의 길이가 n일 때 옮길 크기는 아래와 같은 방법으로 결정한다.

패턴에 들어 있지 않은 문자를 만난 경우
1. 패턴을 옮길 크기는 n이다. 

패턴에 들어 있는 문자를 만난 경우
1. 해당 문자의 마지막 인덱스가 k면 패턴을 옮길 크기는 n - k - 1이다. 
2. 패턴의 마지막 문자가 패턴 안에 중복해 들어 있지 않은 경우("ABAC"의 'C'는 패턴 안에 1개만 들어있다)
   패턴을 옮길 크기를 n으로 한다. 텍스트에서 이런 문자(여기서는 "ABAC"의 'C')를 만날 경우 이동하지 않고
   바로 앞 문자를 비교한다. 이동할 필요가 없으니 사용하지 않지만 편의상 n이라고 한다.

 

아래는 위의 규칙을 적용해 만든 건너뛰기 표다.

텍스트 ... "ABCXDEZCABACABAC"			패턴 ... "ABAC"
=====================================================================================================
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
-----------------------------------------------------------------------------------------------------
4	4	4	4	4	4	4	4	4	4	4	4	4

 

아래는 보이어 • 무어법을 이용해 검색하는 프로그램이다. 패턴에 있을 수 있는 모든 문자의 옮길 크기를 계산하고 저장해야 하므로 건너뛰기 표의 요솟수는 Character.MAX_VALUE + 1이다(Character.MAX_VALUE는 char형으로 나타낼 수 있는 문자 수).

 

참고 서적 :