KMP법

A	B	C	A	B	D
==========================================
-	0	0	1	2	0

지난 글 : [알고리즘/Do it 알고리즘] - 브루트 - 포스법

 

KMP법 알아보기

브르투 - 포스법은 일치하지 않는 문자를 만난 단계에서 그때까지 검사한 결과를 버리고 패턴을 텍스트의 다음 칸으로 옮겨 패턴의 첫 번째 문자부터 다시 검사한다. 하지만 KMP법은 검사한 결과를 버리지 않고 이를 효과적으로 활용한다.

 

텍스트 "ZABCABXACCADEF"에서 패턴 "ABCABD"를 검색하는 경우를 예로 알고리즘을 이해하자.

1. 텍스트, 패턴의 1번째 문자부터 순서대로 검사한다. 텍스트의 1번째 문자 'Z'는 패턴에 없기에 바로 일치하지
   않는다 판단한다.
==========================================================================================================
Z	A	B	C	A	B	X	A	C	C	A	D	E	F
A	B	C	A	B	D
==========================================================================================================
2. 이제 패턴을 뒤로 1칸 옮긴다. 이때 패턴의 처음부터 순서대로 검사하면 패턴의 마지막 문자 'D'가 텍스트의 
   'X'와 일치하지 않는다.
3. 여기서 텍스트의 괄호 친 문자 "AB"와 패턴의 괄호친 문자 "AB"가 일치하고 있는 것에 주목한다. 이 부분을 
   '이미 검사를 마친 부분'으로 보면 텍스트의 'X' 다음 문자부터 패턴의 "CABD"가 일치하나만 검사하면 된다.
==========================================================================================================
Z	A	B	C	(A	B)	X	A	C	C	A	D	E	F
				(A	B)	C	A	B	D
==========================================================================================================

이처럼 KMP법은 텍스트와 패턴 사이에 겹치는 부분을 찾아내 검사를 다시 시작할 위치를 구해 패턴을 한번에 많이 옮기는 알고리즘이다. 하지만 패턴을 옮길 때마다 몇 번째 문자부터 다시 검색을 시작할지 계산해야 한다면 높은 효율을 기대하기 힘들다. 그래서 '몇 번째 문자부터 다시 검색할지'에 대한 값을 미리 '표'로 만들어 이 문제를 해결한다.

 

a)
X	?	?	?	?	?	?	?	?	?	?	?	?	?
(A)	B	C	A	B	D

							▼
                            
X	?	?	?	?	?	?	?	?	?	?	?	?	?
	(A)	B	C	A	B	D
=====================================================================================================
b)
A	X	?	?	?	?	?	?	?	?	?	?	?	?
A	(B)	C	A	B	D

							▼
                            
A	X	?	?	?	?	?	?	?	?	?	?	?	?
	(A)	B	C	A	B	D
=====================================================================================================
c)
A	B	X	?	?	?	?	?	?	?	?	?	?	?
A	B	(C)	A	B	D

							▼
                            
A	B	X	?	?	?	?	?	?	?	?	?	?	?
		(A)	B	C	A	B	D
=====================================================================================================
d)
A	B	C	X	?	?	?	?	?	?	?	?	?	?
A	B	C	(A)	B	D

							▼
                            
A	B	C	X	?	?	?	?	?	?	?	?	?	?
			(A)	B	C	A	B	D
=====================================================================================================
e)
A	B	C	A	X	?	?	?	?	?	?	?	?	?
A	B	C	A	(B)	D

							▼
                            
A	B	X	A	X	?	?	?	?	?	?	?	?	?
			A	(B)	C	A	B	D
=====================================================================================================
f)
A	B	C	A	B	X	?	?	?	?	?	?	?	?
A	B	C	A	B	(D)

							▼
                            
A	B	C	A	B	X	?	?	?	?	?	?	?	?
			A	B	(C)	A	B	D

a) 1번째 문자가 일치하지 않는다 -> 1번째 문자부터 검사를 다시 시작한다.

 

b) 2번째 문자가 일치하지 않는다 -> 1번째 문자부터 검사를 다시 시작한다.

 

c) 3번째 문자가 일치하지 않는다 -> 1번째 문자부터 검사를 다시 시작한다.

 

d) 4번째 문자가 일치하지 않는다 -> 1번째 문자부터 검사를 다시 시작한다.

 

e) 5번째 문자가 일치하지 않는다 -> 2번째 문자부터 검사를 다시 시작한다.

 

f) 6번째 문자가 일치하지 않는다 -> 3번째 문자부터 검사를 다시 시작한다.

 

해설)

a ~ d : 패턴의 1 ~ 4번째 문자에서 검사에 실패하면 패턴을 옮긴 후 1번째 문자부터 다시 검사한다.

 

e : 패턴의 5번째 문자에서 검사에 실패하면 패턴을 옮긴 후 1번째 문자가 일치하므로 2번째 문자부터 다시 검사할 수 있다.

 

f : 패턴의 6번째 문자에서 검사에 실패하면 3번째 문자부터 다시 검사할 수 있다.

 

표를 작성하려면 패턴 안에서 중복되는 문자열을 찾아야 한다. 이때도 KMP법의 아이디어를 이용한다. 패턴 안에서 중복되는 문자열을 찾기 위해 패턴끼리 겹쳐 놓고 생각해보자. 텍스트와 패턴의 1번째 문자가 서로 다른 경우 패턴을 1칸 뒤로 옮기고 패턴의 1번째 문잡터 다시 검사해야 하는 것은 분명하니 패턴의 2번째 문자부터 생각한다. 

 

패턴 "ABCABD"를 두 줄로 겹쳐 놓고 아랫줄을 1칸 뒤로 옮긴다. 아래를 보면 괄호 부분이 겹치지 않으므로 패턴을 다시 1칸 옮길 경우 1번째 문자부터 검사를 다시 시작해야 함을 알 수 있다.

(A	B)	C	A	B	D
	(A)	B	C	A	B	D

A	B	C	A	B	D
===========================================
-	0

그러므로 2번째 문자(B)의 다시 시작하는 값은 0이다. 이는 패턴의 1번째 문자(인덱스 0)부터 검사를 다시 시작한다는 의미다. 다시 패턴을 1칸 뒤로 옮긴다. 문자가 일치하지 않으므로 표에서 3번째 문자(C)의 값을 0으로 한다.

(A	B	C)	A	B	D
		(A)	B	C	A	B	D

A	B	C	A	B	D
==========================================
-	0	0

다시 패턴을 1칸 뒤로 옮기면 "AB"가 일치한다. 여기서 아래와 같은 사실을 알 수 있다.

1. 패턴의 4번째 문자 'A'까지 일치하면 패턴을 텍스트의 다음 'A'까지 한번에 옮긴 뒤 'A'를 건너뛰고 2번째
   문자부터 검사할 수 있다.
2. 패턴의 4번째, 5번째 문자 'AB'까지 일치하면 패턴을 텍스트의 다음 'AB'까지 한번에 옮긴 뒤 'AB'를 
   건너뛰고 3번째 문자부터 검사할 수 있다.

따라서 표에서 4번째와 5번째 문자의 경우 다시 시작하는 값을 1, 2로 한다.

(A	B	C	A	B)	D
			(A	B)	C	A	B	D

A	B	C	A	B	D
==========================================
-	0	0	1	2

(A	B	C	A	B	D)
					(A)	B	C	A	B	D

이제 표 만들기는 끝났다. 

 

아래는 KMP법을 사용해 문자열을 검색하는 프로그램이다.

kmpMatch 메서드가 전달받는 인수나 반환값은 브루트 - 포스법의 함수 bfMatch와 같다.  1번째 while문에서 다시 시작하는 값을 표로 만들고 2번째 while문에서 실제 검색을 수행한다. KMP법에서 텍스트를 스캔하는 커서 pt는 앞으로 나아갈 뿐 뒤로 돌아오는 일은 없다. 하지만 KMP법은 브루트 - 포스법보다 복잡하고, 내일 공부할 보이어•무어법은 성능이 같거나 오히려 낮아 실제 프로그램에서는 잘 사용하지 않는다고 한다.

 

어차피 이 길로 가려면 찝찝하게 대충 아는 것보다 잘 아는게 낫다 생각해 열심히 공부했는데 갑자기 잘 쓰이지 않는다 하니 허무하다. 😢😭

 

참고 서적 :