[자료구조] KMP(Knuth-Morris-Pratt) Algorithm

 

KMP 알고리즘은 문자열 내에서 특정 패턴을 엄청나게 빠르게 찾아주는 알고리즘입니다.

해당 패턴의 위치를 빠르게 알 수 있지요.

 

KMP알고리즘은 이전 포스팅의 마지막에 다루었던 패턴을 찾는 방법처럼 스트링과 패턴의 불일치가 발생했을 때 최대한 중복된 연산을 피하면서 문자열과 비교할 수 있도록 합니다.

이렇게 하기 위해서는 먼저 얼마나 중복연산을 피할것인지 판단하기 위한 값들이 필요합니다.

이를 failture function이라고 한다.

---

<failure function>

failure function은 패턴문자열의 접두사와 접미사의 일치하는 부분을 계산하고 이를 fail 배열에 저장합니다. 

fail 배열의 첫 번째 인덱스의 값은 -1로 설정합니다. 인덱스의 의미는 현재 패턴의 문자가 패턴의 첫문자부터 #번째 문자까지 일치한다는 것을 말합니다.

fail 배열의 두번째, 세번쨰, 네번쨰 인덱스의 값도 -1인것을 볼 수 있는데 이는 아직까지 접두사와 접미사가 일치하는 것을 찾지 못했다는 것을 의미합니다.

다섯번째 문자 A는 접미사로 현재 접두사 A와 드디어 일치하게 되었습니다. 따라서 다섯번째 인덱스는 첫번쨰 인덱스의 문자와 같게 되었으므로 fail 배열의 다섯번째 인덱스에는 0이 들어가게됩니다.

또한 다음에 나오는 문자B를 포함한 접미사 AB는 접두사 AB와 일치하는 것을 볼 수 있습니다. 따라서 1이 들어가게 됩니다.

그 다음에 나온 문자 D는 접미사로 접두사와 일치하는 부분이 없기 때문에 다시 -1을 가지게 됩니다.

 

이를 코드로 나타내 보겠습니다.

void failure(char *pat) {
  int i, j, n = strlen(pat);
  fail[0] = -1;
  for(j=1; j<n; j++) {
    i = fail[j-1];
    while((pat[j] != pat[i+1]) && (i >= 0)) i = fail[i];
    if(pat[j] == pat[i+1]) fail[j] = i+1;
    else fail[j] = -1;
  }
}

하나하나 분석해보겠습니다.

 

fail[0] = -1;

앞서 언급했던 fail배열의 첫번째 값은 -1로 설정한다고 했기 때문에 위와 같이 작성했습니다.

 

for(j=1; j<n; j++) {
    i = fail[j-1];
    while((pat[j] != pat[i+1]) && (i >= 0)) i = fail[i];
    if(pat[j] == pat[i+1]) fail[j] = i+1;
    else fail[j] = -1;
  }

0번 인덱스의 값은 -1로 설정해주었기 때문에 그 다음을 의미하는 1부터 반복문을 시행합니다.

i에는 fail[i-1]의 값으로 나의 이전 문자에 대한 정보를 담고 있습니다.

나의 이전 문자의 fail값이 0보다 크다면 접두사와 이전문자까지의 접미사가 일치하는 것이 있었다는 것과 어디까지 일치했는지 알 수 있겠죠.

 

while((pat[j] != pat[i+1]) && (i >= 0)) i = fail[i];

다소 의미를 생각하기 어려울 수 있습니다.

i >=0 이라는 조건은 위에서 설명한 바와 같습니다.

그리고 pat[j] != pat[i+1] 라는 부분은 현재 j에서 접두사와 접미사의 일치가 깨졌음을 의미합니다.

따라서 i는 fail[i]의 값으로 바뀌게 됩니다. 이 문장의 의미는 접두사에서의 i번째 문자를 접미사로 보았을 때 접두사와 얼만큼 일치했는지를 의미합니다.

만약 이때에도 i가 0보다 큰 값을 가지고 있었다면 다시 한번 pat[j] != pat[i+1]를 통해 접두사와 접미사가 일치하는지 확인다고 이전 과정을 반복합니다.

 

예를 들어서 fail배열이

str     A      B     C     D      A      B      C      D      A      B      E

pat   -1     -1    -1     -1      0      1      2       3       4      5 

라고 가정합시다. 현재 j는 문자 E의 인덱스에 있다고 하겠습니다.

그렇다면 현재 pat[j] != pat[i+1]에서 접두사(ABCDABC)와 접미사(ABCDABE)의 일치가 깨졌으며 i >= 0였기 때문에 while문이 실행됩니다. 따라서 i = fail[i]가됩니다. i는 5였기 때문에 새로운 i는 fail의 5번 인덱스의 값인 1을 가지게 됩니다.

그리고 다시 while문은 실행되는 상황이 됩니다. 따라서 i는 다시 fail[i]가 되어 i는 -1을 가지게 됩니다.

하지만 아주아주 만~~약에 pat[j] == pat[i+1]다고 그냥 한번 얘기만 해보겠습니다. 그렇다면 E에 위치하는 fail배열의 값은 아래 코드에 의하여 1 증가하게 됩니다.

if(pat[j] == pat[i+1]) fail[j] = i+1;

결론을 얘기하면 접두사와 접미사의 불일치로 인하여 접두사 속에서의 일치가 있는지 확인하려고 i를 감소시킨 작업이 

i = fail[i]라고 생각할 수 있습니다. 위에서 아주아주 만~~약에라고 가정한 상황이라면 감소한 i의 다음문자와 현재의 j 문자가 일치하기 때문에 접두사와 접미사가 일치했다고 할 수 있는 것입니다. 따라서 fail[j]의 i가 1증가하는 것입니다.

 

하지만!!!

현재 상황은 그렇지 않습니다 while문이 다시 실행되었고 i = -1이 되었으므로while문의 조건에 위배되어 while문을 빠져 나옵니다. 또한 while문 바로 밑에 있는 if문에도 조건이 맞지 않기에(pat[j] != pat[i+1]) 더 밑에 있는 else 문이 실행됩니다.

i가 -1이라는 것은 접두사와 접미사의 일치가 없는 것이므로 -1을 fail[j]에 대입하는 과정이 됩니다.

---

<matchign function>

자, 이제 failure 함수를 완성했기 때문에 드디어 패턴을 매칭하는 함수를 살펴보겠습니다.

저는 이 함수를 pmatch라고 하겠습니다.

 

int pmatch(char *string, char *pat) {
  int i=0, j=0;
  int lens = strlen(string);
  int lenp = strlen(pat);
  while(i < lens && j < lenp) {
    if(string[i] == pat[j]) { i++; j++; }
    else if(j == 0) i++;
    else j = fail[j-1] + 1;
  }
  return ((j==lenp) ? (i-lenp) : -1);
}

 

 

failure 함수보다는 이해하기 쉬울 겁니다.

 

i는 스트링에 접근하기 위한 인덱스, j는 pat에 접근하기 위한 인덱스입니다.

while 문을 통해서 i와 j 모두가 string과 pat의 문자열의 길이보다 작을 때 시행되도록 조건을 설정하였습니다.

만약 string[i]와 pat[j]가 일치하면 다음 문자를 비교해보기 위해 i와 j모두 증가시킵니다. 만약 그렇지 않고 j 가 0이라면 

string의 인덱스를 가리키는 i만 증가시켜서 패턴의 인덱스를 가리키는 j는 0으로 가만히 두고 string의 다음문자와의 비교를 위해 i만 증가시킵니다.

여기서 또 string[i]와 pat[j]가 일치하지도, j가 0도 아니라면, 일치하다가 중간에 불일치가 생긴 상황입니다.

여기서는 앞서 정의했던 fail배열을 이용합니다.

fail배열을 저는 패턴 안에서 접두사와 접미사가 일치하는 부분들을 계산하여 만들어주었습니다.

string과 pat의 불일치가 생긴다면 이전 문자의 fail값은 패턴 내에서 접두사와 접미사가 얼만큼 일치했는지를 알려주고 있을 것입니다.

만약 그 값이 1이라면 총 2개의 문자가 패턴 안에서 접두사와 접미사와 같았다는 것을 의미하겠죠. 따라서 2개의 문자는 비교하지 않아도 된다는 것입니다. 이미 일치하는 것을 알고 있기 때문입니다.

 

이해를 돕기 위해서 상황극을 하나 생각해봤습니다.

Martin: 엇?! F를 하셔야 저희가 도와드리는데 D를 하셨네요...?

Amy: 에에엥??? 그러면 저는 처음부터 다시 해야되나요??!?

Martin: 잠시만요 이전에 해놓으셨던것들을 한번 볼게요~ (fail 배열을 뒤적뒤적)

Martin: 오!? 그나마 다행이에요~~ A,B까지는 해놓으셨네요!!! C부터 다시하는걸로 해드리겠습니다!!

Amy: 우왕~~ 개꿀이당~~ 감사합니다~~~

(사실 근데 위 그림 상에서는 amy는 또 틀림 ㅋㅋㅋㅋ)

 

위와 같은 상황을 계속 반복하다가 패턴을 찾거나 스트링이 동 나면 반복문을 빠져나올 것입니다.

빠져나오고 바로 조건문을 통해서 비교를 합니다. 만약 패턴을 찾았다면 j는 반복문 내에서 계속 증가하여 패턴의 길이와 같아졌을 것입니다. 그렇다면 스트링에서의 패턴의 시작 위치를 반환하기 위하여 i-lenp를 통해 패턴의 시작 위치를 반환해 줍니다. 

만약 패턴을 찾지 못하였다면 j는 패턴의 길이에 못미칠 것입니다. 그때는 찾지 못했다는 의미로 -1을 반환하여 줍니다.