Boyer-Moore Algorithm
보이어-무어 알고리즘
* String Matching Algorithms (문자열 매칭 알고리즘) (URL)
- 전체 문자열 \(\texttt{string[1...m]}\)에서 부분 문자열 \(\texttt{pattern[1...m]}\)을 찾아내는데,
최악의 경우에는, \(\Theta(n*m)\) 시간 동안 수행되지만,
평균적으로 \(\Theta(n)\)과 \(\Theta({n \over m})\) 사이의 시간 동안 수행되어
실무에서 KMP Algorithm보다 더 자주 쓰이는 알고리즘이다.
(대체로, \(\Theta({n \over m})\)에 더 가까운 성능을 보인다고 한다.)
Mechanism (원리)
- Mismatching이 발생했을 때,
Bad-Character Heuristic(불일치 문자 휴리스틱)과 Good-Suffix Heuristic(일치 접미부 휴리스틱) 중
더 많은 문자를 점프할 수 있는 결과를 선택하여, 문자들을 점프해나간다.
- 간단한 구현을 위해 Bad-Character Heuristic만을 사용한 알고리즘은 Boyer-Moore-Horspool Algorithm이라 부른다.
(실제로, Bad-Character Heuristic만을 사용해도 Performance적 측면에서 큰 차이가 없다고 한다.)
Bad-Character Heuristic (불일치 문자 휴리스틱)
- 전체 문자열 \(\texttt{str[i...i+n-1]}\)에서 부분 문자열 \(\texttt{pat[0...m-1]}\)의 일치 여부를 비교하는데,
이 때, 문자열의 맨 마지막부터 비교를 시작한다.
(즉, \(\texttt{str[i+n-1]}\)과 \(\texttt{pat[m-1]}\)을 비교한다.)
1) \(\texttt{str[i...i+n-1]}\)과 \(\texttt{pat[0...m-1]}\)이 모든 부분에서 정확히 일치한다면,
\(\texttt{str[i]}\)에서 일치가 발생했음을 출력(기록)한다.
2) \(\texttt{str[i...i+n-1]}\)과 \(\texttt{pat[0...m-1]}\)에서 Mismatch가 발생했다면,
\(\texttt{i}\)를 \(\texttt{i+jump}\)로 갱신한다.
* Computation of \(\texttt{jump}\) (in Bad-Character Heuristic Method)
- \(\texttt{str[i+n-1]}\) 문자(\(\texttt{str}\)의 맨 오른쪽 문자)를 기준으로,
\(\texttt{pat}\)의 모든 문자들과 비교했을 때, 몇 칸을 \(\texttt{jump}\)해도 되는지를 계산한다.
(예를 들어, \(\texttt{str[i+n-1]}\) 문자가 \(\texttt{pat}\)에 아예 존재하지 않을 경우, \(\texttt{pat}\)의 길이 만큼을 통채로 넘겨도 문제가 없다.)
Example 1. \(\texttt{pat[] = "tiger"}\)에 대한 \(\texttt{jump}\)값 계산
\(\texttt{str[i+m-1]}\) |
\(\texttt{'t'}\) |
\(\texttt{'i'}\) |
\(\texttt{'g'}\) |
\(\texttt{'e'}\) |
\(\texttt{'r'}\) |
Otherwise |
\(\texttt{jump}\) |
4 |
3 |
2 |
1 |
5 (=\(\texttt{m}\)) |
5 (\(\texttt{m}\)) |
- \(\texttt{str[i+m-1]}\) (=맨 오른쪽 글자)가 \(\texttt{'t'}\)인 상황에서 \(\texttt{str[i...i+m-1]}\)과 \(\texttt{pat[0...m-1]}\)간의 Mismatch가 발생했을 경우,
\(\texttt{jump['t']}\)값이 4이므로, 4칸 건너뛰어도 된다.
(즉, \(\texttt{i = i+4}\)로 Update하여 다시 문자열 비교를 수행한다.)
Step 1 |
 |
- \(\texttt{str[0...4]}\)와 \(\texttt{pat}\)와의 비교: Mismatch를 감지한 후 5칸을 건너뛴다. |
Step 2 |
 |
- \(\texttt{str[5...9]}\)와 \(\texttt{pat}\)와의 비교: Mismatch를 감지한 후 한 칸만 건너뛰어 \(\texttt{str}\)의 \(\texttt{'e'}\)와 \(\texttt{pat}\)의 \(\texttt{'e'}\)를 끼워 맞춘다. |
Step 3 |
 |
- \(\texttt{str[6...10]}\)와 \(\texttt{pat}\)와의 비교: Mismatch를 감지한 후 다섯 칸을 건너뛴다. |
Step 4 |
 |
- \(\texttt{str[11...15]}\)와 \(\texttt{pat}\)와의 비교: 두 개의 문자는 Matching되었지만, \(\texttt{str[13]}\)부터 Mismatching이 발생했으므로, \(\texttt{str[15]}\)에 대한 \(\texttt{jump}\)값 만큼을 또 건너뛴다. |
Example 2. \(\texttt{pat[] = "rational"}\)에 대한 \(\texttt{jump}\)값 계산
\(\texttt{str[i+m-1]}\) |
\(\texttt{'r'}\) |
\(\texttt{'a'}\) |
\(\texttt{'t'}\) |
\(\texttt{'i'}\) |
\(\texttt{'o'}\) |
\(\texttt{'n'}\) |
\(\texttt{'a'}\) |
\(\texttt{'l'}\) |
Otherwise |
| \(\texttt{jump}\) |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
8 |
8 |
- \(\texttt{"rational"}\)에는 \(\texttt{'a'}\)가 두 번 포함되어 있으며, \(\texttt{jump}\)값은 각각 6, 1이다.
- 이렇게 같은 문자가 다수로 존재하는 경우, \(\texttt{jump}\)값은 가장 작은 값으로 결정해야 한다.
(\(\texttt{str}\)과 \(\texttt{pat}\)를 오른쪽부터 대조하기 시작하는데,
오른쪽에 있는 \(\texttt{'a'}\)부터 \(\texttt{str}\)과 \(\texttt{pat}\)가 일치하게 되는 일말의 가능성이 있기 때문이다.)
- 즉, \(\texttt{'a'}\)의 \(\texttt{jump}\)값은 1이어야 하고, \(\texttt{jump}\)값을 아래 표와 같이 완성할 수 있다.
\(\texttt{str[i+m-1]}\) |
\(\texttt{'r'}\) |
\(\texttt{'t'}\) |
\(\texttt{'i'}\) |
\(\texttt{'o'}\) |
\(\texttt{'n'}\) |
\(\texttt{'a'}\) |
\(\texttt{'l'}\) |
Otherwise |
\(\texttt{jump}\) |
7 |
5 |
4 |
3 |
2 |
1 |
8 |
8 |
Good-Suffix Heuristic (일치 접미부 휴리스틱)
Implementation
* GitHub (URL)
Performance (성능)
Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)
