1.개요
- 보이어모어 알고리즘 역시 kmp 알고리즘과 마찬가지로 패턴과 텍스트 중 패턴을 preprocessing 하는 방식이다.
- kmp 알고리즘과는 반대로 패턴을 텍스트의 특정 위치에 놓고 비교를 할 때
kmp는 패턴의 앞 쪽부터 차례대로 비교를 시작하는 반면 (왼쪽에서 오른쪽)
보이어모어는 패턴의 뒤 쪽부터 차례대로 비교를 시작한다. (오른쪽에서 왼쪽)
2.아이디어
- 브루트포스 방식과 어떤차이점을 가지고 수행시간을 단축시켜주느냐~ 인데.
- 보이어모어 알고리즘에서는 두가지의 큰 아이디어가 있다.
-> Looking-glass heuristic
: 패턴의 뒤 쪽부터 비교를 시작한다.
->Character-jump heuristic
: 패턴을 구성할 수 있는 모든 글자의 마지막 발생위치를 미리 구해서 테이블 형태로 저장해 놓는다.
텍스트와 패턴을 뒤쪽에서부터 비교해 오다가 불일치 발생시 그 때 위치의 텍스트 문자가 패턴의 마지막에 등장한 문자의 위치를
맞춰 패턴을 옮긴다.
이해하기 위한 간단한 이론적 예시는 아래와 같다.
3. 전처리(preprocessing)
- 2번에서 말씀드렸다싶이 전처리 과정은 매우간단하며 패턴을 한번 쓱 스캔하면 되므로 시간도 오래걸리지 않습니다.
- 앞에서부터 보면서 뒤쪽에 등장할 때 마다 그 위치로 문자열테이블을 업데이트 해주시면 되겠습니다.
- 처음에 테이블을 만들어 -1로 초기화 시키고 위의 작업을 수행하면 전처리후에도 여전히 -1값을 가지는 문자는 텍스
트에는 있을 수 있으나 패턴에는 존재하지 않는 문자이므로 이 경우 패턴의 길이만큼 jump를 해주시면 되겠습니다.
4.The BoyerMoore Algorithm
-주의 해야할 점 하나는
mismatch가 발생한 위치에 있는 문자가 현재 패턴의 문자열 위치보다 뒤쪽에 있을경우
그대로 옮겼다가는 패턴이 다시 앞쪽으로 갈 수 있고 무한반복과 중복 처리 등이 발생할 수 있다.
이 경우는 그냥 한칸 뒤로만 옮겨주는 것으로 대체한다.
5. 분석(Analysis)
- 시간 복잡도 : O(n*m+s)
- 최악의 경우를 분석해보면 심지어 브루트포스방식의 시간복잡도인 O(n*m)보다도 s만큼의 시간이 더 걸린다.
- 최악의 경우 예시를 보자면
TEXT= aaaaaaaaaa........a
PATTERN = baaa
-최악의 경우는 문자의 범위가 좁은 DNA Sequence나 이진문자열 같은 곳에서는 발생할 확룰이 꽤 있다.
- 하지만 영어 알파벳이나 한국어 처럼 문자의 범위가 매우 큰 경우 매우 효율적으로 빠르게 동작한다.
'알고리즘 > 문자열(string)' 카테고리의 다른 글
| 2. The KMP 알고리즘 (0) | 2020.10.07 |
|---|---|
| 1. Brute-force 방식 (0) | 2020.10.07 |
