티스토리 뷰



 Knuth-Morris-Pratt 알고리즘, 곧 KMP 알고리즘입니다.
 지금까지 알려진 중 가장 최저의 시간복잡도가 필요한, 즉 가장 최신의 알고리즘입니다.


 일단, 짚고 넘어가자면 KMP 알고리즘의 평균 수행 속도는 O(N + K)(N과 K는 비교할 문자열의 길이)입니다. 매칭을 하려면 최소한 원문 문자열과 검색 문자열을 한번씩은 읽어봐야 할 테니, 가장 최적의 복잡도인 것입니다(사실 소스로 구현하기에 따라 약간씩 커질수도 있습니다).

 이름에서 알 수 있듯이 Knuth, Morris, Pratt 세 사람이 완성한 알고리즘입니다. 기존의 문차열 매칭 방식인 '오토마타' 의 문제점을 극복하기 위해 만들어졌고, 그 결과 뛰어난 시/공간 복잡도를 가진 알고리즘이 완성된 것이지요.

 그럼 알고리즘을 살펴보죠.
 KMP 알고리즘의 가장 중요한 요소는 '실패 함수'(Fail Function) 작성입니다. 검색한 문자열에 대한 실패 함수를 작성하여 검색중 불일치가 발견되었을 때 앞의 일치한 요소들에 대한 재참조를 최대한으로 줄이는 것이지요.
 실패 함수 F는 검색할 문자열 P를 중심으로 작성됩니다. Fi는 "P0 ~ Pi의 문자열에서 접미사와 일치하는 최장접두사의 끝 위치, 단 최장접두사 != 전체문자열"로 정의됩니다(주의: 알고리즘에 대한 문헌에 따라 "최장접미사의 시작 위치", "최장접두사의 길이" 등 다르게 정의되기도 하나 본 강좌에서는 소스 작성과 이해의 편의상 "최장접두사의 끝 위치" 로 정의하겠습니다).

 자, 이제 이 실패 함수가 어떻게 적용되는지 알아보죠. 일단, 문자열을 비교할 때 앞의 문자열들이 일치하다가 불일치하는 곳이 발견되었다고 합시다. 그렇다면 그보다 앞쪽에 있는 문자열은 모두 같다는 의미이지요? 그런데 앞부분을 다시 참조하는 것은 시간상의 낭비가 됩니다. 따라서, 검색 문자열의 비교 위치 j를 P[j - 1] + 1로 바꾸어 다시 비교해야 합니다.

 아래 예를 봅시다.
 "ababa" 라는 문자열이 있습니다. 이 문자열을 다른 긴 문자열 "ababcbababa"에서 검색하는 거죠. 비교를 해 보면

ababcbababa
ababa <- 틀린 위치

와 같이 5번째의 a가 틀리게 됩니다.

 문자열 "ababa"의 실패 함수 Pi는 "P0 ~ Pi의 문자열에서 접미사와 일치하는 최장접두사의 끝 위치, 단 최장접두사 != 전체문자열" 이므로
 a  b  a  b  a
-1 -1  0  1  2
와 같습니다. 그런데 틀린 위치의 바로 앞인 4번째의'b'를 보십시오. 이 자리에서의 실패 함수는 1입니다. 즉, 0 ~ 1의 문자열과 2 ~ 3의 문자열이 동일하다는 뜻이지요. 그런데도 검색할 문자열을 '한칸' 앞으로 당겨 본다면 시간낭비 아닐까요?

 원 문자열인 ababcbababa 중 ababcbababa 부분과 검색 문자열의 ababa은 일치합니다. 그렇기 때문에 여기까지 올 수 있겠지요. 그런데, 찾을 문자열을 한 칸 당기는 것은 이미 알고 있는 사실을 다시 한번 확인하는 작업으로, 불필요한 것입니다. 그럼 어디부터 찾아야 할까요? 4번째 'b'의 실패 함수가 뜻하는 바는 "K[0] ~ K[P[4]]" 의 문자열과 K[4 - P[4]] ~ K[4]"의 문자열이 같다는 것입니다. 즉, 4번째인 'a'를 가리키고 있던 포인터를 3번째의 'a'로 바꾼다고 해도 앞의 2글자는 일치한다는 것입니다. 그리고, '최장접두사'를 찾아 실패 함수를 작성하였기 때문에 이는 최적의 값을 가집니다.

 이것이 KMP 알고리즘의 전부입니다. 여러번 읽어보시는 것이 이해를 위해 좋을 것 같습니다. 아래는 소스입니다.

  1. //str은 비교 대상인 문자열, ptr은 비교할 패턴 문자열  
  2. //n은 str의 길이, m은 ptr의 길이  
  3. int fail[1000] = {0, };  
  4.   
  5. void fail(){  
  6.     int i, j;  
  7.     fail[0] = -1;  
  8.     for(i = 1; i < n; i++){  
  9.         j = fail[i - 1] + 1;  
  10.         while(ptr[i] != ptr[j] && j > 0){  
  11.             j = fail[j - 1] + 1;  
  12.         }  
  13.         if(ptr[i] == ptr[j]){  
  14.             fail[i] = j;  
  15.         }  
  16.         else{  
  17.             fail[i] = -1;  
  18.         }  
  19.     }  
  20. }  
  21.   
  22. int comp(){  
  23.     int i, j;  
  24.     for(i = j = 0; i < n; i++, j++){  
  25.         if(j == m){  
  26.             return i - j;  
  27.         }  
  28.         while(str[i] != ptr[j] && j > 0){  
  29.             j = fail[j - 1] + 1;  
  30.         }  
  31.         if(str[i] != ptr[j]){  
  32.             j = -1;  
  33.         }  
  34.     }  
  35.     return -1;  
  36. }  

 보시다시피 실패함수 작성부분과 비교부분이 거의 유사합니다^^

그외 kmp알고리즘 관련 링크들;

'Computer Science' 카테고리의 다른 글

PL Ch 4. Variable  (0) 2011.05.16
PL Ch 3. 정리  (0) 2011.05.16
운영체제 동기화 부분(2)  (0) 2011.04.01
운영체제 동기화 부분(1)  (2) 2011.03.31
[자료구조] AVL 트리  (0) 2011.03.30
댓글