문자열 알고리즘 (3) - KMP 알고리즘

1. 알고리즘 개요

KMP 알고리즘은 매우 복잡하기 때문에 필자도 이해하는데 상당히 오래걸렸음. 이 글을 읽는 분들은 필자처럼 1주일동안 고생하지 말고 편하게 이해했으면 좋겠는 마음에서 평소보다 훨씬 자세히 포스팅 하였음. 아래 설명을 자세히 따라오다보면 KMP 알고리즘을 완벽하게 이해하게 될 것이며, 코드까지 100% 이해할 수 있음. 많은 글들이 코드가 왜 그렇게 구현되는지는 적어놓지 않았기 때문에 이해하는데 많이 난감했는데, 이 글에서는 직접 하나하나 시뮬레이션하면서 왜 그렇게 구현되었는지까지 디테일하게 설명함.

 

기본적으로 KMP 알고리즘은 부르트포스 방식과 달리 매칭 시도중 실패했을 때 한칸 옆에가서 다시 비교를 시작하는 것이 아니라 여러칸을 건너뛰어서 다시 비교를 시작하게 됨. 실패된 매칭이였다고 하더라도 실패 이전에 매칭되었던 정보를 버리지 않고 다음 매칭을 위해 사용해보자는게 KMP 알고리즘의 핵심 아이디어임. 때문에 기존의 부르트포스 방식은 O(N * M)의 시간복잡도를 가지지만 KMP알고리즘은 O(N + M)로 사기적으로 빠른 시간복잡도를 가지게 됨.

 

2. LPS 테이블 (Logest Prefix & Suffix)

가장 먼저 Logest Prefix & Suffix 테이블(이하 LPS)을 만듬. LPS 테이블은 문자열 자기자신을 제외한 동일한 Prefix와 Suffix 쌍의 최대길이를 적어주면 됨. 말이 어려운데 아래 예시를 보면 쉽게 이해할 수 있음. 자기자신을 제외해야하기 때문에 문자열 자기자신과 동일한 길이는 Prefix, Suffix로취급하지 않음. (길이가 원본 문자열 대비 최소 1이라도 짧아야함)

 

예제 1 - abaaba : Prefix는 정방향에서부터, Suffix는 역방향에서부터 읽으면 됨. 예를 들어 abaab의 경우, Prefix는 {a, ab, aba, abaa}이고 Suffix는 {b, ab, aab, baab}임. 이 때 동일한 원소는 ab이기 때문에 ab의 길이인 2가  테이블의 값이 됨. 만약 동일한 원소가 여러개라면 가장 긴 원소를 선택함. (대부분 블로그에서 이 문자열을 예시로 함)

인덱스	문자열	테이블
0	a	0
1	ab	0
2	aba	1
3	abaa	1
4	abaab	2
5	abaaba	3

 

예제 2 - aaaaaa : Prefix와 Suffix가 겹치는 경우도 얼마든지 존재함. 예를 들어 aaaa의 경우 Prefix는 {a, aa, aaa}이고, Suffix는 역시 {a, aa, aaa}임. 모든 원소가 동일한데 이 중 가장 긴원소인 aaa의 길이는 3이기 때문에 테이블의 값은 3이 됨. 아래 그림에서 녹색은 Prefix, 노란색은 Suffix, 파란색은 겹치는 부분을 의미함.

인덱스	문자열	테이블
0	a	0
1	aa	1
2	aaa	2
3	aaaa	3
4	aaaaa	4
5	aaaaaa	5

 

3. KMP 알고리즘

KMP 알고리즘의 활용처로 굉장히 유명한 DNA 염기서열 시퀀싱 문제임. 다른 대부분 블로그에서 AAABBABAABBA 등과 같은 문자열을 사용해서 이해하는 것이 너무 어려웠음. (이해하기 이전에 보는 것도 어려움) 때문에 여기에서는 G(구아닌), C(사이토신), A(아데닌), T(티민)까지 총 4개의 문자를 사용함.

 

가장 먼저 시퀀스의 C와 패턴의 C부터 비교하기 시작하여 두 문자열에서 0번(C)와 1번(T)까지 매칭되었으나 2번(C/G)에서 매칭되지 않았음. 이 때 LPS배열(테이블)에서 가장 마지막에 매칭에 성공했던 인덱스(1번 = 'T')의 값을 가져옴. 이 때의 LPS값은 0이고, 틀린 위치(C/G)에서 0칸 뒤에서 비교하면 됨. 즉, LPS값이 0인 경우 그냥 틀린위치(C/G)에서 검사를 시작하면 됨.

 

틀린 위치에서 다시 매칭을 시도함. 0번(C)에서는 맞았으나, 1번(A/T)에서 매칭되지 않았음. 역시 가장 마지막에 매칭되었던 인덱스(0번, = 'C')의 값을 가져옴. LPS 값이 0이기 때문에 역시 틀린위치(A/T)에서 0칸 뒤로 가서, 즉 틀린위치(A/T)에서 다시 검사를 시작함.

 

이번에는 처음(A/C)부터 틀렸음. 이런 경우에는 문자열 자체가 하나도 매칭된 것이 없기 때문에 j가 증가하지 않고 j가 그대로 0인 상태에서 i만 증가시켜서 비교함.(코드보면 이해가능함) 즉, 쉽게 말해서 하나도 안맞으면 전체 문자열 시퀀스에서 그냥 한칸 옆에 가서 비교하면 됨. (이해안가면 그냥 한칸 옆에 가서 비교한다고 이해하고 아래로 넘어오길 바람. 코드보면 자연스레 이해 됨)

 

그 다음, CTGCCT까지 맞추고 6번째 인덱스인 G/A에서 맞지 않았음. 때문에 가장 최근 매칭되었던 원소(T)의 인덱스(5)에 있는 LPS 값을 확인함. 이 위치에서 LPS 값은 2인데, 그 말은 현재 틀린 위치(G/A) 이전의 2칸(C, T)는 패턴 문자열의 prefix 2칸(C, T)와 동일하다는 말임. 때문에 틀린 위치(G/A)에서 2칸 뒤로 이동해서 'C'가 있는 곳에 패턴문자열을 대고 C, T는 이미 맞는 걸 알고 있으니 G부터 다시 매칭을 시작하면 됨. (코드에서는 실제로 이렇게 뒤로 패턴문자열을 움직이진 않음. 코드를 이해하기 전에 이 단계에서는 일단 이런식으로 이해하는게 훨씬 편함)

 

위에서 언급한 것 처럼 G/A(6번 인덱스)에서 틀렸기 때문에 최근까지 매칭(CTGCCTAG)되었던 LPS테이블 값(T)은 2이고, 틀린위치 G/A에서 2칸 뒤로가서 C, T부분에 패턴 문자열을 대고 G부터 검사를 시작함. 이 경우에는 CTGCCTAG가 모두 일치했기 때문에 가장 앞 문자인 C의 위치를 결과 리스트에 담고, 리스트를 반환하면 됨.

 

4. 소스코드 분석

    @Override
    public List<Integer> search(String whole, String part) {
        List<Integer> result = new LinkedList<>();
        int w = whole.length();
        int p = part.length();

        char[] wh = whole.toCharArray();
        char[] pa = part.toCharArray();

        for (int i = 0, j = 0 ; i < w ; i++) {
        // 문자열 전체 인덱스(i)로 문자열을 순회하면서
        
            while (j > 0 && wh[i] != pa[j]){
            // 문자열이 일치하지 않을 때,
            // while인 이유는 반드시 아래 두가지 경우 중 하나여야 루프가 진행되기 때문.
            // 즉, while은 아래 두가지 경우일 수 밖에 없게 보장함. (걸려서 아래로 못내려감)
            // case 1) j=0으로 보내서 pattern 문자열을 처음부터 비교.
            // case 2) wh[i] == pa[j]이기 때문에, prefix(j)까지 일치했으므로 그 뒤부터 비교.
            
                j = table[j - 1];
                // 1) 만약 j=0이 되었다면 다음 상황에선 pattern 문자열의 처음부터 비교
                // 2) 만약 j!=0이 되었다면 i도 그 만큼(j만큼) 증가해있는 상황으로 이해하고,
                // 이미 맞은 prefix들은 검사하지 않고 그 뒤부터 비교를 진행함.
                
                // 이 부분이 핵심임. 위 설명처럼 j가 j--처럼 진짜 뒤로 움직이는게 아니라
                // j는 일치된 prefix의 끝지점까지 바로 이동해서 이미 비교가 완료된 상태로 만듬.
                
                // 예시)
                // (i=10, j=6)에서 j = table[6-1] = 2로 이동하여 (i=10, j=2)로 왔다면
                // (i=8, j=0), (i=9, j=1)인 경우는 prefix로 일치했기 때문에
                // 반드시 (wh[8] == pa[0]), (wh[9] == pa[1])가 될 수밖에 없음. 
                // 때문에 이 부분은 비교 없이 건너뛰고, (i=10, j=2)부터 비교를 시작하면 됨.
                // 즉, (i=10, j=2)인 상태에서 아래의 if문을 만나게 됨.
                
                // 코드 아래의 시뮬레이션 설명을 보고 자세히 이해바람. 
            }
                 

            if (wh[i] == pa[j]) {
            // 만약에 문자열이 일치했다면
            
                if (j == p - 1) {
                // 검사한 패턴 문자열 개수가 패턴 문자열 길이와 같다면
                // 즉, 문자열을 모두 비교했는데, 마지막 문자까지 동일했다면
                
                    result.add(i - j);
                    // 검사가 끝난 것이니, 배열에 담음. 
                    // 현재 끝 위치이기 때문에 현재 위치 i에서 패턴의 끝 위치 j를 빼면 
                    // i-j는 pattern 문자열이 전체 문차열에서 위치한 시작 인덱스가 됨.
                    // 즉, 모두 매칭된 부분의 시작위치를 리스트에 담음.
                    
                    j = table[j];
                    // 그리고 j는 현재 위치까지 전부 맞았으니 
                    // j를 일치되는 prefix의 맨 끝으로 이동시켜서 (LPS테이블)
                    // 일치하는 prefix의 뒤쪽부터 다시 비교를 시작하게 만듬.

                } else // 아직 검사중이라면
                	j++; // j를 뒤로 계속 보내서 검사를 진행
            }

        }

        return result;
        // 결과 리스트를 반환
    }

 

음... KMP 알고리즘이 대충 어떻게 흘러가는지는 이해를 했는데, 이 상태에서 코드만 보면 솔직히 처음보는 입장에선 이게 뭔소린가 싶어짐. 머릿속으로 아래그림 상황에서의 코드를 직접 돌려보면 정말 명확하게 동작이 어떻게 수행되는지 알 수 있고, 코드는 자연스레 머리에 남아서 다음에 다시 짜기도 편함.

 

 

이 설명을 모두 보고나면, 이제 KMP 알고리즘이 왜 저러한 코드로 구성되었는지 알 수 있을 것임.

1) case A : 가장 처음이기 때문에 i = j = 0으로 초기화 되어있음. (for(int i=0, j=0 ; i<w ; i++)에서 초기화)

• 가장 먼저 C에서 일치했음. while문에 걸리지 않고, if(wh[0, 'C'] = pa[0, 'C'])에서 걸림. 그러나 j(0) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함. (i=1, j=1)
• 그 다음 T에서 일치했음. while문에 걸리지 않고, if(wh[1, 'T'] = pa[1, 'T'])에서 걸림. 그러나 j(1) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=2, j=2)
• 그 다음 C/G에서 불일치했음. while(j(2)>0 && wh[2, 'C'] != pa[2, 'G'])에서, j(2)가 0보다 크고, 문자열도 일치하지 않기 때문에 while문 안으로 들어옴. j = table[2-1]이 됨. table[1] = 'T' = 0이고, j는 0이 됨. j가 0보다 크지 않기 때문에 while문을 빠져나옴. (i=2, j=0)
• 아직 이번 for루프가 종료되지 않았음. while문 다음에 있는 if문에서 case B의 그림으로 넘어감.

 

 

2) case B : case A에서 i=2, j=0인 상태에서 while문까지 지났고, case B는 if문을 만나 시작됨.

• 가장 먼저 C에서 일치했음. if(wh[2, 'C'] = pa[0, 'C'])에서 걸림. 그러나 j != p-1(7)이기 때문에 else j++;로 1 증가함. 그 후, 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=3, j=1)
• 그 다음 A/T에서 불일치 했음 while(j(1) > 0 && wh[3, 'A'] != pa[1, 'T'])에서 j(1)이 0보다 크고, 문자열도 일치하지 않았기 때문에 while문 안으로 들어옴. j = table[1-1]이 됨. table[0] = 'C' = 0이고, j는 0이됨. j가 0보다 크지 않기 때문에 while문을 빠져나옴. (i=3, j=0)
• 아직 이번 for루프가 종료되지 않았음. while문 다음에 있는 if문에서 case C의 그림으로 넘어감

 

3) case B에서 i=3, j=0인 상태에서 while문까지 지났고, case C는 if문을 만나 시작됨.

• 가장 먼저, A/C에서 불일치 했음. if(wh[3, 'A'] != pa[0, 'C'] 이기 때문에 if문에 아예 걸리지 않고, 때문에 j는 그대로 0이고, 이번 loop 종료로 인해, i++만 실행되어 i가 1 증가함. (i=4, j=0)

 

4) case C에서 i=4, j=0인 상태에서 이번 loop인 case D를 시작함. case D는 KMP 알고리즘의 핵심을 이해할 수 있는 단계이므로 자세하게 읽어보고 이해하기 바람.

 

• 가장 먼저 C에서 일치했음. while문에 걸리지 않고, if(wh[4, 'C'] = pa[0, 'C'])에서 걸림. 그러나 j(0) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함. (i=5, j=1)
• 그 다음 T에서 일치했음. while문에 걸리지 않고, if(wh[5, 'T'] = pa[1, 'T'])에서 걸림. 그러나 j(1) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=6, j=2)
• 그 다음 G에서 일치했음. while문에 걸리지 않고, if(wh[6, 'G'] = pa[2, 'G'])에서 걸림. 그러나 j(2) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=7, j=3)
• 그 다음 C에서 일치했음. while문에 걸리지 않고, if(wh[7, 'C'] = pa[3, 'C'])에서 걸림. 그러나 j(3) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=8, j=4)
• 그 다음 C에서 일치했음. while문에 걸리지 않고, if(wh[8, 'C'] = pa[4, 'C'])에서 걸림. 그러나 j(4) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=9, j=5)
• 그 다음 T에서 일치했음. while문에 걸리지 않고, if(wh[9, 'T'] = pa[5, 'T'])에서 걸림. 그러나 j(5) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=10, j=6)
• 그 다음 G/A에서 불일치 했음 while(j(6) > 0 && wh[10, 'G'] != pa[6, 'A'])에서 j(6)이 0보다 크고 문자열도 일치하지 않았기 때문에 while문 안으로 들어옴. j = table[6-1]이 됨. table[5] = 'T' = 2이고, j는 2이됨. j>0이지만, wh[10, 'G'] == pa[2, 'G']이기 때문에 while문을 빠져나옴.
• 이 부분이 KMP 알고리즘의 핵심임. i=10, j=2의 상태라는 것은, (i=8, j=0)과 (i=9, j=1)은 이미 건너뛴 상태가 된다는 것임. 그니까 j를 j-- 등으로 실제로 뒤로 보내는 게 아니라, i=10, j=2라면 j를 2번(G)부터 검사하면 되는거니까, j=0(C), j=1(T)는 이미 검사를 완료한 것 처럼되고, 이 것은 코드 이전에 설명한 패턴문자열을 뒤로 보내는 것과 동치라는 것을 알 수 있음. (위에서는 코드레벨의 이해가 없기 때문에 이해를 쉽게하기 위해서 그렇게 설명하였음) 

 

 

4) case C에서 i=10, j=2인 상태에서 이번 loop인 case E를 시작함. case E에서는 문자열이 일치되어 리스트에 추가하는 장면이 나오기 때문에 자세히 보길바람.

 

• 가장 먼저 G에서 일치했음. while문에 걸리지 않고, if(wh[10, 'G'] = pa[2, 'G'])에서 걸림. 그러나 j(1) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=11, j=3)
• 그 다음 C에서 일치했음. while문에 걸리지 않고, if(wh[11, 'C'] = pa[3, 'C'])에서 걸림. 그러나 j(1) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=12, j=4)
• 그 다음 C에서 일치했음. while문에 걸리지 않고, if(wh[12, 'C'] = pa[4, 'C'])에서 걸림. 그러나 j(1) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=13, j=5)
• 그 다음 T에서 일치했음. while문에 걸리지 않고, if(wh[13, 'T'] = pa[5, 'T'])에서 걸림. 그러나 j(1) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=14, j=6)
• 그 다음 A에서 일치했음. while문에 걸리지 않고, if(wh[14, 'A'] = pa[6, 'A'])에서 걸림. 그러나 j(6) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=15, j=7)
• 그 다음 A에서 일치했음. while문에 걸리지 않고, if(wh[14, 'A'] = pa[6, 'A'])에서 걸림. 그러나 j(6) != p-1(7)이기 때문에 else j++;로 1증가, 그 후 이번 loop 종료로 인해 i++가 실행되어 i도 1증가함 (i=15, j=7)
• 그 다음 G에서 일치했음. while문에 걸리지 않고, if(wh[15, 'G'] = pa[7, 'G'])에서 걸림. j(7) == p-1(7)이기 때문에 전체 문자열에서의 현재 위치 i(15)에서 패턴 문자열에서의 현재 위치 j(7)만큼을 뺀 값(8 = 매칭된 부분의 시작 인덱스)를 리스트에 담음. 즉, result.add(i - j); 를 수행함.
• 이후에 가장 마지막에 매칭에 성공했던 j값을 테이블(table[j])로 부터 받아서 해당 위치에서부터 검사를 다시 해줘야함. 이 예시에선 마지막 매칭에 성공했던 G의 LPS[7]값이 0이고 여기에서 시퀀스가 끝나지만, 만약 패턴이 CTGCCTAG가 아니라 CTGCCTAC였다면 LPS[7] = 1이였을 것임.

 

때문에 j=table[j]=1이 되고, i++로 i=16이 되어 (i=16, j=1)이 되면 15번부터 22번까지 있는 또 다른 패턴 매칭(CTGCCTAC)를 발견할 수 있음. 그러나 만약 j를 그냥 0으로 초기화시켜버리면 아래와 같이 저 패턴을 발견할 수 없음. 즉 패턴들이 서로 포개져서 겹칠 수 있기 때문에 j를 table[j]로 변경하여 마지막에 매칭되었던 j번째 원소의 perfix 위치로 다시 초기화 해줘야하는 것임.

 

만약 위 처럼 j=0으로 초기화하면 포개져있는 패턴을 발견할 수 없음. 때문에 j=table[j]로 초기화 시키고 loop 종료에 의해 i++가 실행되어 i=16, j=1이 되어야함.

 

 

2) LPS 테이블 생성함수

private int[] makeTable(String part) {
        // 같은 문자열(part)을 가지고 KMP 알고리즘을 실행함
        
        int size = part.length();
        char[] string = part.toCharArray();
        int[] table = new int[size];
        
        for (int i = 1, j = 0; i < size; i++) {
        // KMP 실행. (i=1, j=0으로 한칸 차이나게 포개어놓고 시작)
            
            while (j > 0 && string[i] != string[j])
            // 문자열이 일치하지 않았다면  
                j = table[j - 1];
                
            if (string[i] == string[j]) 
            // 문자열이 일치했다면  
                table[i] = ++j;
                // j를 증가시키고, 증가된 j값이 LPS값이 됨.
               
        }

        return table;
    }

LPS 테이블 생성함수는 놀랍게도 KMP 알고리즘과 매우 유사하다. KMP 알고리즘으로 LPS 테이블을 생성한다고 해도 무방하다. LPS 생성함수 시뮬레이션은 여기에서 직접하지 않고 아래의 나동빈님 동영상을 보면 쉽게 이해간다. 전체적으로 KMP 알고리즘과 매우 유사하다. 패턴 문자열을 한 칸 차이나게 포개어놓고(i=1, j=0) KMP알고리즘을 수행한다.

 

i값은 계속 증가하고 만약 문자열이 일치하면 j값이 증가하면서 테이블에 담기고, 일치하지 않으면 j값이 가장 마지막에 일치한 문자의 LPS값이 된다. LPS 테이블은 0으로 초기화 되며, 이하 내용은 동일하다. 사실상 KMP 알고리즘으로 LPS 테이블을 생성하는 것이다. (매우 신기하다) 

 

5. Reference