[String Matching] KMP Algorithm ( 1 )

KMP 알고리즘을 확장 구현하고, 각 패턴에 따라서 탐색하고 패턴이 발생한 모든 위치를 찾을 수 있는지 확인. 
KMP 알고리즘의 동작에 대한 분석과 직접 구현한 코드에 대한 설명, 패턴에 따른 탐색의 분석이 포함됨. 

String Matching Algorithm

스트링 처리 알고리즘

어떤 단어나 문장이 문서의 어느 곳에 있는지 찾고 싶을 때, 이때 대상 문서를 Text라 하고, 찾으려는 단어나 문장을 Pattern이라고 한다. 그리고 주어진 텍스트에서 패턴이 어디에 있는지 알아내는 것을 스트링 매칭( String Matching ) 이라고 한다. 텍스트 스트링이 컴퓨터에 저장될 때는 이진 스트링으로 변환되어 저장된다. 스트링에서는 알파벳에 속하는 문자들만 나타날 수 있다. 

스트링 탐색 알고리즘에서 길이 N 인 텍스트를 배열 t[N]이라 하고, 길이 M인 패턴을 배열 p[M]이라 한다면, 스트링 탐색이란 주어진 텍스트 t[N]에서 주어진 패턴 p[M]과 일치하는 모든 부분을 찾는 문제이다. 스트링 탐색 알고리즘의 목표는 잘못된 시작 횟수와 길이를 최대한 줄이는 것이다. 

스트링 탐색 알고리즘에서 직선적 알고리즘은 한 비트씩 오른쪽으로 진행하면서 텍스트의 처음부터 끝까지 모두 비교하여 탐색하는 알고리즘이다. 이 알고리즘은 불일치가 발생했을 때도 비효율적으로 패턴이 이동하므로, 이를 개선시킨 것이 KMP 알고리즘이다. 

 

KMP Algorithm _ Knuth Morris Pratt 알고리즘

불일치가 발생한 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞부분에 대해서는 다시 비교하지 않고 효율적으로 패턴을 이동시켜 텍스트와 비교하여 패턴과 일치하는 텍스트부분의 탐색을 수행하는 알고리즘이다. KMP 알고리즘에서는 불일치가 발생했을 경우 다음으로 이동하는 위치를 next[M] ( M : pattern size ) 배열에 저장하여 잘못된 시작의 발생을 최소화 시킨다. 위의 next 배열은 initNext() 라는 함수 로부터 얻어온다. Next 배열을 구하게 되면 텍스트의 앞으로 돌아갈 필요 없이 next배열에 저장된 위치를 이용하여 그 위치부터 다시 패턴 매칭을 계속 수행하게 된다. 

이해를 하기 위해 next배열을 구하는 동작 과정을 나타내었다. 

위에서 구한 next 배열을 이용하여 KMP 알고리즘의 동작 과정을 나타내었다.

KMP 알고리즘은 매칭되지 못했을 때 그 위치에서부터 Next 배열의 위치에 따라서 패턴을 옮긴 후에 다시 비교를 하기 시작한다. 예를 들어 2로 옮긴다는 것은 pattern의 세번째 원소부터 비교를 한다는 뜻이다.  

위의 initNext()함수로 구한 유한 상태 장치를 보면, 자기 앞 패턴이 어디 까지 일치하는지 를 알려주는 장치이다. 배열의 5번째 값을 보면 2이다. 이는 자신 앞의 패턴들이 전체 패턴의 2번째 까지 일치하므로 2번째까지의 검사는 동일하므로 그 다음부터 매칭검사를 하게끔 3번째부터 검사하라는 인덱스 2의 값을 저장한 것이다. 마찬가지로 배열의 4번째 값을 보면 1이다. 이는 자신 앞의 패턴들이 전체 패턴의 1번째 까지 일치하므로 2번째부터 검사하라는 인덱스의 1값을 저장한 것이다.  하지만 이 유한 상태 장치의 문제를 보면, 불일치가 발생했을 경우 다시 위치를 이동하여 재검사를 했는데 또다시 불일치가 일어나는 경우이다. 즉 불일치 전이의 이동 전후에 있는 문자가 동일한 경우 비교를 여러 번 하게 된다. 이는 불필요한 작업이며, 처음부터 패턴의 시작점으로 이동하게 하는 것이 효율적이다. 

따라서 이 유한 상태 장치를 개선하기 위해 initNext()함수를 변경하고, 동작과정을 다시 나타내었다.

위에서 구한 next 배열을 이용하여 KMP 알고리즘의 동작 과정을 나타내었다.

위의 결과로 알 수 있듯이, 개선된 유한 상태 장치를 사용하여 KMP 알고리즘을 수행하면, 탐색에 드는 횟수가 줄어들고, 최종적으로 탐색에 걸리는 시간도 줄어들게 된다. 이는 같은 문자에 대해 처음부터 패턴의 시작점으로 돌아가게 if문을 사용하여 패턴이 같을 경우 보다 이전에 있는 같은 문자의 위치를 따라가게 하는 것이다. 따라서 이번 과제에서는 개선된 유한상태장치를 사용하여 KMP 알고리즘을 구현하였다. 

 

KMP 알고리즘에서 겹쳐진 패턴도 탐색할 수 있게 수정

책과 강의 시간, 실습 시간 에 배운 KMP함수는 주어진 텍스트에서 패턴을 찾았을 때, 그 위치를 return 하게 끔 되어있다. 그리고 메인함수에서 while(1)문으로 KMP를 반복 실행하는데, 이 때, 패턴을 한번 찾았을 때 찾은 위치의 다음으로 비트를 옮겨서 매칭을 하기 시작한다. 이를 응용하여 KMP 함수 안에서 패턴이 매칭되었을 때의 위치를 새로운 배열에 저장하였다. 자세한 수정 사항은 아래에 코드 설명에 기술해 놓았다. 매칭된 위치를 저장하는 새로운 배열을 선언하기 때문에 공간이 낭비된다.