크래프톤 정글 6기 TIL - Review | 보이어-무어 알고리즘

진짜 오랜만에 쓴다..

정글 중반기에 들어가면서,, 할게 너무 많고 블로그에 "정리"를 하는거 자체도 힘들어서.. 공부하면서 노션에다 기록했더니 TIL을 안쓰는 사람처럼 보여버렸다..

수료를 하고나서~ 좀 쉬다가!!

정글 콤파스 보면서 놓쳤던 부분들 복습하는 중인데, 여기다가 정리를 해보려구 한다.

나름 복습할 때 도움이 많이 되었다! 키키

---

✅ 보이어 - 무어를 공부하기 전에....

1. 부르투 포스 알고리즘

2. KMP 알고리즘 

에 대해 먼저 공부하는 것을 추천 !

---

 

Boyer - Moore algorithm( 보이어 무어 알고리즘 )

문자열 검색에 사용되는 알고리즘이다.

불필요한 것을 건너뛰고. 검색을 빠르게 하는 것이 주 목표.

워드 검색 기능에서 사용된다.

 

보이어-무어 알고리즘은 보통 상황에서 문자열은 앞부분보다는

뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다.

그래서 오른쪽끝부터 비교하게 된다!

 

 

Bad Character Rule

- 주어진 Text에서 특정 Pattern의 문자열을 찾는 방법.

- 일일이 비교하는 brute-force method보다 효율적.

- 찾고자 하는 문자열 Pattern에 대한 문자열내 저장위치를 알아야 함.

- 앞의 문자부터 비교하지 않고 뒤의 문자부터 비교.

- 문자(Character)가 일치하지 않을 때 사용.

 

 

아래와 같이 Text안에서 Pattern(P)가 있는지 검색을 해본다고 하자.

 

1. Skip Table을 만든다.

문자를 비교하다가  문자가 일치 하지 않을 때

얼만큼 패턴을 이동시킬지 결정하는 테이블이다.

Patter의 길이는 4 이니까, 위와 같이 계산해준다.

 

2. Pattern의 우측부터 차례로 비교를 한다.

불일치 할 경우 Text의 문자가 Pattern에 있는지 검색을 한다.

만약, Pattern에 없을 경우 Skip table의 * 일 경우 만큼 문자를 이동한다.

 

3. 다시 우측부터 비교를 하는데,

T, A는 일치하고 다음 A는 일치하지 않는다.

여기서 A가 패턴에 존재 하는지 검사를 하는데, 현재 남은 패턴 문자들 내에서는 존재하지 않기 때문에 

일치 하지 않는 문자의 개수 만큼 Pattern을 이동시킨다.

 

4. 다시 우측부터 비교를 한다.

C와 T는 일치하지 않지만, Text의 C는 Pattern에 존재한다.

Skip Table에서 C의 값 만큼 이동한다.

 

5. 다시 우측부터 비교를 한다.

모두 일치하므로 검색은 종료된다.

 

Boyer-Moore: Bad Character Rule 효율

1 ) Brute-Force 방법과 달리 모든 문자를 순회하면서 비교하지 않아도 되므로 더 효율적인 비교 가능.
2 ) 선형적 시간 복잡도를 가짐에도 다른 패턴 매칭 알고리즘에 비해 우수한 성능을 가짐.
3 ) Text 길이가 N개의 문자열일 때, 패턴의 길이 M만큼 비교 수행.

O(N*M)