[알고리즘]보이어-무어(Boyer-Moore) 문자열 탐색 알고리즘

보이어 무어 알고리즘은 패턴의 오른쪽부터 비교하여 텍스트 문자를 모두 비교하지 않아도 탐색이 가능한 알고리즘이다.

전체 문자열과 찾고 싶은 문자열(패턴) 비교 시 문자열의 가장 뒷부분 위치를 비교하고,  다르면 일정 길이만큼 이동하여 비교를 계속하는 방법이다.

보이어무어 알고리즘은 두 가지의 이동으로 나뉜다.

• 나쁜 문자 이동(Bad Character Shift)
• 착한 접미부 이동(Good Suffix Shift)

두 가지의 이동을 적절히 이용하여 문자열 탐색을 할 때 최고의 시너지가 나온다.

즉, 전체 문자열과 찾고 싶은 문자열을 비교했을 때 불일치가 발생하면 나쁜 문자 이동과 착한 접미부 이동을 모두 검토해서 더 멀리 옮겨가는 이동 방법을 선택하게 된다.

 

Prefix(접두사), Suffix(접미사)
Prefix(접두사)와 Suffix(접미사)의 개념은 아래의 표를 보면 이해가 될 것이다.
BAABABAA 문자열에서 얻을 수 있는 접두사와 접미사는 아래와 같다.

 

문자열을 오른쪽에서 왼쪽으로 비교, 이동은 왼쪽에서 오른쪽으로

• 패턴의 오른쪽 끝에 있는 문자와 본문의 문자가 불일치하고 그 본문의 문자가 패턴내에 존재하지 않는 경우 이동 거리는 패턴의 길이와 같음

 

나쁜 문자 이동

나쁜 문자 이동의 단계

나쁜 문자 : 본문의 문자열과 패턴이 불일치하도록 만드는 문자

1. 본문과 패턴의 불일치가 발생하면 본문의 불일치한 문자와 같은 불일치 문자를 패턴에서 탐색.
2. 찾아낸 패턴의 불일치 문자 위치가 본문의 불일치 문자 위치와 일치하도록 패턴을 이동

불일치 문자와 동일한 문자가 패턴 내에서 2개 이상 나오는 경우, 발견된 문자 중 가장 오른쪽에 있는 것을 본문의 불일치 문자에 맞춤

문자열	B	A	A	B	A	B	B	A	C
과정1	B	B	A	C
과정2			B	B	A	C
과정3					B	B	A	C
과정4						B	B	A	C

 

착한 접미부 이동을 고려해야 하는 경우

패턴(찾는 문자열)이 오른쪽으로 이동하는 것이 아니라, 왼쪽으로 이동한다면 나쁜 문자 이동을 사용하는 것이 아니라 착한 접미부 이동을 고려해야 한다.

 

착한 접미부 이동

착한 접미부 이동은 두 가지 경우로 나뉜다.

1. 불일치가 발생한 상황에서 본문의 착한 접미부와 동일한 문자열이 패턴의 나머지 부분에 존재할 때
2. 불일치가 발생한 상황에서 본문의 착한 접미부와 동일한 문자열이 패턴의 나머지 부분에 존재하지 않을 때

 

첫 번째 경우

불일치가 발생한 상황에서 본문의 착한 접미부와 동일한 문자열이 패턴의 나머지 부분에 존재할 때

 

• 본문과 패턴 비교를 오른쪽에서부터 시작했는데 3번에서 본문의 B와 패턴의 A가 불일치
• 그래서 착한(동일한) 접미부 AB를 패턴의 나머지 부분에서 찾고 이렇게 찾아낸 부분이 본문의 착한 접미부 위치와 일치하도록 패턴을 이동

 

 

두 번째 경우

불일치가 발생한 상황에서 본문의 착한 접미부와 동일한 문자열이 패턴의 나머지 부분에 존재하지 않을 때

 

• 착한 접미부의 문자열을 왼쪽부터 하나씩 줄여가면서 반복해서 조사
• 완전 불일치의 경우, 패턴의 길이만큼 이동한 후 비교

 

• ‘착한 접미부의 접미부’가 패턴의 접두부와 일치하는지 확인
• 접미부와 일치하는 접두부는 착한 접미부 전체가 아닌 ‘착한 접미부의 접미부’와 일치하는 패턴의 접두부가 동일한 위치에놓이도록 패턴을 이동
• 착한 접미부가 AAB인데 패턴의 나머지 부분에서 이와 같은 문자열을 찾을 수 없음
• 착한 접미부의 문자열을 왼쪽부터 하나씩 줄여봄

 

• 착한 접미부의 접미부 AB는 패턴의 접두부와 일치(AB도 맞지 않을 경우 B가 일치하는지 확인)
• 이제 패턴의 접두부가 착한 접미부의 접미부에 일치하도록 다음과 같이 패턴을 이동
• 완전 불일치의 경우, 패턴의 길이만큼 이동한 후 비교