[알고리즘] 스트링 처리 알고리즘 | 보이어 무어 알고리즘

● 1. 보이어-무어 알고리즘(Boyer-Moore algorithm)

보이어-무어 알고리즘은 문자열 검색에 사용되는 것으로, 이전 포스팅에서 살펴본 KMP 알고리즘의 목적과 유사합니다. 불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것이 주 목표입니다.

보이어-무어 알고리즘은 보통 상황에서 문자열은 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용합니다. 그래서 오른쪽 끝부터 비교하게 됩니다.

---

○ 1-1. 보이어-무어 알고리즘의 예

패턴의 오른쪽 끝에 있는 문자(e)와 본문(z)을 비교하여 일치 여부를 판단합니다. 불일치하고, 이 문자(z)가 패턴(apple)에 존재하지 않는다면, 패턴의 길이만큼 패턴을 이동시킵니다.

만일 패턴의 오른쪽 끝에 있는 문자(e)가 본문(p)와 비교해서 불일치하지만, 본문 문자(p)가 패턴(apple)에 존재한다면, 패턴의 오른쪽 끝에서부터 그 문자(p)까지의 칸 수를 세서 그만큼 이동시킵니다.

즉, 패턴 내에 존재하는 문자에 대하여 오른쪽 끝에서부터 차례대로 한 칸씩 증가하여 이동하게 됩니다.

• 예를 들어, n a t u r e 라는 패턴을 찾을 경우
  • 패턴의 오른쪽 끝과 본문을 비교한 뒤 본문이 e 였다면 -> 0칸 이동(패턴의 오른쪽 끝에서 두번 째와 본문을 재 비교 → … )
  • 패턴의 오른쪽 끝과 본문을 비교한 뒤 본문이 r 이었다면 -> 패턴을 1칸 이동
  • 패턴의 오른쪽 끝과 본문을 비교한 뒤 본문이 u 이었다면 -> 패턴을 2칸 이동
  • …
  • 패턴의 오른쪽 끝과 본문을 비교한 뒤 본문이 n 이었다면 -> 패턴을 6칸 이동

이렇게 이동시키는 기준을 삼기 위한 테이블을 만들어야 합니다. 여기서는 skip 테이블이라 하겠습니다.

• skip 테이블의 값은 위 그림처럼 만들 수 있습니다.

---

본문에서 n a t u r e 를 찾으려고 합니다.

• 패턴의 e와 본문의 s는 불일치하며, s는 패턴(n a t u r e)에 없는 다른 문자이므로, skip 테이블의 ‘다른 문자’ 를 보고 6칸 이동시킵니다.
• 이동 결과

---

• 패턴의 e와 본문의 n은 불일치하며, n는 패턴(n a t u r e)에 있는 문자이므로, skip 테이블의 ‘n’을 보고 5칸 이동시킵니다.
• 이동 결과

---

• 패턴의 e와 본문의 e는 일치하므로, skip 테이블의 ‘e’를 보고 이동시키지 않습니다. (0칸 이동)
• 이렇게 오른쪽 끝과 본문이 일치했을 경우, 패턴의 오른쪽 그 다음 끝부터 차례로 본문과 비교합니다.

---

• 본문의 문자와 패턴을 차례로 다 비교해서 모두 일치했을 경우 검색이 완료됩니다.
• 본문이 뒤에 더 있을 경우, 검색 완료 후에도 패턴의 길이만큼 다시 점프해서 검색을 진행합니다.

만약 위처럼 모두 일치하지 않고, 중간에 문자가 달랐다면, 또다시 skip 배열을 보고 점프해 주면 됩니다.

이처럼 보이어-무어 알고리즘은 오른쪽 끝의 문자열과만 비교하여 점프를 진행하므로, 빠르게 검색 효율을 높일 수 있습니다.

 

또한, 이 경우에 모든 문자를 훑어보지 않아도 되므로 시간 복잡도는 O(n) (본문의 문자열의 길이가 n이라 할 때) 보다 대체로 적다고 할 수 있습니다. (최악의 경우에는 O(mn), m은 패턴의 길이)

평균적으로 KMP 알고리즘보다 보이어-무어 알고리즘이 더 높은 성능을 보인다고 알려져 있습니다.

 

 

 

만약 끝 문자열을 포함해 몇 개가 일치하다가 중간에서 불일치 문자를 만나면 어떻게 될까요?

ACBBBCA에서 BBB를 검색해봅시다.

이 때 skip 테이블은 아래와 같습니다.  B가 여러 개 이므로 최소값인 0이 됩니다.

 

0

3