Knuth-Morris-Pratt Algorithm

1. Introduction

  Ctrl + F 를 통해 인터넷에서 특정 문자열을 검색할 수 있다. 이런 종류의 검색에 이용되는 문자열 매칭 알고리즘 중 가장 유명한 것이 Knuth-Morris-Pratt(KMP) algorithm이다.

 

1.1. Navie Method

  KMP algorithm에 대한 설명을 하기 전 Naive한 문자열 매칭에 관한 이야기를 하겠다. 검색어, 즉 찾고자 하는 문자열을 \(P\)라 하자. 보통 이 \(P\)를 패턴이라고 한다. 우리는 \(P\)를 text \(T\)에서 몇 번 등장하는지, 어디서 등장하는지 알아야 한다. Naive하게 \(P\)를 \(T\)에서 찾으려면 아래의 과정을 수행하게 될 것이다.

Naive-String-Matcher(\(T\),\(P\)) 1    \(n = T.length\) 2    \(m = P.length\) 3    \(\mathbf{for}\ s=0\ \mathbf{to}\ n-m\) 4        \(\mathbf{if}\ P[1..m]==T[s+1..s+m]\) 5            print "Pattern occurs shift" \(s\)

위 pseudocode는 Introduction to Algorithm 3rd Ed의 988p를 그대로 가져온 것이다. 위 pseudocode를 보자. 4번 줄을 수행하는데 점근적으로 \(\Theta(m)\) 만큼의 연산이 필요하다. 이를 \(n-m+1\) 만큼 반복해야 한다. 즉, 전체 time complexity는 점근적으로 \(\Theta((n-m+1)m)\)이다. 이 naive method의 좋은 점은 전처리가 필요 없다는 것이며, 대부분의 naive method와 같게, small case에서는 다른 algorithm보다 빠르게 작동하지만, 충분히 큰 case에서 비효율적이다.

 

2. KMP Algorithm

2.1. The Prefix Function For a Pattern

  이 챕터에서는 흔히 failure function이라고 불리는 array에 대해서 이야기할 것이다. KMP에서 \(O(m)\) 만큼의 연산이 필요한 전처리를 수행해주어야 하는 부분이다. Failure function이라는 이름의 근원이 무엇인지는 모르겠으나, 가장 널리 이용되는 알고리즘 교재 Introduction to Algorithm(CLRS)에서는 'prefix function for pattern'이라는 이름으로 등장하며, 이때 CLRS에서 이요된 기호 \(\pi\)가 이 array를 표현하는 기호로써 널리 이용되고 있다. KMP algorithm이 발표된 Knuth, Moriss, Pratt의 논문 Fast Pattern Matching in Strings에는 \(next\)라는 이름으로 등장하며, 딱히 이 array에 이름을 붙이지는 않는다. 본문에서는 이 array를 \(next\)로 정의하겟다. \(\mathbf{Let}\) \(next[j]\) 는 패턴에서 mismatch되는 character의 다음 position. 즉 \(P[1..next[j]]==P[j-next[j]..j]\)이다. 이를 다르게 표현하면 substring \(P[1..j]\)에서 prefix와 suffix가 같을 수 있는 최대 prefix와 suffix의 length이다. 위 표현들을 모두 알고 있는 것이 좋지만, 처음 읽을 때 마지막 표현만 본다면, 이해가 힘들 수 있다.

 

  Prefix function은 아래 의사코드의 과정을 통해 계산할 수 있다. [CLRS 3rd Ed p1006]

Compute-Prefix-Function(\(P\)) 1    \(m=P.length\) 2    \(\mathbf{let}\) \(next[1..m]\) be a new array 3    \(next[1]=0\) 4    \(k=0\) 5    \(\mathbf{for}\) \(q=2\) \(\mathbf{to}\) \(m\) 6        \(\mathbf{while}\) \(k>0\) and \(P[k+1] \neq P[q]\) 7            \(k=next[k]\) 8        \(\mathbf{if}\) \(P[k+1] == P[k]\) 9            \(k=k+1\) 10       \(next[q]=k\) 11   return \(next\)

 

2.2. Algorithm

  \(next\)를 이용해서 문자열 매칭을 할 방법을 생각해보자. 이 방법을 떠올리기 위해서는 먼저 naive한 방법을 잘 생각해봐야 한다. 1.1.의 pseudocode에서 5번 줄을 보라. Naive method가 느려지는 가장 중요한 요인이다. 이 부분을 없애도록 노력해봐야한다. 즉, \(T\)에서 \(P\)를 찾을 때, 지금 \(T[i]\)와 \(P[j]\)가 같은지 확인해야 한다면, \(T[i-j+1..i-1]==P[1..j-1]\)인 상태를 만들어 주어야 한다. 그렇다면, \(T[i] \neq P[j]\)인 경우에 \(j\)를 적절한 값으로 바꿔주어야 한다. 이때 앞서 설명한 \(next\)를 이용할 수 있다. \(next\)를 구하기 위해 이용한 pseudocode를 보라. 이 psedocode에서는 \(P[k+1] \neq P[q]\) 일 동안 \(k=next[k]\)를 이용해서 \(k\)값을 바꾸어 준다. 이 방법을 그대로 문자열 매칭에도 이용할 수 있고, \(j=next[j]\)로 바꾸어 주면 된다. 이 방법을 이용한 것이 KMP algorithm이다.