junis3's profile image

junis3

January 25, 2021 00:00

KMP 알고리즘과 Aho-Corasick 알고리즘

string

본 글에서는 대표적인 문자열 검색 알고리즘인 KMP 알고리즘과 Aho-Corasick 알고리즘에 대해 다루려 한다. 두 알고리즘이 알고리즘계에서 잘 알려진 이유는 둘 모두 평균 시간 복잡도뿐 아니라 최악의 경우 시간 복잡도가 극적으로 개선되었기 때문이다. 두 알고리즘 모두 실제로는 다이나믹 프로그래밍의 한 예시일 뿐임에도 실제로는 어려운 알고리즘으로 생각되고 있었다. (내가 그랬다..)

풀고 싶은 문제

우리가 두 알고리즘을 이용해 풀고 싶은 문제는 아래와 같다.

1) 아주 긴 문자열 $S$ 와 짧은 문자열 $T$ 가 주어진다. $S$ 의 길이는 $N$, $T$ 의 길이는 $M$ 이라 하자. 이 때, $S$ 안에 $T$ 가 나타나는, 즉 $S[i..i+M-1] = T$ 를 만족하는 인덱스 $i$를 모두 찾아라.

2) 그리고 $T$가 여러 개 주어질 때, 즉 찾아야 하는 문자열이 $T_1, \cdots, T_k$ 와 같이 여러 개일 때에도 각 $T_i$ 에 대해서 위 문제를 해결하라.

위와 같은 문제를 String Matching이라고 부른다. 문자열 $T$는 흔히들 ‘Pattern’이라고들 부르며, 따라서 2)와 같은 경우의 문제를 Multi Pattern String Matching 문제라고 부른다.

KMP 알고리즘

KMP 알고리즘은 패턴 문자열이 하나 있을 때 긴 문자열 안에서 패턴 문자열을 찾는데 쓰이는 알고리즘이다. 이를 계산하기 위해서 약간 다른 문제를 생각해 보자.

길이 $N$인 문자열 $S$가 주어질 때, 다음 배열의 값들을 계산하라.

$F[i]$ : $S[0..k] = S[i-k..i]$ 를 만족하는 가장 큰 $k$값, 단, 전체 문자열($k=i$)는 제외.

즉, $S[0..i]$ 의 접두사이면서 접미사가 되는 가장 긴 문자열의 길이 + 1이다.

해당하는 값이 존재하지 않으면 해당 인덱스에는 $-1$ 을 채우기로 하자.

위 문제는 다이나믹 프로그래밍처럼 생겼고, 실제로 다이나믹 프로그래밍에서 배열을 채우듯이 채워 보자. $F[1]$ 에서 $F[i-1]$ 까지의 값들을 모두 구해서 알고 있는 시점에서 $F[i]$ 의 값을 구해보도록 하자.

  • 우리는 $f_1 = F[i-1]$ 을 알고 있다. $S[0..f_1] = S[i-f_1-1..i-1]$ 이므로, 만약 $S[f_1+1] = S[i]$ 를 만족한다면, $F[i] = f_1 + 1$ 이 된다.
  • 이제 $f_2 = F[F[i-1]]$ 을 생각해 보자. $S[0..f_2] = S[f_1 - f_2 .. f_1] = S[i-f_2-1 .. i-1]$ 이므로, 만약 $S[f_2+1] = S[i]$ 를 만족한다면, $F[i] = f_2 + 1$ 이 된다.

이제 $f_j = F[f_{j-1}]$ 과 같이 $f_3, f_4, \cdots$ 도 정의하기로 하자. 그러면, 놀랍게도, $F[i]$ 의 값이 될 수 있는 후보는 $f_j + 1$ 들 뿐이다. KMP 알고리즘을 제대로 기억하고 싶다면, 이 사실만 기억하면 된다.

$f_j + 1$ 들이 답의 후보가 될 수 있다는 것은 당연해보인다. 하지만 이 값들이 아니면 안 되는 것일까?

명제. $f_1 < k < f_2$ 인 $k$ 에 대해서, $S[0..k] = S[i-k-1..i-1]$ 은 성립하지 않는다.

증명. 위 등식이 성립한다고 하자. $S[0..f_1] = S[i-f_1-1..i-1]$ 이므로, $S[0..k] = S[i-k-1..i-1] = S[f_1-k..f_1]$ 이다. 이는, $f_2 = F[f_1]$이 $S[0..k] = S[f_1-k..f_1]$ 을 만족하는 최대의 $k$ 값임에 모순.

즉, 요약하면, $F[i]$ 를 구하기 위해서는 $f_1 = F[i-1]$, $f_j = F[f_{j-1}]$ 과 같이 정의되고, $f_i = -1$ 이 될 때 멈추는 수열 $f$ 를 생각해야 한다. 다시 말해, $F[i], F[F[i]], \cdots$ 와 같은 형태로 파고 들어간다. 이 수열에서, $S[f_j + 1] = S[i]$ 를 만족하는 첫번째 $f_j$ 를 찾으면, $F[i] = f_j + 1$ 이 된다.

$F$ 배열의 값들 $F[0], \cdots, F[M-1]$ 를, 패턴 문자열 $T$ 에 대해 모두 구해두었다면, 원래의 String Matching 문제는 쉽게 풀 수 있다. 다음과 같은 쉬운 알고리즘에서 조금 변형하면 된다.

알고리즘 1: 간단한 알고리즘

  • $i=0, \cdots, N-M$ 까지 차례로 돌면서 $S[i..i+M-1]$ 에서 $T$ 가 나타나는지 검사한다.
    1. $j=0, \cdots, M-1$ 까지 돌면서 $S[i+j]$ 와 $T[j]$ 를 비교한다.
    2. 불일치 ($S[i+j] \neq T[j]$)가 발생하는 순간, 멈추고, $i \leftarrow i+1$, $j \leftarrow 0$ 부터 다시 시작한다.

위 알고리즘의 2번 부분을 아까 계산해둔 $F$ 배열 (여기서는 실패 함수 (Failure Function) 라고 부른다) 을 이용해 더욱 빠르게 할 수 있다. 요지는, 단순히 $i \leftarrow i+1$, $j \leftarrow 0$ 으로 가면 실패할 게 뻔히 보인다는 것이다.

$S[i..i+M-1]$ 에서 $T$가 나타나려면, 적어도 앞부분은 일치해야 된다. 그런데 불일치가 발생하고 다음 $i+1$ 로 넘어가려는 순간, 우리는 다음과 같은 정보들을 알고 있다.

  • $S[i] = T[0], S[i+1] = T[1], \cdots, S[i+j-1] = T[j-1]$. 즉, $S[i..i+j-1] = T[0..j-1]$
  • $S[i+j] \neq T[j]$

만약 $F[j-1] = j-2$ 였다면, $T[0..j-2] = T[1..j-1]$ 이다. 따라서 $S$ 를 $i \leftarrow i+1$ 에서부터 검사를 시작했을 때, $S[i+1..i+j-1] = T[1..j-1] = T[0..j-2]$ 이므로 앞의 $j-2$ 개의 문자열은 일치하게 된다. 즉, 이 경우에는 $i \leftarrow i+1$ 로 둘 때 앞의 $j-2$ 개의 문자열이 일치한다는 사실을 눈으로 보지 않아도 알고 있다. 실제로 매칭이 되는지 검사하는 작업은 그 다음 인덱스부터 검사하면 된다.

이의 역 또한 성립한다. $F[j-1] \neq j-2$ , 즉 $F[j-1] < j-2$ 라면, $S[i+1..i+j-1] = T[1..j-1] \neq T[0..j-2]$ 이다. (같은지 아닌지 모른다는 것이 아니라, 확실히 다르다는 것이다!) 즉, 이 경우에는 $i \leftarrow i+1$ 로 두고 검사할 필요 자체가 없다. 안 봐도 앞의 $j-2$ 개의 문자들 중 하나에서 어긋날텐데, 매칭이 성공할 리 없다.

위 논리를 다음과 같이 확장할 수 있다. $f = F[j-1]$ 이라면, $i \leftarrow i+1$ 에서부터 $i \leftarrow i+j-f-1$ 까지는 볼 것도 없다. 다시 한 번 실패 함수 $F$는 접두사와 접미사가 같은 최대 길이를 나타낸다는 점을 기억하자. 반면, $i \leftarrow i + j - f$ 를 대입하면, 앞의 $f$ 개의 문자들은 검사할 필요도 없으니 $j \leftarrow k$ 로 바로 건너뛸 수 있다.

극단적인 예외 케이스로, $F[j-1] = -1$ 이라면 $i+1, \cdots, i+j-1$ 까지를 모두 건너뛰고 $i \leftarrow i+j$, $j \leftarrow 0$ 에서부터 다시 시작할 수 있다

이와 같은 최적화가 KMP 알고리즘의 전부이다. 실패 함수 $F$를 최적화된 DP 방법으로 계산하고, 그 실패 함수를 이용해서 건너뛰는 최적화를 수행하면 전체 문제를 풀 수 있다. 위 내용을 $i$ 변수 대신 $i+j$를 나타내는 변수를 두고 구현할 수도 있지만, 아무렴 어떤가!

시간 복잡도

실패함수를 구하는 부분을 제외한 KMP 알고리즘의 각 과정에서, $i$ 는 항상 증가하고, $i+j$ 도 항상 증가한다. 그리고 반복문이 한 번 실행될 때마다 두 값들 중 하나는 무조건 증가하기 때문에, 총 시간 복잡도는 $O(N + M)$이다.

실패함수를 구하는 부분 또한 마찬가지이다. 실패함수를 구하는 과정에서 $i-f$는 항상 증가하고, $f$는 항상 감소한다. 그리고 매번, ($i$를 하나 증가시키고 $f$를 하나 증가시킨다) 또는 ($f$ 값을 감소시킨다) 둘 중 하나가 일어나므로, 두 값 중 하나는 변화한다. 따라서 실패함수도 $O(M)$ 의 시간 복잡도에 구할 수 있다.

Aho-Corasick 알고리즘

Aho-Corasick 알고리즘에서는 $T$ 가 여러 개이다. 각 $T_i$ 에 대해 KMP를 수행하면 $\sum_i ( \lvert S \rvert + \lvert T_i \rvert) = K \lvert S \rvert + \sum_i \lvert T_i \rvert$ 만큼의 시간이 들 것이다. Aho-Corasick 알고리즘은, 문자열 집합 전체를 하나의 트리로 나타낸 다음, 그 트리에 대한 트리 DP의 형태로 실패 함수를 하나의 트리에서 모두 계산해버린다.

문자열 집합에 대한 트라이(Trie)를 그린다. 트라이에 대한 설명은 다른 게시글을 참조하라. 다만, 트라이의 루트에서 어떤 정점으로 쭉 내려가는 경로는 하나의 (부분)문자열을 나타낸다는 사실, 그리고 이 경로가 집합에 들어있는 어떤 문자열의 접두사를 나타낸다는 것은 익히 알고 있을 것이다. 이번에도 유사하게 각 정점에 대해 다음 함수를 정의해보자. 이번에는 함숫값이 “인덱스”가 아니라, “정점”이라는 점에 유의하자. 함수는 보통 화살표로 나타내니깐, 정점 $x$에서 정점 $F[x]$로 화살표를 긋는다고 생각할 수도 있다.

$F[x]$ : $S$ 를, 트라이의 루트에서 정점 $x$까지 내려오면서 만들어진 문자열이라고 하자. 이 때, $S$의 접미사들 중에서, 트라이의 루트에서 도달할 수 있는

위 $F[x]$를, 정점 $x$에 대한 실패 링크(Failure Link)라고 부른다. 사실, 결국은 KMP에서 쓰인 실패 함수의 정의와 다를 게 없다. KMP의 실패 함수 $F[i]$도, “$S[0..i]$의 접미사들 중, 접두사도 되는 가장 긴 문자열의 길이”로 정의되지 않는가!

이제, 실패 링크도 아까와 같은 최적화를 거친 DP로 계산할 수 있다는 것을 알 수 있다. 루트와의 거리가 짧은 정점부터 차례대로 실패 링크를 구한다. $F[x]$의 깊이는 언제나 $x$의 깊이보다 작기 때문에, $x$의 실패 링크를 구하는데 필요한 모든 값을 미리 알고 있다고 가정하고 계산할 수 있다. KMP 알고리즘을 구할 때와 다른 점은, DP 값의 형태 뿐이므로, Aho-Corasick 알고리즘의 구현은 위를 보고 떠올릴 수 있으리라고 생각한다.