[Algorithm] [String Matching Problem] Knuth-Morris-Pratt Algorithm 총 정리 및 예시

 

문자열 매칭 문제를 해결하는 Knuth-Morris-Pratt Algorithm 에 대해서 공부해보자.

 

 

 

문자열 매칭 문제란?

 

문자열에 주어진 패턴(특정 문자열)이 몇번 나타나는 지 찾는 문제

 

 

 

 

 

Knuth-Morris-Pratt Algorithm 소개

 

Text T = "bacbababaabcbab" 

Pattern P = "ababaca"

 

 

 

문자열 T에서 패턴 P를 찾는 과정에서

처음 index부터 차례로 비교하다가

 

 

 

 

 

 

이렇게 일부가 매칭 되다가 틀렸다면..!

 

일반 적인 매칭 방법에서는

패턴이 시작한 부분(ababa 의 맨 앞 a) 의 그 다음 부분 (ababa 의 앞에 있는 b) 에서

 

 

 

 

다시 매칭을 시작해야 한다.

 

 

이 것보다 더 효율 적으로 하는 방법은 없을까?

 

 

 

그러니까 어차피 b 부터 시작하면 패턴이 a 부터 시작하니까 바로 틀릴 텐데

그걸 알고 b는 건너 뛰고 그 다음 a 부터 시작하게 끔 할 수는 없을까?

 

 

 

이렇 듯 , Knuth-Morris-Pratt Algorithm은

Text에서 pattern을 매칭할 때 불필요하고 반복되는 매칭들은 미리 알고 건너 뛰는 방법이다.

그 과정에서 접두사와 접미사의 개념을 활용한다.

 

 

 

---

 

 

이것은 말로 설명이 너무 어렵기 때문에 예시와 함께 보자

 

 

 

 

우리가 먼저 할 일은 다음과 같이 pattern P가 있을 때

pattern P에서 Prefix Function을 구하는 것이다.

 

 

Prefix Function : π

 

π(a) = b

 

a : 패턴의 매칭된 길이

b : 그 다음 패턴이 매칭될 수 있는 최대 길이

 

 

 

a, b도 직접 해봐야 어떤 값인 지 짐작이 갈 것이다.

 

 

Prefix Function구하기

 

1)   a 만큼 Pattern String을 꺼낸다.

2)   Pattern을 하나씩 이동 시킨다.

3)   1)에서의 Pattern과 2)로 인해 하나씩 이동되는 Pattern이 겹치는 부분이 전부 같은 것을 찾는다.

(다른 것 중 맨 앞을 빨간색으로 마킹 해두었다.)

4)   찾은 것들 중 가장 겹치는 것이 가장 많은 갯수가 b이다.

 

그렇게 a와 b를 구하며 Pattern의 Prefix Function 값을 구할 수 있다.

 

 

 

Ex 1)

 

ㅠ(10) 구하기 (a = 10 일 때) 

 

 

1 2 3 4 5 6 7 8 9 10

a b a b a b a b c a                                 ( X )

   a b a b a b a b c a                              ( X )

      a b a b a b a b c a                           ( X )

         a b a b a b a b c a                        ( X )

            a b a b a b a b c a                     ( X ) 

               a b a b a b a b c a                  ( X )

                  a b a b a b a b c a               ( X )

                     a b a b a b a b c a            ( X )

                        a b a b a b a b c a         ( X )

                           a b a b a b a b c a      ( O )

 

 

a 가 10 일 때 b 는 1 이다.

 

 

 

 

Ex 2)

 

ㅠ(9) 구하기 (a = 9 일 때)

 

9 이기 때문에 pattern string의 9개 만 꺼낸다.

 

 

 

1 2 3 4 5 6 7 8 9 10

a b a b a b a b c                                    ( X )

   a b a b a b a b c a                              ( X )

      a b a b a b a b c a                           ( X )

         a b a b a b a b c a                        ( X )

            a b a b a b a b c a                     ( X ) 

               a b a b a b a b c a                  ( X )

                  a b a b a b a b c a               ( X )

                     a b a b a b a b c a            ( X )

                        a b a b a b a b c a         ( X )

                

 

a = 9 일때 b = 0 이다.

 

 

 

Ex 3)

 

ㅠ(9) 구하기 (a = 9 일 때)

 

8 이기 때문에 pattern string의 8개 만 꺼낸다.

 

 

1 2 3 4 5 6 7 8 9 10

a b a b a b a b                                       ( X )

   a b a b a b a b c a                              ( X )

      a b a b a b a b c a                           ( O )

         a b a b a b a b c a                        ( X )

            a b a b a b a b c a                     ( O ) 

               a b a b a b a b c a                  ( X )

                  a b a b a b a b c a               ( O )

                     a b a b a b a b c a            ( X )

                       

 

a = 8 일때 b = 6 이다.

 

 

 

이런 방식으로 구하는 것이다.

 

쭈욱 구해보면

 

 

π Prefix Function

a  1  2  3  4  5  6  7  8  9  10
b  0  0  1  2  3  4  5  6  0  1


보통 아래 처럼 표시

a  1  2  3  4  5  6  7  8  9  10
π  0  0  1  2  3  4  5  6  0  1

 

 

위를 풀다 보면 눈치 챘겠지만

 

비교 기준이 되는 문자열의 접미사 부분과

비교를 하는 (이동 된 문자열) 문자열의 접두사 부분이 최대 몇 개가 같은지를 찾아주는 함수이다.

 

접두사 , 접미사 개념을 활용했다고 볼 수 있다.

 

 

 

 

 

<< 흐름 이해 >>

 

 

이 함수는 패턴과 문자열 매칭 중에 매칭이 실패 되었을 때!

몇 개의 문자열이 매칭에 성공했었는지 (a)의 정보를 통해

그 다음 매칭은 위 매칭이 실패 되었던 index 까지 몇 글자가 매칭 되어 있는 지(b) 를 알게 해줘서

매칭이 실패하더라도 앞으로 다시 돌아오지 않고 (b) 정보를 통해 계속 진행할 수 있다.

 

 

 

Compute-Prefix-Function 의 시간 복잡도

 

Θ(m)

 

 

 

 

---

 

 

이제 Prefix Function을 구했으니 그것으로 패턴을 구하는 KMP-Matcher를 알아보자

 

 

 

알고리듬

 

 

텍스트의 인덱스와 패턴의 인덱스 를 각각 i와 q라고 하자

 

먼저 Compute-Prefix-Function을 통해 π를 구한다.

 

i를 하나씩 증가시키며 패턴과 일치하는 지 비교 한다.

비교 하면서 생기는 처리 해야 할 CASE 3 가지가 있다.

 

 

Case 1) 첫 번째 패턴 문자와 텍스트의 문자가 다를 때  ->  텍스트의 인덱스 +1
Case 2) 첫 번째가 아닌 패턴 문자와 텍스트의 문자가 다를 때  ->  패턴 인덱스 (q) 는 π(q)로 바뀜 , 텍스트 인덱스 그대로
Case 3) 매치가 일어났을 때 -> 패턴 인덱스 + 1 , 텍스트 인덱스 + 1

 

 

 

 

 

Sudo Code

 

 

 

 

 

코드 설명

 

while   ->  조건 true라면  case 2)

if P[q+1] = T[i]   ->   case 3)

if q = m    ->    패턴 존재 확인

 

case 1)   ->    while , if , if 안거칠 때 텍스트의 인덱스만 +1

 

 

 

Example

 

T = "A B C B A B A B A B A B C B"
P = "A B A B A B C B"
π = "0 0 1 2 3 4 0 0"

과정

T => A B C B A B A B A B A B C B
     A B A (X) π(2) = 0
         A (X) 
           A (X)
             A B A B A B C (X) π(6) = 4
         	     A B A B A B C B (O)

 

 

(X) 는 매칭 실패 한 것 들

(O)는 매칭에 성공한 것

 

A (X) 들은 Case 1에 해당한다.

π(2) 와 π(6)은 Case 2에 해당한다.

 

 

시간 복잡도

 

Θ(n)