[프로그래밍] boyer-moore 알고리즘(패턴 매칭 알고리즘)

Boyer-moore 문자열 탐색 알고리즘은 Robert S. Boyer와 J Strother Moore에 의해 1977년에 개발되었다. 

알고리즘의 컨셉은 패턴을 뒤에서부터 비교하여 탐지하는 것이 특징이다. 

Boyer-moore 알고리즘은 크게 다음 두 가지 방식의 탐지 방식을 사용하고 있다.

두 가지 방식 중 더 큰 값만큼 이동하면서 패턴 매칭을 시도하게 된다. 

1. bad character method 

주로, 문자열이 매칭되지 않았을 때 많이 이동 할 수 있는 알고리즘. 
character set인 256만큼의 배열을 잡아서 패턴 길이 값으로 초기화를 시켜준다. 

이후 패턴의 앞 부터 한자씩 읽어 가면서 해당 배열값에 마지막 글자까지의 값으로 설정
예를 들면, 아래 문장의 가장 처음 'A'의 경우, 'A'는 10진수 65이다. 
그러므로, 배열의 65번째 값에 'A'와 패턴의 끝인 'N' 와 7글자 떨어져 있으므로 7을 넣어준다. 
이와 같은 방식으로 A->N->P->A->N->M->A를 처리한다. 만약, 동일한 문자가 나오면 마지막 글자와 가까운 위치에 탐지를 해야할 문자가 있는 것이므로 해당 값을 덮어쓰게 된다.  (마지막 글자 N은 떨어진 거리가 0이므로 제외)
그 결과 아래 표와 같은 결과를 얻을 수 있다. 

예) ANPANMAN 

Character	Shift
A	1
M	2
N	3
P	5
all other characters	8

2. good-sufix method 
주로, 문자열이 매칭된 경우 많이 이동할 수 있는 알고리즘. 
입력받은 패턴을 가지고 최대 이동 값을 미리 계산해둔다. (문자열 길이만큼의 배열)

최대 이동값을 계산하는 방식은 아래 표와 같다.  

i는 현재 패턴을 매칭하기까지 매칭에 성공한 문자 개수이다. 
pattern에서 취소선이 그어져 있다면, 해당 문자는 매칭이 되지 않음을 의미한다. 
Left shift는 왼쪽으로 얼마만큼 이동할지를 의미한다. 
(최종적으로 배열에는 i + left shift 값으로 설정해주게 된다. )

예) ANPANMAN 

i	Pattern	Left Shift
0	N	오른쪽 끝 문자가 N이 아닌 문자만큼 왼쪽으로 이동. 오른쪽 두번째 문자가 A이므로, 한 칸 이동한다. (만약 'ANPANMNN'이라면 두 칸 이동하게 된다. )  = 1
1	AN	AN 은 ANPANMAN에 더이상 나오지 않는다. 때문에, 패턴 길이 만큼 이동하게 된다. = 8
2	MAN	MAN 은 ANPANMAN  패턴에서 세칸 이동하면 찾을 수 있다.   = 3
3	NMAN	'NMAN' 은  'ANPANMAN' 에 더이상 나오지 않는다.  하지만,  'NMAN' 은 6 칸 이동하면 또 나타난다.   ('NMANPANMAN')  = 6
4	ANMAN	'ANMAN'은 더이상 나오지 않는다. 하지만,'ANMAN' 은 6 칸 이동하면 나타난다.    ('ANMANPANMAN') = 6
5	PANMAN	'PANMAN'은 더이상 나오지 않는다. 하지만, ' PANMAN' 은 6 칸 이동하면 나타난다.     ('PANMANPANMAN')  = 6
6	NPANMAN	'NPANMAN'은 더이상 나오지 않는다. 하지만, ' NPANMAN' 은 6 칸 이동하면 나타난다.      ('NPANMANPANMAN')  = 6
7	ANPANMAN	'ANPANMAN'은 더이상 나오지 않는다. 하지만, ' ANPANMAN' 은 6 칸 이동하면 나타난다.       ('ANPANMANPANMAN')  = 6

• 탐지 예제

순번

M

A

N

P

A

N

P

A

N

M

A

N

1

A

N

P

A

N

M

A

N

2

A

N

P

A

N

M

A

N

3

A

N

P

A

N

M

A

N

- 순번 1: 패턴의 뒤에서부터 매칭을 시도 하면 문자열 ‘A’와 패턴 ‘N’이 같지 않으므로 이동을 해야 한다. bad-character method 와 good-suffix method모두 이동 값이 1 이므로 1칸만 이동.

- 순번 2: 뒤에서 ‘AN’이 매칭되었으므로, bad-character method에 의해 ‘P’의 이동 값이 5에서 ‘AN’ 두 문자만큼의 값을 뺀 3만큼 이동하게 된다. Good-suffix method에 의해서도 i가 2일 때 값이 3이므로 3만큼 이동하여 다시 매칭을 시도한다. 

- 순번 3: 원하는 문자열을 찾았다.