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

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

보이어-무어 알고리즘은 텍스트(text) 안에서 패턴(pattern) 을 탐색할 때, 비교 횟수를 줄여 효율적으로 문자열을 찾는 문자열 탐색 알고리즘입니다. 문자열 탐색 알고리즘 중 하나인 KMP보다도 빠른 평균 시간 복잡도를 자랑하며, 특히 패턴이 길고 텍스트가 클 때 효율적입니다.

• 최악 시간 복잡도: O(N * M) (두 문자열 길이의 곱)
• 평균 시간 복잡도: O(N + M) (두 문자열 길이의 합. 다만 KMP보다 훨씬 빠름.)

 

보이어-무어 알고리즘의 핵심 아이디어

오른쪽에서 왼쪽으로 패턴을 비교하면서, 불일치가 발생했을 때 최대한 많이 건너뛰기 위한 두 가지 규칙을 사용합니다.

1. Bad Character Rule (나쁜 문자 규칙)
   • 불일치한 문자가 패턴에 존재한다면, 그 문자까지 이동
   • 없다면, 패턴 전체를 건너뜀
   • Bad Character Table을 통해 관리하며, 각 문자에 대해 "가장 마지막에 등장한 위치"를 저장
2. Good Suffix Rule (좋은 접미사 규칙)
   • 지금까지 일치했던 접미사가 다른 위치에서 다시 등장하는 경우, 그 위치로 이동
   • 또는 일치하는 접미사가 패턴의 접두사에 존재한다면 그 위치로 이동
   • Good Suffix Table을 통해 관리하며, 패턴 내에서 접미사가 다시 등장하는 위치를 계산

 

보이어-무어 알고리즘의 동작 과정

1. 패턴의 끝에서 비교를 시작
2. 일치하는 경우, 왼쪽으로 한 글자씩 계속 비교
3. 불일치하는 경우, Bad Character / Good Suffix 중 더 멀리 이동 가능한 쪽을 선택
4. 다음 위치로 이동하며 다시 비교

 

보이어-무어 vs KMP

항목	KMP 알고리즘	보이어-무어 알고리즘
비교 방향	왼쪽 -> 오른쪽 (정방향)	오른쪽 -> 왼쪽 (역방향)
이동 전략	실패 함수(Failure Function)을 이용한 최소 이동	Bad Character / Good Suffix 규칙으로 최대 이동
평균 성능	안정적이고 빠름	매우 빠름(실제 데이터에서 빠르게 동작)
최악 성능	O(N + M), 항상 보장됨	O(N x M), 점프가 제대로 이루어지지 않으면 성능 저하 발생
전처리 시간	O(M), 실패 함수 구성	O(M), 두 개의 테이블 구성
전체 시간	O(N + M)	O(N + M) ~ O(N x M)
특징 요약	항상 안정적, 예측 가능한 시간 보장	평균적으로 훨씬 빠름, 실제 데이터에 강함
적합한 상황	알고리즘 문제, 최악 시간 고려가 필수일 때	실무 환경, 긴 패턴이나 자연어 처리 등

정리하자면,

• KMP는 문자열-패턴 매칭에서 항상 안전한 선택이고,
• BM(보이어-무어)은 평균적으로 훨씬 빠르지만 최악의 상황을 피할 수 없을 때에는 조심해야 합니다.