KMP 알고리즘에 대해 공부하다가 헷갈리는 것들이 있어 자세히 정리했다. <알고리즘 문제 해결 전략> 책을 참고했음을 밝힌다.
먼저, KMP 알고리즘이란 문자열 검색을 보다 효율적으로 실행하는 알고리즘으로, 전체 문자열의 모든 부분에서 문자열 비교를 행하지 않으면서 대상 문자열을 빠르게 검색해 낸다.
전체 문자열이 짧으면 몰라도, 수천 수만 줄로 이루어진 문서에서 단어를 검색하는 작업은 모든 글자에서 하나하나 단어를 확인하기에는 무리가 있을 수 있다. 그래서 우리는 naive한 방법보다 훨씬 효율적인 KMP 알고리즘을 사용한다.
가장 간단한 알고리즘부터 떠올려 보자
먼저, 우리가 문자열 검색을 수행하고자 하는 전체 문자열을 '짚더미(haystack)', 그리고 찾아내고자 하는 대상 문자열을 '바늘(needle)'이라고 칭하자. 짚더미에서 바늘을 찾기 위해 떠올릴 수 있는 가장 간단한 방법은 짚더미의 모든 문자열에 대해 바늘이 존재하는지 매칭을 시도해 보는 것이다. 이러한 알고리즘으로 문자열 검색을 실행할 때, 짚더미의 문자와 바늘의 문자가 모두 'a'로 이루어진 긴 문자열이라고 생각해 보자. 이 경우 짚더미의 시작부터 짚더미의 끝(바늘의 문자 개수만큼 빠져야겠지만)까지 모든 위치가 답이 된다.
문자열 검색의 경우, 일반적으로 |H|(짚더미의 길이)는 |N|(바늘의 길이)보다 훨씬 크기 때문에, 시작 위치의 수를 대략적으로 O(|H|)라고 표현할 수 있다. 또, 시작 위치마다 바늘의 길이만큼 문자 비교를 실행하기 때문에, 전체 시간 복잡도는 O(|N||H|)라고 할 수 있다.
짚더미의 모든 곳에서 비교를 시작해야 할까
일단 비교를 시작하면 비교 결과가 나오기 전까지는 바늘의 문자에 대하여 계속 짚더미와 비교를 해야 하기 때문에, 자연스레 짚더미에서 비교를 시작하는 부분을 어떻게 효율적으로 줄일 수 있을까에 대한 질문이 떠오르게 된다.
우리가 N="aabaabac"을 찾는 경우를 생각해 보자. 일곱 글자가 대응되었다가 바늘의 마지막 글자와 대응되는 위치에 있는 짚더미의 글자가 c가 아닌 다른 글자라고 했을 때, naive한 검색 알고리즘이라면 begin=i에서 문자열 탐색에 실패하였으므로 begin=i+1에서 문자열 탐색을 다시 시도할 것이다. 그러나, KMP 알고리즘의 핵심 아이디어를 통해 일곱 글자가 대응되었다는 사실을 이용하여 특정 시작 위치를 걸러낼 수 있다.
begin=i+1에서 문자열 검색을 실행하기 위해서는, H의 부분 문자열 H[i+1...i+6]이 "abaaba"여야 하지만, 그렇지 않음을 알고 있기 때문에 begin=i+1에서는 문자열 검색을 실행하지 않고 다음 시작 위치로 넘어가게 된다. 이렇게 i+1부터 i+6까지를 생각해 보면 바늘 문자열을 발견할 수 있는 시작 위치는 i+3과 i+6만이 존재함을 알 수 있다. 여기서, 우리는 이러한 정보를 추가적으로 얻기 위해서 H 상에서의 현재 위치나 H에 포함된 문자열은 보지 않았다는 사실이 중요하다. 일치한 글자의 수는 |N|을 넘을 수 없으므로, 0부터 |N|까지에 대하여 정보를 미리 전처리하는 것을 필요로 한다. 이 아이디어를 핵심으로 하여금 문자열 검색을 실행하는 알고리즘을 Knuth-Morris-Pratt 알고리즘, 줄여서 KMP 알고리즘이라고 한다.
그렇다면 우리가 전처리하여 알고 있어야 할 정보는 정확히 무엇일까? 아래 그림은 H(짚더미)와 N(바늘)을 비교했을 때, matched 글자까지 일치한 후 다음 글자가 불일치한 경우이다.
이후 우리가 전처리한 정보를 활용하여 i+k에서 N을 발견할 수 있다는 결론이 나왔다고 생각해 보자. 그렇다면 점선 안의 노란 부분의 문자열이 모두 일치해야 함을 알 수 있다. 위 두 줄의 문자열은 우리가 직접 비교를 통해 일치함을 알고 있기 때문에, 맨 위 4글자와 맨 아래 4글자가 일치함을 알고 있어야 한다. 즉, N의 부분 문자열인 N[...matched-1]의 끝 4글자(점선 안의 맨 위 4글자)와 첫 4글자(점선 안의 맨 아래 4글자)가 일치해야 한다는 것이다. 이것을 정리하면, N[...matched-1]의 길이 matched-k인 접두사(prefix)와 접미사(suffix)가 일치해야 한다고 할 수 있다.
KMP 알고리즘은 전처리 과정을 통해 위 정보를 담고 있는 배열 pi[]를 계산한다. 여기서, pi[i]는 N[...i]의 접두사이자 접미사가 될 수 있는 문자열의 최대 길이를 담고 있다. 이 배열을 흔히 부분 일치 테이블(partial match table)이라고 부른다.
실제 KMP 알고리즘의 구현
vector<int> kmpSearch(const string &H, const string &N)
{
vector<int> ret; // 짚더미에서 바늘이 있는 시작 위치를 모두 반환함
vector<int> pi = getPartialMatch(N);
int begin = 0, matched = 0;
// begin이 |H| - |N|보다 커지면 끝까지 비교해도 바늘의 문자들이 남음
while (begin <= H.size() - N.size())
{
// 일치하는 경우
if (matched < N.size() && H[begin + matched] == N[matched])
{
++matched;
if (matched == N.size())
{
ret.push_back(begin); // 끝까지 일치했다면 추가함
}
}
else
{
// 한 글자도 일치하지 않았으면 바로 다음 위치에서 탐색
if (matched == 0)
{
++begin;
}
else
{
begin += matched - pi[matched - 1]; // *1
matched = pi[matched - 1]; // *2
}
}
}
return ret;
}
*1) N[...matched-1]까지 총 matched 개의 문자열이 일치했음을 알았기 때문에, matched에서 pi[matched-1]를 뺀 만큼 begin에 더해 준다. 즉, N[...matched-1]의 접두사이자 접미사인 문자열이 길면 길수록 begin은 덜 이동하게 된다. 반대로, pi[matched-1]이 0이라면(접두사이자 접미사인 문자열이 없다면), H에서 begin부터 matched-1까지는 N을 찾을 수 없다는 뜻이므로, matched를 온전히 더해 주게 된다.
*2) begin+matched-pi[matched-1](*1에서 계산한 begin)을 nextBegin이라고 하면, 다음 반복에서 H[nextBegin]과 N[0]을 비교하는 것이 아니라, H[nextBegin...]과 N이 pi[matched-1]만큼은 이미 일치함을 알고 있기 때문에, matched는 0이 아닌 pi[matched-1]로 초기화한다.
부분 일치 테이블의 생성
그렇다면 위 코드에서 우리가 건너뛴, pi[]를 반환하는 getPartialMatch() 함수의 구현에 대해 생각해 보자. 이 역시 가장 간단하게 떠올릴 수 있는 방법은 각각의 부분 문자열에 대해 접두사이자 접미사가 될 수 있는 모든 경우의 수를 시도해 보는 것이다. N[...p-1]인 접두사에 대하여 길이가 p-1인 접두사, p-2인 접두사, ...를 모두 체크해 보는 것이다.
위와 같은 경우, length=4와 3에 대해서는 불일치가 발생했고, length=2와 1에 대해서는 불일치가 발생하지 않았으므로 이중 가장 큰 값인 2가 '접두사이자 접미사가 될 수 있는 가장 긴 문자열의 길이'가 된다. 즉, pi[4]는 2가 된다. 물론, 문자열 검색 알고리즘에서 긴 문자열로 고생하는 경우는 대개 짚더미가 길어서이고, 바늘 문자열은 그렇게 길지 않기 때문에 이정도로 충분할 수 있지만, 부분 일치 테이블을 생성하는 알고리즘 역시 최적화할 수 있다.
위 그림을 잘 보면, N[...4]에 대해 모든 경우의 수를 따져보는 방법이 사실 위 그림의 일부에 지나지 않는다는 사실을 간단히 알 수 있다. 이 사실을 이용해서, N[i]와 N[begin+i]를 비교하면서, 대응될 때마다 pi[begin+i]를 갱신해 주면 O(|N|^2)만에 pi[]를 구할 수 있게 된다.
예를 들어, begin=3일 때, i=2라면 N[5]와 N[2]가 b로 일치하고, begin부터 시작해서 총 i+1글자가 일치하였으니 pi[5]가 i+1인 3으로 갱신된다. 이 방법은 pi의 특정 인덱스에 여러 번 접근하여 갱신을 시도할 수 있기 때문에, pi에 이미 i+1보다 큰 값이 들어오면 무시해야 하는 것을 염두에 두어야 한다.
위 그림에 따라 pi[]를 갱신하는 규칙은 아래와 같다.
* pi의 모든 요소는 0으로 초기화한다.
* begin=1부터 시작한다. (begin=0은 N 자기 자신임)
* begin의 값이 바뀔 때마다 i=0부터 시작해서 N[begin+i] != N[i]일 때까지 계속 갱신한다.
* N[begin+i] == N[i]일 때 갱신을 시도하는 요소는 pi[begin+i]이다.
따라서, 예시 그림의 갱신 순서는
begin=1에서 pi[1] = max(pi[1], 1)
begin=3에서 pi[3] = max(pi[3], 1), pi[4] = max(pi[4], 2), pi[5] = max(pi[5], 3), pi[6] = max(pi[6], 4)
begin=4에서 pi[4] = max(pi[4], 1)
begin=6에서 pi[6] = max(pi[6], 1)이다.
실제로 pi[4]와 pi[6]은 두 번씩 방문되었고, N[...4]는 "aabaa"라서 후보가 되는 부분 문자열이 "a"와 "aa", N[...6]은 "aabaaba"라서 후보가 되는 부분 문자열이 "a"와 "aaba"이다.
부분 일치 테이블 생성 알고리즘의 개선
이러한 부분 일치 테이블 생성 알고리즘은 우리가 지금 읽고 있는 KMP 알고리즘을 통하여 추가로 개선할 수 있다. pi[]를 0부터 차례로 한 번씩만 방문하기 때문에 pi[]를 계산하는 중에 우리가 계산한 pi[]값을 사용할 수 있다.
vector<int> getPartialMatch(const string &N)
{
vector<int> pi(N.size(), 0);
// begin이 0이면 N 자신에 대해 찾기 때문에 1부터 시작함
int begin = 1, matched = 0;
while (begin + matched < N.size())
{
if (N[begin + matched] == N[matched])
{
++matched;
pi[begin + matched - 1] = matched;
}
else
{
if (matched == 0)
{
++begin;
}
else
{
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return pi;
}
이 알고리즘이 위에서 구현한 KMP 알고리즘과 얼마나 유사한지 비교해 보자.
시간 복잡도
KMP 알고리즘의 시간 복잡도는 반복문의 반복 횟수에 좌우됨을 알 수 있다. 그럼 이 반복문은 최대 몇 번까지 반복하게 될까? 중요한 사실은, 반복문 내에서 begin+matched가 감소하는 일이 없다는 것이다. matched가 감소하는 경우에 begin은 matched가 감소하는 만큼 증가하기 때문이다.
따라서, if문이 성공하는 것은 아무리 많아 봤자 |H|번임을 알 수 있다. if문이 실패하더라도 begin은 항상 증가하므로, 반복문은 최대 O(|H|)번 수행됨을 알 수 있다.
그러나 반복문 이외에도 우리가 생각해야 할 것은 부분 일치 테이블의 시간 복잡도이다. 부분 일치 테이블을 구하는 알고리즘 역시 KMP 알고리즘으로 이루어져 있기 때문에, 이번에는 시간 복잡도가 O(|N|)임을 알 수 있다. 즉, 전체 코드의 시간 복잡도는 O(|N|+|H|)로, 우리가 처음에 구상한 O(|N||H|)보다 훨씬 빠름을 알 수 있다.
사실 <알고리즘 문제 해결 전략> 책을 읽으면서 내용을 까먹으면 까먹었지(사실 trie같은 생소한 자료 구조는 존재만 기억나고 구체적인 내용은 이미 까먹어버렸다), 이해하는 데에는 큰 문제가 없었지만 KMP 알고리즘과 유량 네트워크 알고리즘 만큼은 내 발목을 붙잡았었다. KMP 알고리즘은 오늘 정리할 기회가 있었지만, 이 책을 다시금 읽고, 또 PS 문제를 풀면서 유량 네트워크 알고리즘과 마주하는 때가 온다면 그때는 그것에 관한 글을 쓸 지도 모르겠다.
'공부 > PS' 카테고리의 다른 글
[BOJ 1949] 우수 마을 (Gold II) (0) | 2022.11.17 |
---|---|
백준 64일 스트릭 회고 (0) | 2022.11.03 |
PS에 편한 C++ 문법 (1) | 2022.09.29 |
최단 거리 알고리즘의 이해 (0) | 2022.09.22 |