[알고리즘] 문자열 매칭 알고리즘 - KMP (Knuth-Morris-Pratt) Pattern matching

아래 링크 강의를 수강하고 정리하였습니다. 기초 학습 단계로 부정확한 정보가 있을 수 있습니다.

https://youtu.be/yWWbLrV4PZ8 / 나동빈님의 실전 알고리즘 강좌 34강

https://www.youtube.com/watch?v=UcjK_k5PLHI   / 코드없는프로그래밍님의 String 강좌

https://youtu.be/GTJr8OvyEVQ / Tushar Roy -  KMP Pattern matching

---

문자열 매칭 알고리즘이란, 특정한 글이 있을 때 그 글안에서 주어진 문자열을 찾는 알고리즘이다. 이전까지 문자열을 찾는 경우에는 브루트포스처럼 O(nm)의 시간을 소요해 문자열을 찾았었다. 이 과정에 KMP 문자열 매칭 알고리즘, 라빈-카프 문자열 매칭 알고리즘을 도입해 매칭에 소요하는 시간을 줄일 수 있다.

 

이런 예를 들어 KMP 알고리즘과 라빈-카프 알고리즘을 순서대로 말해보자면

먼저, KMP알고리즘은 prefix, postfix 개념을 도입해 복잡한 매칭 반복 연산 과정을 줄이기 위해 '실패 함수'를 구현한다.

나동빈님의 강의를 보면, 이 지표 데이터를 접두사(prefix)와 접미사(suffix)가 일치하는 최대 길이라고 설명했는데, 쉽게 말하면 주어진 긴 문자열에서 중복된 문자의 인덱스 데이터를 구해 중복의 다음 인덱스로 매칭포인터를 점프시킨다는 것이다. 여기서 실패 함수는, 매칭을 실패한 경우, 문자가 반복되는 패턴을 기입해서 다시 어떤 인덱스부터 매칭을 하면 되는지 알려줄 지표 데이터를 저장하는 함수이다. 

 

이 개념에서 헷갈렸던 점은, 문자열 매칭이라는 이름때문에 단순히 두 문자열을 비교하는 개념으로 생각했었던 점이었다. 이 KMP 알고리즘은 단순히 문자열 비교에 그치지 않고 문자열 내부의 중복을 패턴 데이터로 저장해 매칭 포인터를 "Jump"할 수 있다는 것이다. 특히, prefix와 suffix가 하나의 문자열인 경우, suffix의 앞 인덱스에서 매칭을 검사하면 된다.

 

아래는 KMP알고리즘의 예시이다.

a	a	a	a	a	b	b
a	a	a	a	b	b

긴 문자열로 "aaaaabb"와, 짧은 문자열로 "aaaabb"가 주어졌다고 생각해보자.

a	a	a	a	a	b	b
a	a	a	a	b	b
0	1	2	3	0

두 문자열의 첫 문자를 가리키는 포인터를 만들고 비교해 나아갈 때, 이전 문자와 중복인경우 패턴 데이터 값을 1씩 증가시킨다. 긴 문자열과 짧은 문자열은 "a"가 4번 반복되므로 인덱스 3까지 계속 증가한다. 그러나, "b"를 매칭시켜보는 순간, 그 이전의 문자들과 매치되지 않으므로 인덱스가 0이된다. 패턴 데이터를 살펴보면, "aaaa"가 하나의 prefix이자 suffix이다.

a	a	a	a	a	b	b
	j
	a	a	a	a	b	b
				matching!

접두사이자 접미사인 "aaaa"문자열이 끝나는 인덱스의 이전 포인터, [3]을 매칭이 실패한 포인터와 매칭시켜본다. 

매칭이 성공했다. 이때 parent string의 pointer는 [1]을 가리키고 있다.

a

b

c

x

a

b

c

d

a

b

x

a

b

c

d

a

b

c

y

a

j

a

b

c

d

a

b

c

y

i

긴 문자열 "abcxabcdabxabcdabcya"가 있을 때, 짧은 문자열 "abcdabcy"를 매칭해보자. 먼저 각각의 문자열 첫 글자를 가리키는 포인터 j와 i를 만든다.

a

b

c

x

a

b

c

d

a

b

x

a

b

c

d

a

b

c

y

a

a

b

c

d

a

b

c

y

x

맨앞에서 부터 비교하면, 'x'에서 불일치가 생긴다.

a

b

c

x

a

b

c

d

a

b

x

a

b

c

d

a

b

c

y

a

a

b

c

d

a

b

c

y

x

그렇다면 짧은 문자열을 'x'부터 대조한다. 결과는 불일치이다.

a

b

c

x

a

b

c

d

a

b

x

a

b

c

d

a

b

c

y

a

a

b

c

d

a

b

c

y

x

'x'와 불일치 이므로, 매치 포인터를 그 다음 글자인 'a'로 옮긴다. 'a'부터 짧은 문자열을 대조해보면, 다시 'x'에서 불일치가 생긴다.

a

b

c

x

a

b

c

d

a

b

x

a

b

c

d

a

b

c

y

a

a

b

c

d

a

b

c

y

x

불일치가 생긴 지점에서 짧은 문자열 "abcdabcy"을 살펴보면, "ab"는 문자열 그 자체로 prefix이자 suffix이다. 그러므로, mismatched pointer는 prefix의 뒤 인덱스의 'c'를 비교한다.

a

b

c

x

a

b

c

d

a

b

x

a

b

c

d

a

b

c

y

a

a

b

c

d

a

b

c

y

x

prefix인 "ab"의  뒷 문자 c가 x와 불일치 한다는 것을 알았으므로 다시 짧은 string의 첫 인덱스를 mismatched pointer가 가리키는 문자 'x'와 비교한다

a

b

c

x

a

b

c

d

a

b

x

a

b

c

d

a

b

c

y

a

a

b

c

d

a

b

c

y

x

이 또한 일치하지 않으므로, 'x'를 가리키는 포인터를 증가시켜 짧은 string을 매칭한다.

a

b

c

x

a

b

c

d

a

b

x

a

b

c

d

a

b

c

y

a

a

b

c

d

a

b

c

y

찾았다~

 

위 그래프의 예와, 강의를 토대로 코드를 작성해보았다.

/*
KMP 문자열 매칭 알고리즘
*/

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> makeTable(string pattern) // comparing prefix and suffix to make faillure table 
{
	int patternSize = pattern.size();
	vector<int> table(patternSize, 0); //init 0 
	
	int j = 0;
	for (int i = 1; i < patternSize; i++) // Searching pattern
	{
		while (j > 0 && pattern[i] != pattern[j]) // j포인터가 가리키는 왼쪽 데이터와 i포인터가 가리키는 오른쪽 데이터를 비교
		{
			j = table[j - 1]; // 두 데이터가 일치하지 않을 경우 j 포인터는 이전 접두사 데이터(prefix)의 끝을 가리킴
		}
		if (pattern[i] == pattern[j]) table[i] = ++j;
	}
	return table;
}

void KMP(string parent, string pattern)
{
	vector<int> table = makeTable(pattern);
	int parentSize = parent.size();
	int patternSize = pattern.size();

	int j = 0;
	for (int i = 0; i < parentSize; i++) 
	{
		while (j > 0 && parent[i] != pattern[j]) j = table[j - 1];
		if (j == patternSize - 1)
		{
			cout << "Found word at index [" << i - patternSize + 2 << "]." << '\n';
			j = table[j];
		}
		else {
			j++;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//solve();

	string parent = "ababacabacaabacaaba";
	string pattern = "abacaaba";
	KMP(parent, pattern);
	return 0;
}

KMP 매칭 알고리즘을 공부하면서 느꼈던 어려운 점은, 매칭 대상인 패턴데이터에서 prefix와 suffix의 관계를 어떤 원리로 찾아낸건지 이해하기 어려웠다는 점이었다.. 역시 여러 번 다양한 강의를 살펴보고 대조하니 점점 이해가 되어가고 있지만, 실습을 통해 보다 더 깊게 원리를 이해해야할 것 같다. 

 

또한, KMP 패턴 매칭보다 더 직관적인 알고리즘인 "Rabin-Karp(Rolling Hash)" 문자열 매칭 알고리즘이 있다고 한다. 다음 포스트에선 이를 공부해 기록해보자.