KMP 알고리즘 (Knuth Morris Pratt)

문자열 탐색

뉴스 페이지 문자열 찾기

많은 사람들이 업무를 하기 위해 문서를 볼 때 원하는 부분을 빠르게 찾기 위해 문자열 검색이라는 기능을 사용하곤 한다. 보통 Ctrl + F 단축키를 이용하여 현재 보이는 화면내의 수 많은 문자 중에서 원하는 문자열을 찾는다. 일상 속에서 자연스럽게 사용하고 있는 기능이지만, 수 많은 문자중에 원하는 문자열을 빠르게 찾기까지 알고리즘이 존재한다. 

Brute Force

먼저, 단순하게 생각해보자.

위 처럼 "SON IS BEST PLAYER"라는 텍스트가 존재하고 우리는 "BEST"라는 문자열 패턴을 찾아보자.

 

Brute Force 방식에서는 막연하게 모든 텍스트를 지나가면서 패턴과 해당 위치의 텍스트를 비교한다.

텍스트 인덱스 0과 문자열 패턴인텍스 0을 먼저 비교한다. S와 O는 서로 다른 문자이기 때문에 비교 결과 False를 반환한다. 해당 인덱스의 문자가 서로 같지 않다면 이후의 문자열이 모두 같다고 하더라도 패턴과는 일치하지 않기 때문에 오른쪽으로 한 칸씩 이동한다.

 

이동 후에 텍스트 인덱스 1과 문자열 패턴 인덱스 0의 문자를 비교한다. O와 O는 서로 다른 문자이기 때문에 비교 결과가 True가 될 것이다. 만약 일치하는 인덱스가 있다면 인덱스를 하나씩 증가시켜 비교를 실시한다. 

텍스트 인덱스 2와 문자열 패턴 인덱스 1의 문자를 비교한다.  두 문자는 동일하여 또 비교 결과 True를 반환한다.

 

한 번더 인덱스를 증가시켜 문자열을 비교하면 공백과 E로 서로 다른 문자로 비교 결과 False를 반환한다.

결국 문자열 패턴과 일치하지 않음을 판단한 뒤에는 우측으로 한 칸 이동하고  문자열 패턴 인덱스 0부터 다시 비교를 수행한다. 

이러한 방식을 반복하며 문자열 패턴과 완전히 일치하는 인덱스를 찾을 때까지 반복한다.

성능

Brute Force 방식으로 문자열 탐색 기능을 구현한다면 성능은 어떨까?

알고리즘을 수행하고자 하는 텍스트의 길이가 n이고 문자열 패턴의 길이가 m이라고 할 때, 텍스트를 n번 순회하고 1회 순회할 때마다 m번 검증을 하게 된다. 따라서 O(nm) 의 성능을 갖게 된다.

KMP (Knuth Morris Prett)

알고리즘은 기능엔 문제가 없고 성능이 보다 우수할 때 기존 알고리즘을 대체할 수 있다.

KMP 알고리즘의 경우도 마찬가지이다. 성능이 O(n + m)으로 Brute Force 구현 방식보다 우수하다.

 

그렇다면 KMP 알고리즘은 어떤 방식으로 구현될까?

Brute Force 방식과의 기본적인 차이점은 비교 검증을 하지 않아도 되는 부분을 넘기어 수행 속도를 단축한다는 것이다.

 

 

AAAAAAAB라는 텍스트에서 AAAAB라는 패턴을 찾는다고 가정을 하자.

처음 4글자에 대해서는 일치하다고 판단을 하고 마지막 글자에서 패턴과 불일치한다고 판단할 수 있다. 이 비교 검증 단계에서 AAAA가 연속적으로 일치한다는 정보에 대해 다음 단계의 검증에서 넘길 수 있다면 성능을 향상할 수 있다는 것이다.

 

바로 이와 같은 아이디어에서 KMP 알고리즘은 구상되었다.

Prefix Function

비교 검증을 하지 않아도 되는 부분은 입력받은 문자열 패턴에서 미리 정의해놓고 탐색 검증을 수행한다. 이 때 Prefix 함수를 이용한다. 아래에 제시된 함수의 설명에 있어서 j는 0부터 i는 1부터 인덱싱을 시작한다. 예시를 설명하기 전에 보다 이해하기 쉬운 설명을 위해 아래와 같이 의미를 정의하고 시작하도록 하자.

• index가 j인 Pattern내 Character 값 : J문자
• index가 i인 Pattern내 Character 값 : I문자
• index가 j인 Value내 int 값 : J값
• index가 i인 Value내 int 값 : I값

먼저, J문자와 I문자를 비교하여 서로 같음을 확인한다.

문자가 서로 같을 경우에 I값에는 j+1의 값이 할당되고 j와 i는 하나씩 증가한다.

그 다음 단계에서는 J문자와 I문자를 비교하고 이전 단계와 마찬가지로 I값에는 j+1인 2가 할당되고 j와 i는 하나씩 증가한다.

이번 단계에서는 J문자와 I문자가 서로 다르다. 비교 결과가 서로 다를 때에는 두 가지 경우로 나뉘는데, j가 0보다 클 경우와 그렇지 않을 경우로 나뉜다. j는 값이 서로 같을 경우에만 증가하는데 j가 0보다 크다는 것은 이미 이전 반복 패턴이 존재했다는 것을 유추할 수 있다. 위의 표도 이전 반복 패턴이 존재한다. 이럴 때 j는 J-1값으로 인덱스가 변경된다. 현재 j가 2이고 J-1값인 1로 j를 이동한다.

 

이번 단계에서도 이전 단계와 같이 값에 대한 비교 결과가 다르고 j가 0보다 크므로 J-1값인 0으로 이동한다.

해당 경우에는 J값과 I값은 다르지만 j값이 0보다 크지 않다. 이럴 경우에는 i값을 증가하여 다음 비교를 수행한다.

모든 과정이 끝난 이후에 PrefixFunction의 결과를 확인할 수 있다.

KMP 알고리즘 구현

Prefix에 대한 정보를 얻었다면 본격적으로 KMP 알고리즘을 구현할 차례이다. abcdabcdabee라는 텍스트가 있고 abcdabe 라는 패턴이 있다고 하자. KMP 알고리즘은 먼저 abcdabe라는 패턴의 Prefix 정보를 구한다.

 

본격적인 KMP 알고리즘의 순서는 아래와 같다. 먼저 Brute Force  방식처럼 문자열비교를 시작한다.

문자 비교 결과가 다르다고 나타날때 KMP 알고리즘만의 특정이 발생한다.

이해를 돕기 위해 Text내 기준 문자의 index를 i, Pattern내 기준 문자의 index를 j라 할 때, Text[i]와 Pattern[j]가 서로 다르다. 이미 앞선 Pattern 문자들과 일치함을 보였다.(j > 0) 이제 Prefix 정보가 등장한다. Prifix[j-1](Prefix[5])값으로 j를 치환해준다. 

j가 2로 치환되고 Text[i](Text[6])와 Pattern[j](Pattern[2])간의 비교부터 진행하게 된다.

이렇게 Prefix 정보를 추출하여 Brute Force 방식보다 적은 횟수로 매칭된 문자열을 탐색할 수 있게 된다.

github

아래 프로젝트를 실행시키면 알고리즘 진행 단계별로 확인할 수 있다.

 

 

GitHub - jaywapp/Jaywapp.Algorithm.KMP: Example for KMP algorithm