문자열 패턴 매칭 3 - KMP

* 본 포스팅은 인사이트 프로그래밍대회에서 배우는 알고리즘 문제해결 전략을 참조해서 작성되었습니다.

 

다음으로는 '비교해보지 않고도 알수 있는 것이 있다'는  KMP에 대해 알아보자. 이 알고리즘은 Knuth-Morris-Pratt 세 사람의 이름을 딴 알고리즘이다.

 

Brute Force는 한 칸씩 이동하면서 비교하기 때문에 불필요한 비교 회수가 많이 발생하는데 이를 줄여서 연산을 빠르게 수행하는것이 K.M.P 알고리즘이다.

 

KMP는 패턴 비교 과정에서 발생한 부분일치 문자열을 버리지 않고 건너뛸 수 있는 기회로 사용한다. 

다음 그림을 살펴보자. 타겟과 패턴 문자열을 비교해보니 처음 비교에서 7번째에서 불일치가 발생했다. Brute Force방식을 적용한다면 이후 한 칸씩 패턴을 이동시켜보면서 타겟과의 일치 여부를 확인할 것이다. 아래 그림처럼 말이다.

 

 

그런데 처음 비교 즉 i 번째 비교에서 우리가 알아야할 사실은 j=7에서 불일치가 발생했다는 사실 뿐이 아니라 0 ~ 6까지는 일치했다는 점이다. 이 점을 이용하면 시작 위치 중 일부는 답이 될 수 없음을 하나씩 대보지 않아도 알 수 있다.

 

빨간색 테두리 부분은 타겟 문자열과 패턴이 일치하는 영역인데 거기서 패턴과의 연관성을 파악해보면 i+1, i+2, i+4, i+5 4가지는 불일치가 발생하기 때문에 비교해볼 필요가 없는 것이다. i+3와 i+6의 경우는 빨간색 박스 내에서는 일치한다. 이들을 점검 대상이다.

 

그럼 어떻게 i+1, i+2, i+4, i+5가 불필요하다는 것을 알아서 건너뛰고 i+3, i+6에서 다시 검색을 시작할 수 있을까? 이를 위해 접두부, 접미부의 개념과 이를 바탕으로 Pi 배열을 만들 수 있어야 한다.

 

접두부와 접미부의 개념

접두부와 접미부는 말 그대로 패턴의 앞 부분과 뒷 부분을 말한다.

접두부와 접미부를 구할 때 주의할 점이 두 가지있는데

 - 첫째는 전체 문자열은 접두부, 접미부가 아니다.

 - 둘째는 접미부를 읽을 때 뒤에서 읽지 않고 앞에서 읽는다.

예를 들어 AABAA라는 문자열에서 접두부와 접미부를 살펴보자.

 

그림만 봐도 어떻게 접두부와 접미부를 구별하는지 알 수 있다. 접두부와 접미부는 찾으려는 패턴에서 한 글자씩 늘려가면서 찾을 수 있다. 따라서 길이가 5인 패턴은 총 4개(전체 문자열 제외)의 접두, 접미 쌍이 나올 수 있다.

 

다음에 검색을 시작할 위치 찾기

빠른 검색과 접두부/접미부는 어떤 관계가 있을까? 다음 그림을 살펴보자.

일단 pattern은 target의 i 번째 즉 target[i]부터  matched 개가 일치하는 상황이다. X에서 불일치가 발생했다. [pattern, j=i]와 target의 회색 부분은 동일하다고 했으니까 당연히 굵은 선 안의 A와 B의 내용은 같을 것이다. 

 

위 그림에서 N은  패턴 문자열을 나타내고 ...i라는 것은 0~i까지의 부분 문자열을 의미한다. 따라서 N[...matched-1]은 패턴 문자열에서 matched개의 문자가 일치한 경우로 패턴에서 0~matched-1까지의 문자열을 일컫는다.

 

이 시점에서 [pattern j=i+k]가 답이 될 수 있으려면 B와 C도 당연히 같아야 한다. 결과적으로 A와 C도 같아야 하는데 잘 살펴보면 A가 바로 N[...matched-1]의 접미부이고 C는 접두부이다.!!

결국 i+k 에서부터 시작한 검색이 매치가 되려면 N[...matched-1]인 문자열에서 길이 matched-k인 접두어와 그만큼 길이의 접미어가 같아야 한다.

이 상황에서 다음 비교 위치를 계산하기 위해서는 접두부와 접미부가 일치하는 최대 길이(matched-k)가 필요하다. 이를 알면 k만큼 건너뛸 수가 있다.  최대 일치 길이가 적다면 한번에 건너뛰는 k가 그만큼 커질 것이다. 따라서 예제처럼 반복되는 패턴이 아니라 실제 문장을 검색한다면 접두/접미 일치가 길지 않으므로 효율이 매우 뛰어나게 된다.

 

 

이제 우리는 pattern에서 matched 개의 문자열이 일치할 때 접두부와 접미부가 같은 최대 길이인 matched-k가 필요하다. 이 값들은 패턴만 정의되면 타겟 문자열과 무관하게 계산할 수 있기 때문에 본격적인 매칭 파악 전에 미리 구해 놓는다. 이 값을 저장할 때 부분 일치 테이블(Partial match table)을 이용하는데  통상 pi라는 배열을 사용한다.

 

Partial match table(부분 일치 테이블) Pi 배열 작성

K.M.P는 패턴 비교의 전처리로 Pi라는 배열을 만드는데 pi의 정의는 아래와 같다.

pi[i] = N[...i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이

여기서 N은 패턴 문자열을 나타내고 ...i라는 것은 0~i까지의 부분 문자열을 의미하므로 i+1길이의 부분문자열에서 최대 접두/접미부 길이를 의미한다.

위 정의를 기반으로 패턴 AABAABAC의 부분일치 테이블을 만들어보면 아래와 같다.

 

따라서 pi는 아래와 같이 구할 수 있다.

 

문자열 검색의 구현

이제 실제적인 코드를 구현해보자. target문자열의 begin에서 시작한 비교과정에서 matched 개의 문자가 일치한 후 불일치가 되었을 때 다음으로 target에서 검색을 시작할 위치 begin`은 어디일까? 

 

 

 위 그림을 참조해보면 C가 있는 위치이기 때문에 패턴의 비교 시작 위치 begin`는 다음과 같이 나타낼 수 있다.

begin` = begin + k = begin + matched - (matched-k)

여기서 matched-k 즉 접두/접미가 일치하는 최대 길이는 di 배열에 저장해둔 값이므로 위 식은 아래로 수정할 수 있다.

begin` = begin + matched - pi[matched-1]

드디어 pi 배열이 등장했다.

또하나 잊지 말아야 할 것은 다음 비교 위치 matched 도 0부터 시작할 필요는 없다는 점이다. pi[matched-1]까지는 이미 일치하므로 확인할 필요 없고 그 다음부터 비교해보면 된다.

따라서 이 시점에서 매칭된 길이 matched는 다음과 같다.

matched = pi[matched - 1];

 

중간에 건너뛰기도 했고 검색 시작 위치도 pi[matched-1]만큼 뒤로 이동했으므로 비교 회수가 상당히 많이 줄어들었다.

이제 한 글자씩 비교해가면서 pattern의 matched와 target의 begin + matched가 같으면 matched를 1증가 시켜가며 진행한다. 만약 비교 도중 답을 찾은 경우 (즉 matched==pattern.length())에는 검색 시작 위치인 begin를 답으로 출력해준다.

불일치가 발생했을 때

만약 아직까지 하나도 일치하지 않은 상태(matched==0)라면 begin만 증가시켜서 다음 문자를 비교한다.

그렇지 않고 기존에 matched가 있었다면 이것을 이용해서 이동한다.

 

이를 소스 코드로 구현해보자. 

아직은 pi가 어떻게 구해졌는지 모르지만 이미 구해져 있다고 하자.

 public static void kmp(String target, String pattern) {
    int tl = target.length();
    int pl = pattern.length();
    // pi 배열: 구해왔다고 친다.
    int[] pi = getPi(pattern); 

    int begin = 0, matched = 0;

    while (begin +pl <= tl) {

        if (matched < pl && pattern.charAt(matched) == target.charAt(begin + matched)) {
            matched++;
            if (matched == pl) {
                System.out.print(begin + "에서 패턴 발견\t");
            }
        }
        else {
            if (matched == 0) {
                begin++;
            }
            else {
                begin = begin + matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
}

 

이 과정에서의 시간 복잡도는 일단 Pi 배열을 구하는 부분을 제외한다면 O(m)의 시간 복잡도를 가진다. 여기서 m은 타겟 문자열의 길이이다.

 

부분 일치 테이블의 작성

이제 마지막으로 살펴볼 부분은 부분일치 테이블을 작성 즉 최장 접두, 접미부를 찾는 과정이다.

접두, 접미부를 찾는 가장 쉬운 방법은 부분 문자열 N의 각 접두사에 대해 가능한 답을 하나씩 모두 시도하는 것이다. 다음 그림은 N[...4]즉 길이가 5인 패턴에 대해 최대 접두/접미부를 찾는 과정이다.

 

 

위 그림을 살펴보면 길이가 5일 때 최대 일치 접두/접미부의 길이는 length=2일 때인 2임을 알 수 있다. 

위 그림을 좀 더 확장해보면 아래와 같이 그려볼 수 있다.

 

어디서 많이 본 그림이다. 바로 상단부에서 패턴과 문자열을 비교하면서 건너뛸 위치를 결정할 때 사용했던 그림과 동일하다. 접두, 접미부는 전체 문자열에 대해서는 생각하지 않기 때문에 j=6까지에서 찾으면(j=7이 불일치라고 생각하면) kmp와 거의 유사한 코드를 사용할 수 있다.

아까와의 차이점은 pi를 만들어가는 과정인데 여기서는 단순 활용이 아니라 채워가는 과정이다.

 

public static int[] getPi(String pattern) {
    int pl = pattern.length();
    int[] pi = new int[pl];
    
    int begin = 1, matched = 0;
    
    while (begin + matched < pl) {	
        if (pattern.charAt(matched) == pattern.charAt(begin + matched)) {
            matched++;
            pi[begin + matched - 1] = matched;
        } else {
            if (matched == 0) {
                begin++;
            } else {                
                begin = begin + matched - pi[matched - 1]; 
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}

이 전처리 과정에서 발생하는 비용은 O[n]이다.  n은 패턴의 길이이다.

따라서 전체적으로 KMP의 시간 복잡도는 O(n+m)이 된다. 

Brute Force: https://goodteacher.tistory.com/127
RabinKarp: https://goodteacher.tistory.com/128
KMP: https://goodteacher.tistory.com/129