[문자열 매칭] 보이어무어(Boyer-Moore) - Bad Character Heuristic

✅ 개요

어제 문자열 매칭 알고리즘 중 KMP에 대해 알아보았다.

[알고리즘] 문자열 매칭 KMP (동작방식,수도코드)

 
 
그리고 비교군으로 보이어무어라는 문자열 매칭 알고리즘이 존재하는걸 알게되었다.
 
 
존재하는걸 알았으니, 해당 알고리즘이 뭔지, 동작방식까지 이해해보자.
 
 

✅ 보이어무어 (Boyer-Moore)

 

• 보이어무어 알고리즘도 KMP와 마찬가지로 모든경우를 계산하지 않고, 반복되는 연산을 줄인다.
• 보이어무어는 문자열 매칭이 마지막에 틀릴 가능성이 높다는 특징을 이용한다.
• 문자열의 가장 뒷부분을 비교하고, 다르면 일정 길이만큼 이동하며 비교를 계속한다.
• 대부분의 워드프로세스, RDB, JAVA언어에서도 검색기능에서 사용된다.
  
• https://stackoverflow.com/questions/20005690/stringutils-contains-of-apache-and-boyer-moore-string-search-algorithm

 

🤔 복잡도

• 일반적인 복잡도 : O(N)보다 작다고 한다.
• 최악의 경우 :  O(N*M)
• N : text의 길이
• M : pattern의 길이 (text에 존재하는지 찾으려는 문자열)

 
최악의 경우가 O(NM)이고  KMP는 O(N+M)인데, 
내가 사용하고자 하는 상황에서는 최악의 경우가 나올 확률이 0에 수렴할 것 같아 
보이어무어도 함께 고민해보고, 구현해서 성능 비교를 해야겠다 생각을 했다.
 

---

 
 
✍️ 보이어무어의 핵심은 다음 두가지 방식이다.

• 나쁜문자이동 방식 (Bad Character Method)
• 착한 접미부이동 방식 (Good Suffix Method)

 
✍️ 보이어무어는 Skip 배열을 만들어둔다. 
문자가 일치하지 않을 경우에 얼마만큼 이동시킬지 저장하는 배열
 
 
 
여기까지 읽기만 하면 당연히 이해가 안될것이다.
아래 그림을 세세하게 그렸으니 skip배열까지 아래에서 함께 이해하자.

 

 

⏺ 나쁜문자 이동 방식 (Bad Character Method)

나쁜문자 : 본문의 문자열과 패턴이 불일치하는 문자
 
나쁜 문자를 발견하면, 패턴의 나쁜문자와 본문문자의 나쁜문자위치를 일치하게 만드는 방식이다.
 

1. text에서 pattern을 발견하고자 한다. 
2. pattern의 가장 오른쪽부터 비교한다.
3. pattern과 text의 비교 상황에서 매칭이 안되는 상황이 발생하면, 그 상황에서의 text문자를 <나쁜문자>라고 한다.
4. 나쁜문자가 pattern에 존재하는지 체크한다. 존재하면, 미리 만들어둔 skip 배열에서 <나쁜문자>는 몇만큼 이동시키면 되는지 확인하고, 그만큼 pattern을 우측으로 이동시킨다.

 

👩‍💻 Skip 배열 만드는 방법

BBAC 를 예로 들겠다. 
가장 오른쪽 인덱스(C 가 위치한 곳)를 기준으로
해당 인덱스까지 우측으로 이동시키려면 몇칸 이동해야하는지 저장하면 된다.
 
중복 값(B)의 경우엔 더 오른쪽것을 기준으로 저장한다.
 
C는 가장 오른쪽에 위치하기 위해선 우측으로 0칸 이동하면 된다.
A는 가장 오른쪽에 위치하기 위해선 우측으로 1칸 이동하면 된다.
B는 여러개가 존재하는데, B중 가장 우측에 있는것이   가장 오른쪽에 위치하기 위해선 우측으로 2칸 이동하면 된다.
 
 
➡️ BBAC - Skip 배열

A	B	C
1	2	0

 
 

좀더 이해하기 쉽게 내가 공부하면서 그린 그림을 추가한다. 

 

 
Text  =  BAABABBAC  에서
Pattern =  BBAC  를 발견하는 상황이다.
 
 

👩‍💻 Process 1

Text	B	A	A	B	A	B	B	A	C
Pattern	B	B	A	C

 
가장 오른쪽의 C를 확인했는데 B와 불일치가 일어났다.
여기에서 나쁜문자는 B이고, 
 
Skip 배열을 보자. 
B는 2칸 우측으로 이동하면된다.  

A	B	C
1	2	0

 
전체적으로 2칸 밀고 Process2를 진행한다.
 

👩‍💻 Process 2 

Text	B	A	A	B	A	B	B	A	C
Pattern			B	B	A	C

 
두번째에서도 가장 오른쪽의 C를 확인했는데 B와 불일치가 일어났다.
여기에서 나쁜문자는 B이고, B는 2칸 우측으로 이동하면된다. 
 
전체적으로 2칸 밀고 Process3를 진행한다.
 

👩‍💻 Process 3

Text	B	A	A	B	A	B	B	A	C
Pattern					B	B	A	C

 
세번째에서는 가장 오른쪽의 C를 확인했는데 A와 불일치가 일어났다.

여기에서 나쁜문자는 A이고, A는 1칸 우측으로 이동하면된다. 

 
전체적으로 1칸 밀고 Process4를 진행한다.

 

 

👩‍💻 Process 4

Text	B	A	A	B	A	B	B	A	C
Pattern						B	B	A	C

 
우측부터 차례대로 매칭시켜보았는데, 전부 일치가 되었다. 
발견후 Pattern이 더이상 우측으로 이동할곳이 없어 Process도 종료된다.
 
 
 

 

오늘은 피곤하니
착한 접미부 이동 방식 (Good Suffix Method)은 내일 블로깅하겠다 😉

 
 
 

---

references
https://youtu.be/mXQtunIEo0k
https://yoongrammer.tistory.com/94