KMP 알고리즘 - Knuth, Morris, Prett

SEUNGHWANLEE·2021년 10월 20일

Algorithm

목록 보기

11/14

흔히 찾는 문자나 문자열이 있는 지 없는 지를 확인할 때는 주로 if pattern in words 이런 식으로 검사를 할 수 있다. 하지만, words의 길이가 수없이 길어진다면 어떻게 될까? 만약의 words의 길이가 1,000,000 이라고 가정하고 찾는 문자열의 길이가 1,000 이라고 할 때 총 걸리는 시간은 $O(1,000,000 \times 1,000)$ 만큼의 시간이 걸리게 될 것이다. 예전에 학교에서 프로젝트를 하면서 배웠던 BNDM이나 KMP 알고리즘으로 문자열 관련 프로젝트를 했었는데 그때 이후에 쓰고 구현하려니 쉽지 않아서 새롭게 포스팅하기로 했다 😭

KMP 알고리즘이란?

접두사(prefix)와 접미사(suffix)를 이용하는 알고리즘이다. 처음에 들었을 때는 한번에 이해가 되지는 않지만 찾는 방식을 따라서 그려보면 이해하기 수월할 수 있다. KMP 알고리즘에서는 접두사와 접미사를 이용해서 pi 테이블을 만들어 사용한다. 만들어낸 pi 테이블을 가지고 찾으려는 string에서 pattern을 찾아내는 방법이다. 그럼 앞서 언급한 pi 테이블은 무엇일까?

pi 테이블

pi 테이블은 찾으려는 문자열(pattern)의 정보를 저장하고 있는 배열, 자료구조이다. 예시와 함께 보면 이해하기 쉽다. 예를 들어서 찾으려는 문자열(pattern)이 "abacaaba" 라고 가정해보자.

💡 구성요소

pattern 내 순환할 포인터(i)
table 내 순환할 포인터(j)
pattern의 크기(길이)

테이블을 만들면서 저장하려는 정보는 i번째 index까지 접두사(prefix)와 접미사(suffix)가 같은 갯수를 저장한다.

length	string	value
1	a	0
2	ab	0
3	a b a	1
4	abac	0
6	a bac a	1
7	ab ac ab	2
8	aba ac aba	3

위와 같이 prefix와 suffix를 보고 테이블에 저장해 후에 찾으려는 패턴을 어디까지 찾았는지 기억하면서 찾을 수 있기 때문에 테이블을 만드는 작업이 중요하다.

만약에 갖고있는 string을 "abacaabeabacaaba" 라고 가정을 해보면, $O(N \times M)$ (N은 string의 길이, M은 pattern의 길이) 동안 검색을 해야되는데 테이블을 사용하면 이를 $O(N + M)$ 으로 단축할 수 있다. 예를 들어 아래와 같은 탐색과정을 거치게 되는데

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
string	a	b	a	c	a	a	b	e	a	b	a	c	a	a	b	a
pattern	a	b	a	c	a	a	b	a
match	O	O	O	O	O	O	O	X

이때 index가 7인 지점에서 매칭이 안되는 걸 알 수 있다. 여기서 "abacaaba"를 index가 1부터 다시 매칭 검사를 하는 것이 아니라 index가 5와 6인 곳까지 매칭이 이루어졌기때문에 index 1부터 다시 매칭 검사하는 작업을 줄일 수 있다. 작업을 줄이는 과정에서 pi 테이블이 필요한 것이다.

pi 테이블을 다시 보면 현재까지 매칭이 올바르게 진행된 길이는 "abacaab" 총 7이다. length가 7인 테이블에서 value값은 여기서 2인 것을 확인할 수 있다. 이제 일치하는 접두사 만큼 탐색을 시작할 위치를 옮겨준다.

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
string	a	b	a	c	a	a	b	e	a	b	a	c	a	a	b	a
pattern			a	b	a	c	a	a	b	a
match			O	X

과정 반복 후 👇

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
string	a	b	a	c	a	a	b	e	a	b	a	c	a	a	b	a
pattern									a	b	a	c	a	a	b	a
match									O	O	O	O	O	O	O	O

이런식으로 접두사가 일치한 크기만큼 더해가다보면 그만큼 중간과정을 생략할 수 있다.

Summary

string을 탐색하는 index = i
pattern을 탐색하는 index = j
match가 "O"인 부분까지 가장 많이 일치한 접두사==접미사 길이(K)만큼 i + K 후 비교 작업, 이때 j = table[j-1], K는 pi 테이블로 부터 얻을 수 있음

pi 테이블 만들기

👉 pattern: "abacaaba", size: 8
👉 i는 1부터 시작
👉 j는 0부터 시작
👉 table은 모두 0으로 초기화

i는 1부터 pattern의 길이만큼 순회, j는 pattern[i]와 pattern[j] 가 다르면 table[j-1]으로 초기화

index	0	1	2	3	4	5	6	7
char	a	b	a	c	a	a	b	a
i		v
j	v
table	0	0	0	0	0	0	0	0

다음 👇

index	0	1	2	3	4	5	6	7
char	a	b	a	c	a	a	b	a
i			v
j	① v →	v
table	0	0	② 0 → 1	0	0	0	0	0

pattern[i] == pattern[j] 이 True 인 관계로 해당 table[i] = ++j

다음 👇

index	0	1	2	3	4	5	6	7
char	a	b	a	c	a	a	b	a
i				v
j	v	← v
table	0	0	1	0	0	0	0	0

하지만 여기서 pattern[i] == pattern[j] 이 False 이므로 j = table[j-1] 이 반복되게 된다.

과정 반복 후 index = 5, i 도착 👇

index	0	1	2	3	4	5	6	7
char	a	b	a	c	a	a	b	a
i						v
j	① v →	v
table	0	0	1	0	1	② 0 → 1	0	0

i번째와 j번째가 동일한 a이므로 table[i] = ++j 을 해준다.

다음 👇

index	0	1	2	3	4	5	6	7
char	a	b	a	c	a	a	b	a
i							v
j		① v →	v
table	0	0	1	0	1	1	② 0 → 2	0

pattern[i] == pattern[j] 이 True 인 관계로 해당 table[i] = ++j

설명이 길었지만 위와 같은 방식으로 테이블을 채워가다보면 아래와 같은 테이블을 얻을 수 있다.

index	0	1	2	3	4	5	6	7
table	0	0	1	0	1	1	2	3

소스코드로 확인해도 결과는 동일하게 나오는 것을 확인할 수 있다.

create_table(pattern) - python

💡 소스코드

def create_table(pattern):
    table = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = table[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
    return table

🔥 결과화면

이제 pi 테이블을 만들었으니 사용할 일만 남았다. KMP 알고리즘을 위 설명 처럼 구현해보자.

💡 구성요소

주어진 문자열(parent)을 탐색할 index, i
찾으려는 문자열(pattern)을 탐색할 index, j
pattern으로 생성한 pi 테이블

KMP(parent, pattern) - python

💡 소스코드

def KMP(parent, pattern):
    table = create_table(pattern)
    j = 0
    for i in range(len(parent)):
        while j > 0 and parent[i] != pattern[j]:
            j = table[j - 1]
        if parent[i] == pattern[j]:
            if j == len(pattern) - 1:
                return 1
            else: j += 1
    return 0

구성요소처럼 i는 주어진 parent를 처음부터 순회를 하게된다. 그리고 j는 0보다 클 때 pattern[j]와parent[i]가 같으면 그때 j가 얼만큼 비교를 해서 왔는지 확인해준다. 이게 무슨 말이냐면 j가 1이라면 그동안 앞에서 2자리가 동일하다는 것을 알 수 있으니, j 가 pattern의 크기 - 1만큼 더해져있다면 이는 주어진 문자열 내에서 찾으려는 문자열을 발견했다고 할 수 있다. 찾으려는 문자열의 index는 i - len(pattern) + 2로 구할 수 있다.