L14 - KMP Algorithm

 

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한
 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다

 

 

String Matching

 

문서에서 단어를 빠르게 찾으려면?

 

 

문서에서 특정 단어를 검색해서 찾는 경우가 종종 있을텐데

 

이때 찾으려는 단어를 pattern이라 함

 

이렇게 문서에서 단어를 찾을 때 빠르게 찾으려면 어떤 방법을 써야할지에 대한 알고리즘임

 

Problem Definition

 

 

 

입력은 길이 n인 문서 문자열 A, 길이 m인 패턴 문자열 P 가 주어지고 보통 n이 m보다 훨씬 큰 상황임

 

이때 출력은 패턴 문자열과 일치하는 A의 부분 문자열(sub-string) 위치를 출력하게됨

 

Naive Algorithm

 

문서 A의 모든 부분 문자열을 순차적으로 패턴 P에 매치해보는 알고리즘을 생각해볼 수 있음

 

Pseudo Code를 보면

 

 

시간복잡도가 O(mn)임

 

• O(n)회 반복 (정확히는 n - m + 1 만큼)
  
  
• 각 반복마다 O(m) 번의 문자 비교

 

문서에서 단어를 O(mn)보다 빠르게 찾기 위해서는 KMP Algorithm을 적용해볼 수 있음

 

KMP Algorithm

 

탐색 알고리즘

 

 

 

KMP 알고리즘의 기본 아이디어는 패턴의 중복 부분을 재사용하여 중복 매칭을 건너뛰는 것임

 

중복 매칭을 어떻게 건너뛸 수 있을까?

 

 

복구위치 배열 π를 활용함

 

=> 문자 매칭에 실패했을 때, 매칭을 재시작할 위치 표시

 

만약 위 그림에서 w가 일치하지 않았으면 해당 π 배열에 적힌 3번 index (알파벳 d)를 현재 w가 비교한 자리에서 탐색을 다시 시작하면 된다는 의미임

 

 

우선 그림으로 4가지 경우를 살펴보면 이해가 쉬움

 

문서 A에서 P="abdabwz" 찾기

 

우선 각각 문서와 패턴의 첫 시작 인덱스에 포인터 i, j를 위치시키고 시작하면됨

 

1번 상황

 

i가 가리키던 x와 j가 가리키던 a가 다르고 j가 0의 값에 위치해있으면 i를 하나 증가 시킴
(문서 A의 다음 문자열을 살펴봄)

 

2번 상황

 

i가 가리키던 a와 j가 가리키던 a가 일치하므로 i와 j를 모두 1씩 증가시켜 다음 문자를 살펴봄

 

=> 위 그림에서는 abdab까지 일치할 것을 생각해볼 수 있음

 

3번 상황

 

 

여기서부터 π배열이 사용되는데 

 

pseudo code를 보면 알 수 있듯이 i가 가리키는 'd' 와 j가 가리키는 'w'의 문자가 일치하지 않으므로 j가 가리키는 곳이 0번인지 확인해봄

 

위 상황에서는 j가 5번째 인덱스를 가리키고 있으므로 π배열의 해당 인덱스에 적힌 2번 인덱스 (문자 d)로 j를 옮겨 현재 i가 가리키는 위치와 비교함

 

=> 일치하므로 i와 j가 각각 1씩 증가할 것임
(다시 탐색이 시작된 것을 알 수 있음)

 

4번 상황

 

 

i가 가리키던 문자 d와 j가 가리키던 문자 a가 일치하지 않아 해당 인덱스의 π배열을 따라 0번째 인덱스 (문자 a)로 이동하여 현재 i가 가리키는 문자 d와 비교

 

이 때 이것도 일치하지 않는데 j가 0번 인덱스를 가리키므로 i를 1 증가시킴

 

 

매치 성공 후 상황

 

이렇게 계속 탐색하면 j가 p의 길이와 동일해지는 인덱스를 가리키는 상황이 오게되는데

 

이러면 매치가 성공한 것으로 간주하고 j를 다시 초기화 시켜 다음 매치를 탐색함

 

생각해볼점

 

String Match를 할 때 2가지 경우를 생각해볼 수 있음

 

 

위와 같은 문서 A와 P가 주어지면 2개를 return 할지 4개를 return 할지임

 

일단 위의 KMP 알고리즘은 1번의 경우처럼 2개를 return하는 코드임

(매치 성공 후 j만 초기화 하고 다시 탐색을 시작하므로)

 

밑에처럼 4개를 return하는 상황처럼 구현하고 싶다면

 

π배열에 탐색이 끝났을 때 다시 탐색을 시작할 값을 미리 설정해놓아야함

 

=> j가 P의 길이가 되었을 때 중간에 다시 탐색을 시작할 값으로 갈 수 있게

 

Complexity Analysis

 

pseudo code

 

 

매 반복마다 i와 j의 변화를 관찰하여 증명할 수 있음

 

위에서 다뤘던 4가지 상황들을 살펴봤을 때 

 

• i와 j가 동시에 1 증가함
  
  
• i는 1 증가하고 j는 0이됨
  
  
• i만 1 증가함
  
  
• j가 π[j]로 감소함

인데

 

i + (i - j)는 최소한 1씩 증가함

i + (i - j)에서 j는 양수이므로 <= 2i 일테고 pseudo code에서 봤듯이 while문의 조건 i < n이 있으므로

 

i + (i - j) <= 2i <= 2n 이 됨

 

=> 즉, i + (i - j) 가 1에서 시작하여 최소 1씩 증가하며 2n이 되기전에 반복문을 종료함

O(2n) = O(n)

 

결국 시간복잡도는 연산의 횟수인데

i + (i - j)는 각 연산마다 최소한 1씩 증가하므로 시간복잡도를 구하는 지표로 사용할 수 있음

 

π 배열 생성 알고리즘

 

그럼 π배열은 어떻게 구할까?

 

 

 

 

 

 

π배열은 LPS 길이 배열을 한 칸 옮긴 것과 동일함

=> Longest Prefix Suffix (LPS)란 처음과 마지막이 겹치는 (동일한) 부분을 의미

 

 

pseudo code와 함께 π배열을 구하는 과정을 살펴보면

 

실제로는 P배열 하나에서 2개의 포인터로 진행되는 과정임

 

 

우선 시작할 때 i의 인덱스는 1부터 진행을함

=> 0번째가 일치하지 않으면 어쩌피 탐색하는 코드에서 조건에 걸리므로 따로 어디로 갈지 결정할 필요가 없이 바로 0을 넣음

(또, 0번째 부터 시작하면 패턴에서 패턴을 찾아버리는 꼴이 되버림...)

 

이렇게 초기 세팅을 마쳤으면

LPS의 길이 즉, j의 위치를 해당 π배열이 인덱스 위치에 적어주면 됨

 

1번 상황

 

 

i가 가리키던 P의 1번 인덱스 문자 a와 j가 가리키던 0번 인덱스 문자 a가 일치하므로 j와 i모두 증가시키고

 

j의 인덱스 위치를 i가 가리키는 인덱스로 π배열에 값을 넣어줌

 

2번 상황

 

i가 가리키는 문자 b와 j가 가리키던 인덱스 1번 문자 a가 다르므로

π배열에 따라 0번으로 이동해서 다시 확인해보고 또 다르므로 코드에 의해 i를 하나 증가시킬 것임

 

 

이런식으로 반복되며 진행됨

 

생각해볼점

 

pseudo code

 

아까 String Match를 어떻게 할지에 대해 2가지를 이야기했었는데

 

현재 포스팅하는 kmp 알고리즘은 위의 내용중 1번 방식에 해당하는 String Match를 진행한다고 했었음

 

만약 2번 방식으로 String Match 하는 KMP 알고리즘은 π배열에 탐색이 끝났을 때 다시 탐색을 시작할 값을 미리 설정해놓아야 하는데

 

이 때는 π배열 생성할 때 while문의 조건을 i < m - 1이 아니라 i < m으로 해야함!

 

 

왜 이렇게 진행이 되는걸까?

 

 

이해가 어려울 수 있는데 결국 π배열을 생성하는 과정은 LPS의 길이 배열을 한 칸 옮긴거라는 것에 집중하면됨

어쩌피 탐색과정을 살펴봤을 때 π배열에서 0번째 인덱스는 0으로 가는 선택지 밖에 없으므로 포인터 i를 1번 인덱스 부터 시작함

그리고 값을 적을 때는 i를 먼저 1 증가시키고 해당 π배열 자리에 값을 적어줘야 LPS의 길이 배열을 한 칸 옮긴 효과가 나타남

=> 여기서 i는 현재 길이의 배열에서 뒷부분, j는 이전 인덱스들의 길이 즉, 앞부분을 의미하므로 배열에 값을 넣기전에 j 위치를 + 1 시킨게 곧 해당 LPS의 길이가 되는거임

 

Complexity Analysis

 

pseudo code

 

π 배열 생성 시간 복잡도는 O(m) 임

 

=> 앞서 다뤘던 탐색 시간 복잡도와 동일한 방식으로 증명됨

 

따라서 앞서 구했던 탐색 시간 복잡도 O(n)과 더하면

 

KMP의 전체 시간 복잡도는 O(m + n)이 됨