크래프톤 정글

보이어-무어 문자열 검색 알고리즘

고웅 2025. 4. 15. 12:48

크래프톤 정글 8기 - 36일차 TIL

Boyer-Moore 문자열 검색 알고리즘 정리

Boyer–Moore 알고리즘은 문자열 검색 알고리즘 중에서도 가장 빠르고 실용적인 알고리즘 중 하나다. 이 글에서는 Boyer-Moore 알고리즘의 기본 개념, 핵심 규칙(Bad Character Rule, Good Suffix Rule), 그리고 실제 탐색 방식에 대해 정리한다.

1. Boyer-Moore 알고리즘의 핵심 아이디어

"비교는 오른쪽 끝부터 시작하며, 실패하면 패턴을 최대한 멀리 점프시킨다."

  • 일반적인 문자열 검색은 왼쪽부터 비교하지만,
  • Boyer–Moore는 오른쪽부터 왼쪽으로 비교한다.
  • 실패 시, 두 가지 규칙 중 더 먼 쪽으로 점프하여 검색 속도를 높인다.

보이어-무어 알고리즘에서는 한국어로 "건너뛰기 표(skip table)"를 사용하는데 건너뛰기 표는 알고리즘이 패턴을 얼마나 점프할 수 있는지 계산할 수 있도록 도와주는 전처리 테이블들을 말한다. 다른 말로는 이동 거리 테이블 또는 점프 테이블이라고 부른다.

2. 주요 전처리: 두 가지 점프 규칙

🔹 1. Bad Character Rule

  • 틀린 문자를 기준으로 패턴을 이동
  • 현재 틀린 문자가 패턴 내 어디에 다시 등장하는지 확인
  • 없으면 → 패턴 전체를 넘기기

예시:

Text:   ... A B C D E ...
Pattern:    A B C D F
                ↑   ↑
                |   틀림 (E ≠ F)

→ E는 패턴 내 없음 → 패턴 전체 점프

🔹 2. Good Suffix Rule

  • 이미 맞은 접미사를 기준으로 이동
  • 해당 접미사가 패턴 내 어디서 다시 등장하는지 확인
  • 등장하면 → 해당 위치로 정렬하여 점프
  • 없다면 → 접미사의 일부 또는 전체 이동

3. 실제 탐색 시 동작 방식

보이어-무어 알고리즘에서 말하는 skip table은 이러한 이동 거리를 미리 계산해서 저장해 놓은 표를 의미한다.

Skip Table 종류 핵심 키 값
Bad Character Table 문자 마지막 등장 위치
Good Suffix Table 접미사 길이 이동 거리

이 두 가지 skip table을 미리 만들어두면, 실제 비교 도중에는:

  • 둘 중 더 많이 이동할 수 있는 쪽을 선택해서 패턴을 효율적으로 이동시킴

4. 전처리 테이블 만들기

▶ Bad Character Table

  • 크기: 일반적으로 256 (ASCII)
  • 각 문자에 대해 가장 마지막 등장 인덱스 저장

예시 - 패턴이 "ABAC" 일 때

패턴 길이는 4이다. 이때 아스키코드 크기만큼의 배열을 만든 뒤 초가 값을 전부 4로 채워 넣는다. 이후 패턴 내에서의 마지막 등장 위치를 기준으로 각 문자의 이동거리를 계산한다.

badChar[char] = m - 1 - last_index_in_pattern

--> 패턴 끝에서 부터 얼마나 떨어져 있는지를 기준으로 점프 거리 설정

예: 패턴 "ABAC"

문자 인덱스 이동 거리 = m - 1 인덱스
A 2 4 - 1 - 2 = 1
B 1 4 - 1 - 1 = 2
C 3 4 - 1 - 3 = 0

▶ Good Suffix Table

  • 각 접미사에 대해:
    • 패턴 내에서 다시 사용할 수 있는 위치 계산
    • 없으면 → 더 짧은 접미사 탐색
    • 최종적으로 없으면 → 패턴 전체 이동

Good Suffix Shift 테이블은 두 가지 정보를 조합해서 만들어진 구조다:

테이블 설명
border_pos[i] 접미사 P[i:] 가 패턴 내 어디와 다시 일치하는지 나타냄 (재정렬 기준)
shift[i] P[i:]가 일치했을 때 패턴을 얼마나 이동시켜야 하는지

이때 shift[i]는 실질적으로 아래의 두 단계 점화식과 유사하게 구성된다.

Step 1: 접미사 재정렬용 테이블 border_pos[i]

border_pos[i] = j

의 의미는:

접미사 P[i:]와 일치하는 다른 부분 문자열 P[j:] 가 있다는 뜻

이건 KMP의 failure table과 유사한 재귀 구조이다.

if P[i - 1] == P[j - 1]:
    border_pos[i - 1] = j - 1
else:
    j = border_pos[j]

이게 재귀적으로 호출되므로 일종의 suffix-based DP로 작동한다.

Step 2: 점프 거리 계산 shift[i]

if pattern[i - 1] != pattern[j - 1]:
    shift[j] = j - i

이 조건이 성립될 때:

  • P[i:]는 일치하고,
  • 그 앞 P[i - 1] ≠ P[j - 1] → 불일치 발생
  • 이때 shift는 j - i만큼 패턴을 이동

여기서도 j = border_pos[j]로 재귀적으로 이동하며,
이미 채워진 shift[j]가 없을 경우에만 갱신하는 방식으로 작동한다.

 

  • border_pos[i]는 KMP에서 접두사/접미사 비교로 실패 시 어디로 점프할지 계산하는 것과 같고
  • shift[i]는 Good Suffix가 등장했을 때, 재정렬이 가능한 위치를 기반으로 얼마를 점프할지 나타냄

 

예시로 설명

예시 문자열

  • 텍스트: T = C G T G C C T A C T T A C T T A C T T A C T T A C G C G A A
  • 패턴: P = C T T A C T T A C

Step 1

일부 문자들은 성공적으로 매치됨
t = C T T A C T T A C → 불일치 발생

이제 이 일치된 접미사 t를 기준으로 다음 중 가장 빠르게 일치할 가능성이 있는 곳으로 패턴을 이동시킵니다:

Good Suffix Rule에서의 세 가지 이동 기준

  1. (a) t와 같은 문자열이 P 내에서 다른 위치에 또 존재 → 그 위치에 정렬
  2. (b) t의 접미사 중 일부가 P의 접두사(prefix)와 일치 → 그만큼 이동
  3. (c) 위 둘 다 해당 안 되면 P를 통째로 t 오른쪽으로 넘김 (t를 벗어남)

예시 :

패턴: C T T A C T T A C
우리가 방금 맞았던 부분이 T T A C 라고 해 보겠다.

Good Suffix Rule에 따라서 다음과 같이 생각해 보겠다:

  1. "혹시 T T A C라는 패턴이 내 안에 또 있는가?"
  2. 있다면 → 그 위치로 점프한다.
  3. 없다면 → 혹시 T A C, A C, C처럼 짧은 부분은 내 앞쪽에 있는가?
  4. 그마저도 없다면 → 아예 t를 피해서 통째로 패턴을 점프시킨다.

예시에서는 8칸을 한 번에 이동한다. 왜 그럴까?

C G T G C C T A C T T A C T T A C T T A C T T A C G C G A A  라는 문자열에서 우리가 찾고자 하는 패턴은 C T T A C T T A C 이다.

  1. 8번 인덱스부터 앞으로 비교하기 시작해서 TAC 까지는 맞았지만 그 앞의 T 즉 TTAC 에서 틀렸다.
  2. 그럼 t는 지금까지 맞았던 값 TAC 로 지정한다.
  3. 이제 자신 내부 즉 패턴 안에 TAC 값이 또 있는지 확인한다. 인덱스 2번부터 TAC가 또 등장한다.
  4. 그럼 바로 TAC로 이동을 하면 되는 것이 아닌가? 아니다.
  5. 앞에 발견된 TAC의 바로 앞 문자를 봐라 T이다. 그럼 TTAC 가 된다. 즉 우리가 이전에 틀렸던 상황이 또 발생하는 것이다. 
  6. 그래서 TAC로 이동하는 것이 아니라 그냥 8칸을 이동하겠다고 결정한 것이다.

 그렇다면 언제 t의 일부 접미사가 패턴의 접두사와 일치할 때 이동하는 것일까?

패턴에서 찾은 접두사의 앞 글자가 접미사의 틀렸던 위치 앞 값과 다를 때 이다.

다음 예시를 보자

T = C G T G C C T A C T T A C T T A C T T A C T T A C G C G A A
P = A C T T G A G A

P[7] 과 T[7]의 비교 결과 A가 맞다. 그다음 T와 G 가 틀린 상황이다. 이때 A가 어디에 위치했는지 보면 0번 인덱스와 5번 인덱스이다. 이때 5번 인덱스를 선택했을 시 A의 앞은 G로 이전에 틀렸던 값과 같다. 그렇다면 결국 0번 인덱스인 A를 선택해야 한다.

그럼 0번 인덱스의 A를 7번 인덱스에 위치하도록 점프를 한다.

T = C G T G C C T A C T T A C T T A C T T A C T T A C G C G A A
P =               A C T T G A G A

자 이동을 마쳤는데 이제 다시 Good Suffix Rule에 의해 오른쪽부터 비교를 할 것인데 보면 일치하는 문자가 없다. 그렇다면 Good suffix Rule에 의해서는 이동할 수 없을 것이다. 이때 우리가 처음 봤던 Bad Character Rule을 이용하게 된다.

즉 두 가지 방법의 테이블을 완성한 상태에서 어떤 값이 더 멀리 점프할 수 있는지 비교를 하는 것 일종의 다이내믹 프로그램일 수 있다.

5. Boyer-Moore의 장점과 활용

장점 설명
매우 빠름 평균적으로 가장 빠른 문자열 검색 알고리즘 중 하나
멀리 점프 가능 비교 실패 시 최대한 멀리 이동 가능
실전 활용도 높음 grep, IDE 검색, 컴파일러 등에서 사용

6. KMP와 비교

항목 KMP Boyer-Moore
비교 방향 왼쪽 → 오른쪽 오른쪽 → 왼쪽
점프 방식 LPS 배열 기반 점프 Bad Character + Good Suffix 기반
평균 속도 빠름 더 빠름
구현 난이도 쉬움 어려움

결론

Boyer–Moore는 매우 빠르며 실전에서도 널리 활용되는 문자열 검색 알고리즘이다.
두 가지 전처리 규칙만 잘 이해하면, 매우 효율적인 검색이 가능하다.

강력한 검색 성능이 필요할 때 꼭 고려해 볼 만한 알고리즘이다.

저작자표시 동일조건