Boyer & Moore Algorithm (보이어&무어 알고리즘)

• 문자열 패턴을 찾는 알고리즘
  1. Naive Algorithm : 가장 쉽게 생각할 수 있는, O(N^2)의 전체 탐색 알고리즘이다.(Brute-Force Algorithm)
  2. Rabin & Karp Algorithm : 해시를 이용한 문자열 탐색 알고리즘이다.
  3. Boyer & Moore Algorithm : 일반적으로 가장 빠른 알고리즘이다.
  4. Suffix Tree / Array : 접미사 트리/배열이라고 불리는 테이블을 이용한 알고리즘이다.
  5. KMP : Knuth, Morris, Prett 3명이서 만든 알고리즘으로, 접두사와 접미사를 이용해서 패턴을 찾는다.
• 위의 5개 중에서 이번에는 Boyer & Moore Algorithm에 대해서 정리해보고자 한다.
  • KMP 알고리즘의 개선판이라고 할 수 있다.
  • Worst case는 O(N)이지만 평균 O(N/M)의 시간복잡도를 가진다고 한다.
  • 오른쪽에서 왼쪽으로 String을 검색한다. (뒤에서 부터 확인 하는 방법)
  • String을 옮기는 기준은 조건에 맞는 칸 수 만큼 옮기면서 비교해나간다고 보면 된다.
  • 예를 들어, 주어진 String은 'STRING STARTING CONSISTING' / 찾으려고 하는 패턴은 'STING' 이다.

    G	N	I	T	S	다른 모든 문자
    0	1	2	3	4	5

    - 오른쪽에서 왼쪽을 기준으로, 주어진 String과 비교하였을 때, 표와 같은 칸 수를 옮긴다. 
    - 위의 표를 바탕으로, 패턴을 찾는 것을 보면 이해가 될 것이다.

1.  미스 매칭된 문자열 N은 위의 표대로 1칸만 이동하게 된다.

2. 1칸 움직인 것을 확인 할 수 있다. 다음으로는 R에서 미스매칭이 된다. R은 패턴에 존재하지 않음으로, 5칸 이동한다.

3.  5칸을 이동한 후에도, 똑같이 R이 미스매칭이다. 동일하게 5칸을 이동한다.

4.  G와 매칭이 되는 문자열이 없다. 이 부분도 다른 모든 문자 조건에 속해서 5칸을 이동한다.

5. 다음으로는 I에서 미스매칭이 된다. 2칸 이동한다.

 

 

6. 다음으로는 T가 미스매칭이 된다. 3칸 이동한다.

7. 찾고 싶었던 STING이라는 패턴을 찾을 수 있다.

 

Boyer & Moore Algorithm 알고리즘에 대해서 정리를 해보았다.

사진으로 보면 훨씬 이해가 빠를 것이라고 생각한다. 관련된 문제 및 코드는 풀어보고 차후에 업데이트 할 예정이다.