L15 - Boyer-Moore Algorithm

 

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한
 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다

 

 

 

이전 포스팅에서 String Match에 대해 O(n + m) = O(n)의 시간복잡도를 가진 KMP 알고리즘을 다뤘었음

 

이번에는 최선의 경우 O(n)보다 더 빠르게 매칭할 수 있는 알고리즘에 대해 다룰 예정

 

String Match 관련 포스팅 참고

 

https://hanjungyo.tistory.com/101

L14 - KMP Algorithm

 

 

Boyer-Moore-Horspool Algorithm

 

앞서 말했듯이 최선의 경우 O(n) 보다 더 빠르게 String Match를 할 수 있을까에서 부터 시작됨

 

Boyer-Moore-Horspool 알고리즘의 아이디어는

 

Bad Character Rule로 불필요한 비교를 건너뛰는 것임

 

=> Bad Character Rule이란 문서 A의 마지막 비교 문자를 확인하여 매치 가능성을 확인하는 것임

 

예시 1

 

우선 패턴이 일치하지 않는걸 확인했고 문서 A에서 마지막 비교문자 "b"는 P에 없기 때문에 5칸을 건너뛸 수 있음

 

예시 2

 

위 상황과 동일하게 패턴이 일치하지 않는걸 확인했고

 

문서 A에서 마지막 비교문자 "i"는 P의 2번째에 있기 때문에 3칸을 건너뛸 수 있음

 

 

이를 위해 jump라는 dict를 도입

 

마지막 비교문자가 어떤 것인지에 따라 패턴 매칭시 얼마나 건너뛸지를 기록해놓는 것인데

 

만약 P = "rational" 같이 중복된 문자가 있을 경우에는

 

 

더 작은 jump를 선택해야 특정 경우가 제외되지 않고 match가 가능함

 

jump를 만들 때 python을 기준으로 default dict를 사용하여 기타 문자가 올 경우에 대해 설정을 해놓고

중복 문자의 경우는 앞에서 부터 차례대로 dict에 넣으면 어쩌피 덮어 씌워지기 때문에 괜찮음

 

 

예시 상황의 흐름을 보면 이해가 훨씬 잘됨

 

 

 

 

우선 pseudo code부터 살펴보면 compute_jump로 jump dict를 만들었고

while문을 통해 현재 A의 비교 문자열과 패턴 P의 뒷쪽부터 차례로 검사하며 일치하지 않는 경우 i를 jump에서 마지막 비교 문자의 점프 숫자를 확인하여 이동시킴 

 

 

위 상황에서는 일단 패턴이 일치하지 않는걸 확인했고 마지막 비교문자가 문서 A의 "d" 였음

 

근데 이 "d"는 패턴에 속하지 않는 문자이므로 jump의 기타에 있는 4만큼 건너뛰게되됨

 



 

그럼 위 그림의 상황이 되고 4칸 건너뛰게 되어 다시 문서 A의 abac와 패턴 abac를 뒤에서 부터 while문으로 검색하게 됨

 

이 경우 패턴이 일치하므로 i를 return해주고 jump dict에서 마지막 비교 문자인 c를 보고 4만큼 건너뛰어 다시 매칭을 시작함

 

 

Boyer-Moore Algorithm

 

Boyer-Moore-Horspool 알고리즘의 경우 Bad Character Rule만 활용했는데

 

Boyer-Moore 알고리즘의 경우 Bad Character Rule과 Good Suffix Rule을 통해 불필요한 비교를 건너뜀

 

=> 두 Rule 중에 더 많이 건너뛰는 것을 선택

 

 

 

Bad Character Rule의 경우 틀린걸 기준으로 건너뛰고

Good Suffix Rule의 경우 일치하는 문자열이 중복되는게 있나를 확인하고 건너뛰게됨

 

Good Suffix Rule이 선택되는 경우

 

위 상황과 같이 Bad Character Rule이 뒤로 밀리는 경우가 있을 수 있음

 

=> 이럴 경우 더 많이 건너뛰는 Good Suffix Rule을 선택해서 다음 매칭을 진행함

 

Complexity Analysis

 

최악의 경우 시간복잡도가 O(mn)임

 

=> 건너뛰기가 한 번도 발생하지 않은 경우 계속 1칸씩 이동하므로 (n-m+1) 회 반복하며 패턴 전체 m 을 비교하므로

 

최선의 경우 시간복잡도는 O(n/m)임

 

=> 항상 건너뛰기가 발생해서 패턴 만큼 건너뛰게 되면 (n-m+1) /m 회 반복하며 O(1)의 비교를 수행함

 

(문서 A와 패턴 P 사이에 일치하는 문자가 전혀 없는 경우를 생각하면됨)

 

대부분의 상황에서 KMP 알고리즘보다 빠르게 동작