2024-04-03-09. KMP String Matching Algorithm

KMP(Knuth-Morris-Pratt) 알고리즘

KMP 알고리즘은 전이 함수 대신 실패 함수(failure function) f를 사용한다.

f는 집합 {1, 2, ..., m}에서 집합 {0, 1, ..., m-1} 로 대응되는 함수로, 코드에서 길이가 m인 배열로 표현 가능하다.

f[q]는 δ(q, a) 를 계산하는 데 필요한 정보를 담고 있다. 여기서 a는 ∑내의 임의의 문자열이다. 즉, 실패 함수의 값은 전이 함수와 달리 문자 a와 관계없이 정해진다.

DFA 알고리즘은 오토마타의 전이 함수를 만드는 데 O(m|∑|) 시간이 걸린 반면, KMP에서 실패 함수를 만드는 데는 O(m) 시간이 걸린다.

실패 함수의 의미

패턴이 길이가 10인 문자열이라고 하자. (텍스트와 패턴의 구체적인 내용은 생각하지 않는다)

텍스트를 i개 읽어 σ(T_i) = 8 임을 구한 상황에서, i+1번째 텍스트를 읽어 σ(T_i+1)을 구하려 한다.

만약 T[i+1] = P[9]라면, 오토마타를 증명할 때 사용한 보조 정리 1에 따라 σ(T_i+1) <= 8+1 이므로, σ(T_i+1) = 9 이다.

T[i+1] != P[9] 일 때, σ(T_i+1)를 효율적으로 구하기 위해, T_i의 접미부에 매칭될 수 있는 P의 모든 접두부에 대해 고려해야 한다.

σ(T_i) = 8 는 T_i의 접미부에 매칭될 수 있는 P의 접두부의 최대 길이가 8이라는 것을 의미한다.

여기서 P의 접두부가 최대 길이가 아닌 경우, 즉 T_i의 접미부에 매칭될 수 있는 P의 모든 접두부에 대해 생각해 보자.

예를 들어, P₆ , P₃ , P₁ , P₀ 가 T_i의 접미부와 매칭된다고 하자.

이때, σ(T_i+1) 가 될 수 있는 값은 (9는 아니라고 가정하면) 6+1, 3+1, 1+1, 0+1, 0뿐이다.

만약 σ(T_i+1) 의 값이 k+1이라면, T_i+1의 접미부가 P_k+1이고, P_k는 T_i의 접미부가 되기 때문이다. (단, 0<=k)

T_i의 접미부가 되는 P의 접두부의 길이가 8외에 6, 3, 1, 0 뿐이라는 것을 안다면, σ(T_i+1)의 값은

if T[i+1] == P[6+1], 6+1
else if T[i+1] == P[3+1], 3+1
else if T[i+1] == P[1+1], 1+1
else if T[i+1] == P[0+1], 0+1
else, 0

이다.

그런데 여기서 P_k가 T_i의 접미부일 필요충분조건은, P_k가 P₈의 접미부인 것이다.

증명 :

증명 과정에서, 배열 A의 뒤에서 n번째 원소를 A[-n]으로 표기한다.
P_k 가 T_i의 접미부이면

1이상 k이하의 정수 j에 대해
P₈이 T_i의 접미부이므로, T_i[-j] = P₈[-j] 이다.
P_k가 T_i의 접미부이므로, T_i[-j] = P_k[-j] 이다.
두 식을 연립하면 P₈[-j] = P_k[-j] 가 성립하므로, P_k는 P₈의 접미부이다.

P_k가 P₈의 접미부이면

1이상 k이하의 정수 j에 대해
P₈[-j] = P_k[-j]
P₈[-j] = T_i[-j]
두 식을 연립하면 T_i[-j] = P_k[-j] 가 성립하므로, P_k는 T_i의 접미부이다.

따라서 σ(T_i) = 8 일 때, T_i 의 접미부가 되는 P의 접두부의 길이는 P₈로부터 구해진다. 즉, T의 내용과는 무관하게 구해진다.

실패 함수 f의 정의

실패 함수 f[q]는 다음과 같이 정의된다.

f[q]

= σ(T_i)=q일 때, T_i의 접미부가 되는 P의 두번째로 긴 접두부의 길이
= P_q의 접미부가 되는 P의 두번째로 긴 접두부의 길이

f[q] = x, 즉 P_q의 접미부가 되는 P의 두번째로 긴 접두부의 길이가 x라 하자.

그리고 세번째로 긴 접두부의 길이는 y라 하자.

그러면, f[x] = y, 즉 P_x의 접미부가 되는 P의 두번째로 긴 접두부의 길이는 y이다.

증명

P_x의 두번째로 긴 접두부가 P_z 이고, y<z<x 라 가정한다.
그러면 P_z는 P_q의 접미부이고, 길이가 P_y보다 길다..
이는 P_y가 P_q의 접미부가 되는 P의 세번째로 긴 접두부라는 전제와 모순이다.
따라서 P_x의 두번째로 긴 접두부는 P_y여야만 한다.

위 증명은 P_q의 두번째, 세번째를 n번째, n+1번째로 치환하여 일반화할 수 있다.

이러한 실패 함수의 특성으로 인해, f의 원소 각각에는 P의 두번째로 긴 접두부의 길이만 저장되어 있음에도 불구하고, 세번째, 네번째로 긴 접두부의 길이도 f를 통해 쉽게 구할 수 있다.

예를 들어, P₈의 접미부에 매칭되는 P의 접두부의 길이가 8, 6, 3, 1, 0 인 앞의 예시에서, 실패 함수는 다음과 같이 구성된다.

P₈의 접미부가 되는 P의 두번째로 긴 접두부의 길이는 f[8]=6이고,

세번째로 긴 접두부의 길이는 f[6]=3이며,

네번째로 긴 접두부의 길이는 f[3]=1이고,

다섯번째로 긴 접두부의 길이는 f[1]=0이다.

KMP 알고리즘 구현

먼저 실패 함수 f가 주어졌다고 가정하고, 이를 이용해 string matching을 하는 알고리즘을 구현해 보자. f를 구하는 알고리즘은 뒤에 살펴볼 것이다.

int f[15] = {...};

int[] KMPMatch(char[] T, int n, char[] P, int m, int output[]) {
    int q = 0;         // q는 P에서 매칭할 접두부의 개수이다.
    for(int i=0; i<n; i++) {  // 텍스트의 i번째 문자까지 읽음
        while(0 < q && T[i+1] != P[q+1])
            q = f[q];  // i+1번째 문자와 매칭될 때까지 실패 함수로 q 갱신
        if(T[i+1] == P[q+1])
            q++;       // i+1번째 문자와 매칭에 성공하면 q를 1 증가
        output[i+1] = q;
        /* 매칭에 끝까지 실패하였다면, 즉 q=0이고 T[i+1] != P[q+1] 이면, output[i+1]에 0가 저장된다. */
    }
    return output;
}

Failure Function의 계산

위에서 σ(T_i) = 8이고, T_i의 접미부에 매칭될 수 있는 P의 접두부의 길이가 8, 6, 3, 1, 0일 때, σ(T_i+1) 의 값은 9, 7, 4, 2, 1, 0 중 하나임을 증명하였다.

마찬가지 방법으로, f[8] = 6이고, P₈의 접미부에 매칭될 수 있는 P의 접두부의 길이가 (가장 긴 8을 제외하고) 6, 3, 1, 0일 때, f[9]의 값은 7, 4, 2, 1, 0 중 하나임이 증명된다.

위에서 f[8] = 6, f[6] =3, f[3] = 1, f[1] = 0 이 됨을 상기하자.

따라서 f[1..8] 가 구해져 있다면, f[9]은

if P[9] = P[f[8]+1] = P[6+1], 7
else if P[9] = P[f[6]+1] = P[3+1], 4
else if P[9] = P[f[3]+1] = P[1+1], 2
else if P[9] = P[f[1]+1] = P[0+1], 1
else, 0

이다.

이를 일반화하면, P_q+1의 두번째로 긴 P의 접두부 길이는 P_q의 두번째, 세번째, 네번째, ... 로 긴 접두부 길이 + 1 중 하나 또는 0임을 알 수 있다. 즉 f[q+1]은 f[q]+1, f[f[q]] + 1, f[f[f[q]]] + 1, ..., 0 중 하나이다.

위와 같은 사실을 바탕으로 f를 구하는 알고리즘을 다음과 같이 설계할 수 있다.

int[] compute_failure_function(char[] P, int m) {
    int[] f[1..m];  // 길이 m인 int 배열 선언
    f[1] = 0;
    int k = 0;
    for(int q = 1; q<m; q++) {  // 패턴의 q번째 문자까지 읽음
        while(0 < k && P[q+1] != P[k+1])
            k = f[k];  // q+1번째 문자와 매칭될 때까지 실패 함수로 k 갱신
        if(P[k+1] == P[q+1])
            k++;       // q+1번째 문자와 매칭에 성공하면 k를 1 증가
        f[q+1] = k;
    }
    return f;
}

실패 함수를 구하는 알고리즘은 실패 함수로 string matching을 구하는 알고리즘과 거의 같다.

두 알고리즘은 다음과 같은 차이점이 있다.

KMPMatch는 T와 P를 매칭시키는 반면 compute_failure_function는 P와 P를 매칭시킨다.
KMPMatch는 가장 긴 P의 접두부 길이를 구하는 반면 compute_failure_function는 두번째로 긴 P의 접두부 길이를 구한다.

알고리즘의 수행 시간은 다음과 같이 구한다.

각 for 루프에서 k값이 변하는 경우는, k = f[k] 연산이나 k++ 연산이 수행되는 경우 뿐이다.
실패 함수의 정의에 의해, while 문의 k = f[k] 연산은 k를 감소시키고, if문의 k++연산은 k를 1만큼 증가시킨다.
for 루프가 m-1번 반복되므로, k의 증가 연산은 최대 m-1번 발생한다.
k의 초기값이 0이고, k가 음수가 될 순 없으므로, k가 감소하는 연산도 (항상 1씩 감소한다고 가정해도) 최대 m-1번 발생한다.
즉, while 루프는 전체 알고리즘에서 최대 m-1번 반복된다.
while 루프가 총 m-1번 반복되고, for문 안의 나머지 문장도 m-1번 반복되므로, 알고리즘의 수행 시간은 O(m)이다.

KMPMatch의 수행 시간도 같은 방법으로 구할 수 있다. KMPMatch의 수행 시간은 O(n)이다.

← Previous Post Next Post →

목록으로