[문자열 매칭] 보이어무어(Boyer-Moore) - Good Suffix Heuristics

 

✅ 개요

 

문자열 매칭 알고리즘 중 보이어무어에 대해 알게 된지 2일차...

 

보이어무어를 제대로 알기 위해 핵심 방식 2가지를 이해해야하는데,

 

어제는 나쁜문자이동방식을 공부했었다.

https://jie0025.tistory.com/537

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

 

 

오늘은 착한접미부이동방식에 대해 공부를 해보자.

 

 

✅ 보이어무어 (Boyer-Moore)

 

어떤 문자열에서  찾고자하는 패턴을 찾을때 효율적으로 처리할 수 있는 알고리즘

 

 
✍️ 보이어무어의 핵심

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

 
✍️ 보이어무어는 Skip 배열을 만들어둔다. 
문자가 일치하지 않을 경우에 얼마만큼 이동시킬지 저장하는 배열

 

 

 

⏺ 착한 접미부 이동 방식 (Good Suffix Method)

 

😵 나쁜문자이동이 불가능한 케이스

어제 공부한 나쁜문자 이동방식에서 한가지 문제가 발생한다.

 

1. 만약 나쁜 문자를 발견하고

2. 그 문자가 패턴에 존재하는데

3. 패턴에 존재하는 나쁜문자가 이미 오른쪽에 존재하는 경우

 

나쁜문자이동방식을 활용할 수 없게 된다.

 

 

아래 예시를 보자. 

text : BAABABBAC에서

pattern : ABAB를 찾고자

 

나쁜문자이동방식을 처리했을때

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

 

1) A와 B에서 불일치가 발생하여, 나쁜문자는 A가 된다. 

2) Skip Table에서는 A의 위치를 가장 우측에 가까운 문자 기준으로 저장하기 떄문에,

이미 Pattern에 존재하는 이동시킬 A의 위치가 더 오른쪽에 존재한다. 

 

 

😉 착한 접미부 이동

나쁜 문자 이동 방식의 경우 1칸만 이동하는 경우도 발생하는데, 

착한접미부 이동을 사용하면, 그런 상황에서 최대 이동 거리를 선택할 수 있다.

 

 

나쁜 문자가 발생했다면, 그 오른쪽의 문자들은 일치했다는 것이다.

이 일치한 문자들을 착한 접미부라고 한다.

 

패턴에서 착한접미부와 일치하는게 존재하는지 찾는다.



 

✔️ 이때 존재하면, 착한 접미부와 일치시켜 오른쪽으로 Shift해주면 된다. 

 

1️⃣ 착한접미부와 일치하는 문자열이 패턴에 존재하는지 찾음

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

 

2️⃣ 오른쪽으로 shift : 착한접미부와 자리가 일치하도록

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

 

3️⃣ 다시 우측부터 확인하고, 패턴이 모두 일치하는것을 발견

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

 

 

✔️ 만약 존재하지 않는다면?

 

✍️ 착한 접미부의 문자열을 왼쪽부터 하나씩 줄여가며 반복해서 조사한다.

 

Text : BCABCAABC이고,

Pattern은 CAABCA라고 가정 

 

ABCA가 착한 접미부

C와 A에서 불일치가 발생

 

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

 

 

착한접미부보다 왼쪽에서 ABCA를 발견할 수 없다.  --  CA

 

착한접미부의 왼쪽한개  (A) 를 지운다

BCA역시 발견할 수 없다.

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

 

 

착한접미부의 왼쪽한개  (B) 를 지운다

CA를 발견했다.

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

 

CA를 착한접미부 CA와 맞추어 Shift한다.

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

 

 

✍️ 만약 위의 과정을 했는데도 완전 불일치라면? 

 

패턴의 길이만큼 이동시킨 후 비교한다.

 

 

 

아래와 같은 상황으로 변경시키면

위의 상황과는 다른, 완전 불일치가 일어난다.

 

 

Text : BCABCAABC

Pattern은 EDABC 

 

 

ABC가 착한 접미부

C와 D에서 불일치가 발생

 

 

착한접미부보다 왼쪽에서    ABC  를 발견할 수 없다.  --  왼쪽에는 ED만 있다.

Text	B	C	A	B	C	A	A	B	C
Pattern	E	D	A	B	C

 

 

착한접미부의 왼쪽한개  (A) 를 지운다

  BC   를  발견할 수 없다. - EDA

Text	B	C	A	B	C	A	A	B	C
Pattern	E	D	A	B	C

 

 

착한접미부의 왼쪽한개  (B) 를 지운다

  C  를  발견할 수 없다. - EDAB

Text	B	C	A	B	C	A	A	B	C
Pattern	E	D	A	B	C

 

결국 완전불일치가 일어났으므로, Pattern의 길이만큼 우측으로 shift하고

다시 탐색을 시작하게 된다.

Text	B	C	A	B	C	A	A	B	C ...
Pattern						E	D	A	B ...

 

 

 

 

오늘은 착한 접미부 방식까지 공부를 했다. 

 

보이어무어의 두가지 방식이 얼마나 문자열 탐색을 효율적으로 할 수 있는지 이해할 수 있는 계기가 되어서 좋다!

 

 

---

 

References

https://youtu.be/mXQtunIEo0k

https://yoongrammer.tistory.com/95