문자열 검색 알고리즘 개념 (브루트포스, KMP, Boyer-Moore)

문자열 검색(String Search)은 본문(T)에서 패턴(P)을 찾는 것이다.

[그림 1] 문자열 검색 설명

 

 

브루트포스, KMP, Boyer-Moore 3가지 알고리즘에 대하여 개념 위주로 알아보고, 비교해보려고 한다. 

01  브루트 포스법(Brute Force)   02  KMP법   03  Boyer-Moore   04 알고리즘 간단 요약 & 비교

 

---

01 브루트 포스법(Brute Force)

brute a.무식한  force n.힘

이를 해석하면 무식한 힘으로 해결한다는 뜻으로 한마디로 단순 무식한 방법이다.  

완전탐색 알고리즘으로 문제에 나와있는 모든 경우의 수를 시험해보는 방법이다. 

[그림 2] 브루트포스법 과정

 

문자열 검색 시에는 패턴의 문자를 하나씩 왼쪽에서 오른쪽으로 이동해가면서

본문의 텍스트 문자와 하나씩 비교해간다. 

 

1. 다른 문자를 만나면 패턴에서 문자를 검사했던 위치 결과를 버리고

2. 다음 텍스트의 위치로 1칸 이동한 다음

3. 다시 패턴의 첫 번째 문자부터 검사한다. 

 

 

브루트 포스법을 이해하기는 가장 쉽지만 문자열 검색시에는 가장 비효율적이다. 

 

---

02 KMP법

D.E. Knuth, J.H. Morris, V.R.Pratt가 거의 같은 시기에 고안했기 때문에 이들 이름의 각 앞글자를 따서 KMP 알고리즘이라 부른다. 

 

브루트 포스법과는 달리 검사했던 위치 결과를 버리지 않고 이를 효율적으로 활용한 알고리즘이다. 

한 마디로 비교할 필요가 없으면 패스하고, 비교할 필요가 없으면 비교를 수행한다는 것이다.

이 때 비교할 필요가 없다는 것을 판단하기 위해서 검사했던 위치 결과가 사용된다.

 

How? 

이동하는 데 있어 경계를 찾고 접두부에서 접미부로 만큼 이동을 해준다. 

 경계가 없을 경우, 문자열 패턴의 길이만큼 이동을 해준다. 

 

이렇게만 보면 무슨말인지 이해가 되지 않을 것이다. 

여기서 먼저 알아야할 개념이 문자열에서 접두부(Prefix)와 접미부(Suffix)이다. 

접두부(Prefix) : 문자열의 머리부분
접미부(Suffix) : 문자열의 꼬리부분

[그림 3]은 접두부 접미부, 경계를 BAABABAA라는 문자를 통해 설명한다. 

[그림 3] 접두부(Prefix), 접미부(Suffix), 경계

 

[그림 3]에 있는 표는 접두부(Prefix)와 접미부(Suffix)를 나타내는 표다. 

경계가 되기 위해서는 접두부와 접미부가 같아야 한다.

이는 표에서 3번째를 통해 확인할 수 있다. 

결국 여기서 접두부와 접미부가 같은 'BAA'에서 이 사이에 값인  'BA'를 경계라고 한다. 

 

[그림 4] KMP 간추린 과정

 

본문(T)과 패턴(P)을 비교하면서 불일치 지점이 발생했을 때 일치하는 값 사이에서 경계를 찾고 이동시켜주면된다. 

조금 더 자세히 설명하자면, 패턴(P)에서 불일치 지점의 왼쪽 부분이 본문(T)과 일치하는 값들이 된다.

 

경계가 2개 이상일 경우 접두부와 접미부가 일치하는 문자열의 개수가 최대가 되었을 때로 설정한다. 

경계 없는 경우, 따라서 접두부와 접미부가 일치하는 값이 없을 때는 문자열 패턴의 길이만큼 이동한다.

 

이동시켜 줄 때는 접두부 시작위치에서 접미부 위치로 이동시켜주고 다시 본문(T)과 패턴(P)을 비교한다. 

 

더 자세한 과정은 [그림 5]에서 확인할 수 있다. 

 

실패함수 (Failure Function)

접두부와 접미부가 일치하는 문자열의 개수를 구할 때 실패함수를 사용한다. KMP에서 실패함수는 매우 중요한 개념이다.

불일치가 발생(실패)했을 때 어떻게 해야하는지 알려준다는 점에서 실패함수라 불린다. 

 

아래 첫 번째 그림을 보고 실패함수가 어떻게 만들어지는 지 확인할 수 있다. 

실패함수를 F(k)라고 할 때, F(k)의 의미는 k번째 인덱스에서 접두사와 접미사가 일치하는 최대길이를 말한다.

 

실패함수를 이용하면 경계를 찾는데 소요되는 비용을 줄일 수 있다. 

실패함수를 먼저 구해놓으면 알고리즘을 동작할 때 이동경로만 보고 진행하기 때문에 매번 경계를 찾는 일을 제거할 수 있다. 

 

[그림 5] KMP 구체적 과정

 

m = F(m-1)으로 초기화를 왜 시켜줄까?

본문(T)과 패턴(P)을 비교할 때는 왼쪽에서 오른쪽으로 비교를 한다. 

m을 2(F(5-1)=F(4))로 초기화 시켜뒀기 때문에  비교 시작 지점을 설정하여 불필요한 비교 횟수를 줄일 수 있다. 

따라서 패턴(P) BAABAB가 있을 때 K=3인 B부터가 하는 게 아닌 K=5인 A 부터 본문(T)의 5의 인덱스 값과 비교를 한다.

 

정리하자면 본문(T)과 비교하기 위해서

패턴(P)의 자리를 이동할 때는 begin 값을 가지고 이동시켜준다.

이동하고나서 비교할 때의 시작지점은 begin과 m을 통해 정해주는 것이다. 

실패함수를 이용해서 begin과 m을 빠르게 구할 수 있다. 

 

KMP법이 한 칸씩 이동해서 비교하는 브루트포스법보다 훨씬 빠른 알고리즘이라는 것을 알 수 있다. 

---

03 Boyer-Moore법

Robert S. Boyer와 J Stother Moore에 의해 개발된 알고리즘이다. 

기존 검색 방법들이 문자열 비교를 왼쪽에서 오른쪽으로 했다면, 보이어-무어 알고리즘은 오른쪽에서 왼쪽으로 문자열을 비교한다. 

그러나 이동(skip)을 할 때는 왼쪽에서 오른쪽으로 하는 일반적 방식이다. 이 때 최대한 많이 건너뛰면서 비교한다. 

 

 크게 두 가지 방식의 탐지 방식을 사용한다. 두 가지 방식 중 더 큰 값만큼 이동하는 방식을 선택하여 패턴 매칭을 시도하게 된다. 

 여기서는 두 가지 방식인 Bad Character Rule과 Good Suffix Rule을 먼저 살펴보고,  실제 Boyer-Moore법에서는 어떻게 혼합하여 비교하는 지에 대하여 다뤄볼 것이다.

 

• Bad Character Rule - 문자값 이용
• Good Suffix Rule  - 문자열 이용 
• BC(Bad Character) & GS(Good Suffix) 혼합 사용

---

• Bad Character Rule

 Bad Character는 현재 비교하려는 문자와 일치하지 않은 전체 문자열의 문자를 말한다.

아래 그림에서 b가 Bad Character를 의미한다.

즉, Bad Character Rule은 본문(T)에서 비교하지 않아도 되는 문자들은 건너 뛰고

비교를 시작해야할 지점을 선택하여 문자 비교를 할 수 있도록 패턴(P)의 위치를 이동시켜주는 것이다. 

여기서 본문의 불일치 지점 문자인 Bad Charater의 값과 일치하는 패턴의 값이 비교를 시작하는 지점이 된다. 

 

이에 대한 구체적인 과정은 [그림 6]을 통해 확인하길 바란다. 

 

[그림 6]Boyer-Moore : Bad Character Rule의 과정

[그림 6]에서 '② 본문의 불일치 지점 문자와 일치하는 패턴의 가장 오른쪽 지점만큼 이동시킨다'

이 말이 충분히 혼란을 줄 수 있다고 생각된다. 나는 한참을 들여다 봤다 :)

 

풀이하자면 위 그림의 Step 1을 보면 '본문의 불일치 지점문자'는 b(Bad Character)가 의미하는 C임을 알 수 있다. 

패턴(P)  CCTTTTGC에서 불일치 지점은  T이다. T를 기준으로 왼쪽 글자를 살펴보면 CCTT이다. 

여기서 '일치하는 패턴'이 의미하는 것이 본문의 불일치 지점문자인 C와 일치하는 패턴 값 C를 말한다. 

 

그렇다면 '일치하는 패턴의 가장 오른쪽'은 무슨 말 일까?

왼쪽글자인 CCTT에서 일치하는 패턴값인 C 중 가장 오른쪽에 있는 값을 말한다. 

따라서 CCTT에서는 두 개의 C를 가지는 데 더 오른쪽에 있는 C를 선택하여 그 지점만큼 이동하라는 것이다. 

 

KMP 알고리즘의 실패함수와 동일하게 패턴에서 얼만큼 이동할 지를 보관하고 있어야 한다. 

 

---

• Good Suffix Rule 

Good Suffix Rule은 불일치 지점이 발생했을 때,

패턴(P)에서 본문(T)과 일치한 지점의 접미부(suffix)와 대응되는 접두부(prefix)를 찾아서 패턴의 위치를 이동시킨다. 

대응되는 접두부를 일치한 지점의 접미부 자리에 이동시켜 다시 비교를 수행하게 된다. 

대응되는 접두부가 없을 경우에는 패턴의 길이만큼 이동한다.

여기서 패턴에서 일치한 지점의 접미부를 Good Suffix라고 본다.

 

이는 KMP법과 굉장히 유사하다.

본문(T)과 패턴(P)을 비교할 때 KMP는 일치한 지점의 접두부를 찾는다. 

그러나 Boyer-Moore의 Good Suffix는 뒤에서 부터 비교하기에 일치한 지점의 접미부를 찾는 것이다.

 

Good Suffix Rule에 대한 구체적 과정은 [그림 7]을 통해 확인할 수 있다. 

 

[그림 7] Boyer-Moore : Good Suffix Rule의 과정

 

[그림 7] Step1에서 패턴  CTTACTTAC에서 TAC까지 일치했고 접미부 TAC와 일치한 접두부 TAC가 있다. 

이를 그만큼 이동시키고 다시 패턴의 오른쪽부터 비교한다.

 

[그림 7] Step2에서 패턴 CTTACTTAC를 살펴보면, 본문과 일치한 부분 TACTTAC이 접두부에서 CTTAC와 일치한다.

이 부분을 맞춰 이동시키고 다시 패턴의 오른쪽부터 검사한다.

 

---

• BC(Bad Character) & GS(Good Suffix) 혼합 사용

본문과 패턴을 비교하는데 불일치 지점이 발생했을 때

Bad Character는 문자값을 이용해서 이동한다면 Good Suffix 는 문자열을 이용해서 이동한다.

그렇기에 주로 문자열이 매칭된 경우에는 Good Suddix를 , 그렇지 않은 경우에는 Bad Character를 사용했을 때 skip 값이 더 크다. 

 

 

[그림 8] Boyer-Moore : 혼합 사용

 

BC (Bad Character)와 GS (Good Suffix) 중에서 하나만으로는 좋은 성능을 내는 것은 어렵다. 

[그림 8] Step1, Step2처럼 한쪽만 사용했을 때는 skip할 수 있지만, 1byte씩 검사해야하는 상황들이 나온다.

Step 1에서의 gs:0, Step 2에서의 bs:0이 1byte씩 검사해야하는 상황이다.

또는 Step3에서는 GS를 사용했을 때 더 많은 skip을 할 수 있지만, BC만을 사용한다면 2byte만 skip하지 못한다.

이처럼 BC, GS값을 최종적으로 비교해서 더 큰방향으로 skip할 수 있는 로직이 되어야한다.

---

04 알고리즘  간단 요약 & 비교 

브루트 포스 

패턴의 문자를 하나씩 왼쪽에서 오른쪽으로 이동해가면서 본문의 텍스트 문자와 하나씩 비교

 

KMP

왼쪽에서 오른쪽으로 이동해가면서 불일치 지점이 발생했을 때

패턴과 본문이 일치하는 값 사이에서 패턴의 접두부와 접미부를 통해 경계를 찾고 이동시켜주면서 비교 

 

Boyer-Moore

오른쪽에서 왼쪽으로 비교해가면서 (이동방향은 왼쪽에서 오른쪽 )

불일치 지점 발생 시  두 가지 방식 중 더 큰 값만큼 이동하는 방식을 선택하여 패턴 매칭을 시도

(두 가지 방식 : Bad Character 문자값 이용해서 이동 / Good Suffix  문자열 이용해서 이동)

 

	브루트 포스	KMP	Boyer-Moore
비교기준	문자값	문자열	문자값 & 문자열 혼합 사용
비교검사 방향	→ (왼쪽에서 오른쪽)	→ (왼쪽에서 오른쪽)	← (오른쪽에서 왼쪽)
이동간격	한 칸	패턴(P) 글자수 이내	패턴(P) 글자수 이내
이동경로 저장여부	x	O(실패함수)	O(이동경로 테이블)
시간복잡도	O(NM)	O(N+M)	Best : O(N+M/M) Worst : O(NM)

본문(T)의 문자열 길이 : N   /  패턴(P)의 문자열 길이 : M

---

※ 출저

- 브루트포스 알고리즘 : https://hcr3066.tistory.com/26

알고리즘 기법[전체 탐색] - 브루트 포스(brute force)

- KMP 알고리즘 1 : https://carstart.tistory.com/143

[알고리즘] KMP 알고리즘 (문자열 검색 #2)

- KMP 알고리즘 2 : https://baeharam.github.io/posts/algorithm/kmp/

[알고리즘] KMP 알고리즘

- Boyer-Moore : https://m.blog.naver.com/PostView.nhn?blogId=cestlavie_01&logNo=221055516242&proxyReferer=https:%2F%2Fwww.google.com%2F

문자열 검색 - Boyer-Moore algorithm