보이어-무어 알고리즘
보이어-무어 알고리즘은 패턴의 오른쪽부터 비교하며 불일치 정보를 이용해 큰 폭으로 건너뛰는 검색 기법이다 문자열 패턴 검색 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순...
| 분류 | 알고리즘 · 문자열 패턴 검색 |
|---|---|
| 핵심 문제 | 패턴의 오른쪽부터 비교하며 불일치 정보를 이용해 큰 폭으로 건너뛰는 검색 기법이다 |
| 방법 | 나쁜 문자 규칙과 좋은 접미사 규칙을 전처리해 다음 정렬 위치를 선택한다 |
| 계산 비용 | 전처리와 탐색 비용은 구현·패턴 길이에 따라 달라지며 고전 단순 변형은 최악 O(nm) 가능 |
| 적용 조건 | 유효한 문자 비교 및 이동 테이블이 필요하다 |
| 관련 활용 | 긴 패턴과 일반 텍스트 검색에 실용적이며 Horspool 등 단순화된 변형도 널리 사용한다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
보이어-무어 알고리즘은 패턴의 오른쪽부터 비교하며 불일치 정보를 이용해 큰 폭으로 건너뛰는 검색 기법이다 문자열 패턴 검색 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 나쁜 문자 규칙과 좋은 접미사 규칙을 전처리해 다음 정렬 위치를 선택한다. 문자 집합과 입력의 일치 구조에 따라 검사 횟수가 크게 줄어든다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 전처리와 탐색 비용은 구현·패턴 길이에 따라 달라지며 고전 단순 변형은 최악 O(nm) 가능 적용 전제는 유효한 문자 비교 및 이동 테이블이 필요하다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 긴 패턴과 일반 텍스트 검색에 실용적이며 Horspool 등 단순화된 변형도 널리 사용한다. KMP는 선형 최악 시간 보장을 갖는다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]