[String Matching] KMP(Knuth-Morris-Pratt) 알고리즘

서론

 

 

String Matching (문자열 매칭) 알고리즘은 주어진 텍스트에서 특정 패턴을 찾을 때 사용하는 알고리즘이다.  

대표적인 문자열 매칭 알고리즘에는 

 

1. 브루트 포스 알고리즘
2. KMP 알고리즘
3. Rabin-Karp 알고리즘
4. Boyer-Moore 알고리즘
5. Sunday 알고리즘

등이 있으며 여기서는 KMP 알고리즘에 대해 알아보려고 한다.

 

KMP 알고리즘은 Knuth , Morris, Pratt 3명의 사람이 설계한 알고리즘으로, 전체 문자열에서 특정 문자열을 찾는 알고리즘이다.

 

시간 복잡도는 N(전체 문자열 길이) + M(패턴 문자열 길이) 가 나온다.

 

결과값으로는 다음과 같이 나올 수 있으며 필요한 값을 반환시키면 된다!

• 인덱스 리스트 : 패턴이 텍스트 내에서 발견된 모든 시작 위치를 반환
• 불리언 값 : 패턴이 텍스트 내에 존재하는 지 여부를 반환
• 첫 매칭 인덱스 : 패턴이 텍스트 내에서 처음으로 발견된 위치를 반환

 

구현

아이디어

 

KMP 알고리즘의 가장 중요한 아이디어는 문자열이 불일치 할 때 탐색을 시작했던 위치의 다음 문자 부터가 아닌, 우리가 앞서 탐색했던 정보를 이용하여 몇 칸 정도는 건너 뛴 후 탐색할 수 있지 않을까? 부터 시작한다.

 

만약 문자열 탐색을 건너 뛸 수 있다면 어떤 전제조건이 꼭 성립해야 할까?

 

건너 뛴 후의 패턴의 앞 부분과 텍스트의 뒷 부분이 일치해야 한다 가 전제 조건으로 성립해야 한다.

 

건너 뛴 후의 패턴과 텍스트가 일치해야 그 이후로 탐색을 진행할 것이기 때문이다.

 

탐색 문자열 = 텍스트 , 원본 문자열 = 패턴

 

반대로 일정부분 건너 뛴 후 패턴과 텍스트가 일치하지 않는다면, 건너뛰는 의미가 없다.

 

여기서 얻을 수 있는 결론은 패턴의 앞 부분과 텍스트의 뒷 부분이 동일한 부분까지는 문자열 탐색을 건너뛸 수 있다는 사실이다.

 

 

 

부분 일치 테이블 (LPS 배열) 생성

 

부분 일치 테이블은 패턴의 각 위치에서 최대한으로 일치하는 접두사(prefix) 와 접미사(suffix) 의 길이를 저장한다.

 

부분 일치 테이블을 만들기 위해서는 각 위치에서 접두사와 접미사가 일치하는 최대 길이를 기록해야 한다.

 

패턴 "ABABCABAB" 를 예시로 들어보자

 

1. 패턴의 첫 글자부터 시작해서 하나씩 진행한다.

 

2. 첫 번째 글자 'A'

패턴	A	B	A	B	C	A	B	A	B
LPS	0

 

접두사와 접미사가 없으므로 LPS 값은 0이다.

 

3. 두 번째 글자 'B'

 

패턴	A	B	A	B	C	A	B	A	B
LPS	0	0

 

접두사와 접미사가 없으므로 LPS 값은 0이다.

 

4. 세 번째 글자 'A'

 

패턴	A	B	A	B	C	A	B	A	B
LPS	0	0	1

 

접두사 'A'와 접미사 'A' 가 일치하므로 LPS 값은 1이다.

 

5.  네 번째 글자 'B'

 

패턴	A	B	A	B	C	A	B	A	B
LPS	0	0	1	2

 

접두사 'AB'와 접미사 'AB'가 일치하므로 LPS 값은 2이다.

 

 

6. 다섯 번째 글자 'C'

 

패턴	A	B	A	B	C	A	B	A	B
LPS	0	0	1	2	0

 

접두사와 접미사가 일치하지 않으므로 LPS 값은 0이다.

 

이런식으로 LPS 테이블을 채우면

 

패턴	A	B	A	B	C	A	B	A	B
LPS	0	0	1	2	0	1	2	3	4

 

이런 배열을 얻을 수 있다.

 

이를 통해 패턴이 일치하지 않는 경우에도 이미 일치한 부분을 활용하여 불필요한 비교를 줄일 수 있다.

 

패턴과 텍스트 비교

 

텍스트의 각 위치에서 패턴을 비교하되, 일치하지 않는 경우 LPS 테이블을 활용해 불필요한 비교를 건너뛴다.

 

예를 들어, 텍스트(T)가 ABABDABACDABABCABAB 이고 패턴(P)이 ABABCABAB 일 때, 다음과 같은 과정으로 비교한다.

 

1. 텍스트의 처음부터 패턴을 비교하기 시작한다.
2. 일치하지 않는 위치에서, 패턴의 일치된 부분을 이용해 LPS 테이블을 참조한다.
3. 얻은 값만큼 패턴을 뒤로 밀어준다.

 

 

패턴의 P[3]까지는 일치하지만 P[4]부터 불일치가 발생한다.

 

현재 탐색하고 있는 문자의 위치는 4, 여기서 LPS[3] 을 빼주면 KMP 알고리즘의 아이디어대로 접두사, 접미사가 일치하는 다음 탐색 위치를 한 번에 얻을 수 있게 된다.

 

그러므로 4 - 2 = 2 만큼 패턴을 뒤로 밀어준다.

 

패턴의 P[1]까지는 일치하지만 P[2]부터 불일치가 발생한다.

 

현재 탐색하고 있는 문자의 위치는 4, 여기서 P[1]를 빼주면 4 - 0 = 4를 다음 탐색 위치로 지정한다. 

 

 

일치하는 부분이 없을 경우에는 한 칸 뒤로 밀어준다. 다음 탐색위치는 5가 된다. 

 

 

이번에는 텍스트의 8번째 문자, P[3]에서 불일치가 발생했다. 

 

8 - 1 = 7을 다음 탐색 위치로 지정한다.

 

 

 

 

이런식으로

 

현재 탐색하고 있는 문자의 위치 - 마지막으로 일치한 패턴의 LPS 값 = 다음 탐색 시작 위치

 

식을 사용하여 일치하는 문자열을 찾아가면 된다.

 

 

 

이렇게 8번만에 일치 문자열을 찾았다. 가장 끝에 있어 브루트포스 방법의 경우 11개의 문자열 비교를 했어야 했는데 KMP를 이용하여 비교 횟수를 현저하게 줄일 수 있었다. 

 

이는 문자열을 한 번만 읽고 탐색하는 것과 같은 시간복잡도 이므로 이론상으로 가장 빠른 문자열 탐색 알고리즘이다.

 

 

 

 

 

 

 

 

https://cano721.tistory.com/21

[알고리즘 개념] KMP - 문자열 검색 알고리즘(JAVA 코드)

https://injae-kim.github.io/dev/2020/07/23/all-about-kmp-algorithm.html