자료구조: String Matching(2)

지난번에 이어서 패턴 문제를 KMP 알고리즘에서 어떻게 처리하는지에 대해 알아보겠다.

KMP 알고리즘은 DFA와 비슷하면서도 조금 더 메모리를 적게 먹는 알고리즘이다. 

전반적인 과정은 비슷하지만 텍스트와 패턴을 비교했을때 다른 글자가 나올경우 다른 방법으로 처리하게 된다.

kmp 알고리즘

위에가 text 밑에를 pattern이라고 하자. 그리고 위의 숫자가 써있는 표가 있다. 이것의 용도를 차차 설명하겠다.

일단 상황을 하나 가정하자 텍스트에 값들이 써져있다고 생각한다. 아래의 사진을 보자

 

 

일단 맨위의 숫자는 생각하지 말고 글자 위에 다음과 같은 숫자들이 있고 빨간색은 패턴과 텍스트가 서로 지금까지 일치함을 뜻한다. 그리고 이제 다음으로 볼글자가 다음과 같이 c로 같다고 생각해보자. c 위에는 어떤 숫자를 써야할까?

DFA와 같다. 서로 일치하므로 9 다음 숫자인 10을 적어주고 그다음 글자로 넘어 갈 것이다.

 

그렇다면 서로 다른경우면 어떻게 될까? 예를들어 다음과 같이 생각해보자.

 

이렇게 되면 DFA같은 경우는 어떻게 했는가? 만들어진 Table을 보고 적을 숫자를 결정한다. 만약 t가 패턴의 빨간 부분어딘가에 존재한다면 숫자를 적고 그곳에서 부터 다시 비교작업이 들어가기 시작한다.

 

그러나 KMP알고리즘은 DFA보다 메모리를 적게 쓰기 위해 DFA처럼 따로따로 적을 방법이 없다. 그렇다면 어떻게 문제를 해결해야 할까 ? 그 때 등장하는 것이 아까 맨 위의 수수께끼의 숫자들이다.

 

위의 숫자는 패턴이 가지고 있는 성질을 이용한 숫자들이다. 먼저 9라고 써있는게 무슨뜻인지 다시 한번 생각해보자.

지금 까지 그 전에 본 9번째 글자까지 패턴과 텍스트가 일치했다는 의미이다. 그러면 저 위에 숫자는 무엇을 적어놓은 것인가? 9번째가 일치하기전에 패턴과 일부분 일치한 부분이 있을것이다. 그 전 포스트나 위의 그림을 봐도 숫자는 8789 이런식으로 나올수 있다. 그 일치한 부분들을 적어 놓은 것이 01369라 써있는 숫자의 의미이다. 실제 kmp에서는 일부만 만들지만 설명을 위해 일단 이렇게 적어놓는다.

 

따라서 맨 위의 숫자들은 각각 아래 그림과 같은 뜻이 된다.

 

그렇다면 9다음 글자가 틀렸을 때 kmp 알고리즘 은 어떻게 하겠는가? 9다음 6이라고 써 있으니 6을 가지고 와서 그다음값이 7인지 확인을 하는 과정을 가질 것이다. 3보다 6이 더 많이 맞아있기 때문에 9다음 제일 긴 6을 가지고 시도를한다.

그렇게 계속 다를경우 그다음 케이스로 넘어 간다.  이런식으로 패턴을 하나하나 순서대로 맞춰나아가는 것이 kmp의 흐름이다. 결국 맨위의 숫자는 패턴의 특징을 적어놓은 것이라고 할 수 있다. 그럼 이것을 어떤식으로 적어놔야 할까? 9일때 6310을 다 써 놓아야 할까?  다행히도 6만 써놓으면된다. 9에는 6이 써있고, 6에 3이 가지고 있기 때문이다.

그래서 우리는 이를 바탕으로 Failure Function을 정의할 수 있다.

Failure Function

• Pattern의 P의 앞부분 k글자까지 매치되었을 때 다음 번 시도할 Pattern 앞 부분의 길이

 

Failure Function의 한 예시

그러면 이제 코드로 KMP 알고리즘의 흐름을 살펴 보자.

KMP Code

 
int f [8] = {-1, 0, 1, 1, 2, 2, 3, 4, 5, 6, 8, 4, 1};
 
int KMPmatch(char T[], int n, int output[])
{
    int i, s;
    i = 0; s = 0;
    output[i] = s;
    while(i<=n) {
        if(s == 0){
            if(T[i] != P[s+1]) {output[i] = 0; i++; s=0;}
       else { output[i]=1; i++; s=1; }
 else{
            if(T[i] == P[s+1]) {output[i] = s+1; i++; s++;}
             else{ s = f[s]; }
         }
}
}
}

이 코드에는 빼먹은 과정이 있다. s를 증가시키면 안되는 경우가 있다. 답을 찾게 되고나서 또 다시 돌아야 하는 경우

다시 밀어 두어야 하는 과정이 빠진 코드이다.

 

 

이제 KMP의 시간 복잡도와 공간 복잡도를 알아보자. DFA와 다르게 매번 루프를 돌때마다 i 가 더해지지 않기 때문에 (같은 값을 계속해서 보는 과정이 있기 때문에) 시간 복잡도를 계산하기 조금 이상해(?)진다.

 

일단 케이스가 3가지가 있다.  10: if(T[i] != P[s+1]) {output[i] = 0; i++; s=0;} 인경우는 실패한 경우이다.

11: else { output[i]=1; i++; s=1; }, 13: if(T[i] == P[s+1]) {output[i] = s+1; i++; s++;} 인 경우는 성공한 경우이다.

14: else{ s = f[s]; } 인 경우 성공도 실패도 아닌 경우 이렇게 3가지이다.

각각 X, O, R 이라고 하자. 

 

이렇게 한번 쫙 도는게 아니라 어떨때는 다시 멈춰서 보고 하는 경우가 종종 있다.

이럴 때는 우리는 Amortized Analysis 라고 부른다.

 

Amortized Analysis

• 루프 마다 실행 시간이 다름
• 계산 1 : (루프횟수) X (가장 오래 걸리는 경우의 시간)
• 계산 2 : 각 루프의 실행 시간을 모두 따져서 더한다.(계산 1로 계산하기 어려울 때)

 

 이 경우 우리는 계산2를 쓸 수 밖에 없다. 계산1을 활용하면 결국 O(n^2)이 되기 때문이다.

 그러면 우리는 어떻게 계산2를 활용해서 시간복잡도를 계산해야할까?

다음과 같이 예시를 생각해보자. 여기서 보면 O의 개수와 X의 개수를 더하면 N의 개수가 되는 것을 알수 있다.

그렇담 유일하게 궁금한것은 R의 개수이다. R이 일어 날때 무슨일이 일어 나는지 생각해보자. R를 할때마다 반드시 패턴이 옆으로 움직이게 된다.(겹치는 개수가 바꾸기 때문에) 그러면 이걸로 R의 개수를 어떻게 제한할 수 있나? 패턴이 옆으로 가는 것은 한계가 있다. 앞서 우리가 본것처럼 R은 절대 패턴의 길이보다 많아 질수는 없다. 패턴이 옆으로 끝까지 밀리면 끝이나기 때문이다. 따라서 R은 개수는 N보다 작거나 같다. 따라서 O,X,R은 O(n) 이다.

 

이제 Failure Function을 만드는 시간을 알아보자. 놀랍게도 이과정은 텍스트에서 매칭하는 과정하고 같게 된다. 따라서 

Failure Function을 만드는 시간은 O(m) 이 된다. 결과적으로 정리하면 다음 표와 같다.

 

 

이렇게 우리는 String match 문제를 해결하는 3가지 알고리즘을 알아 보았다. 다음에는 다른 자료구조를 다루는 시간을 가지겠다.