5. KMP 알고리즘

Reference:
- 이것이 자료구조+알고리즘이다 with C언어 / 박상현 / 한빛미디어
- 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님
- https://inuplace.tistory.com/314 / 이누의 개발성장기

KMP 알고리즘

KMP (Knuth-Morris-Pratt) 알고리즘

: '고지식한 탐색' 처럼 탐색 위치를 본문 왼쪽부터 시작해서 오른쪽으로 옮겨가며 문자를 직접 비교하는 방식으로 동작

==> 하지만 요령을 눈곱만큼도 부리지 않는 고지식한 탐색과 달리, KMP 알고리즘은 비교할 필요 없는 부분은 지나치고 비교가 필요한 부분만 비교를 수행하는 똑똑한 알고리즘

==>  '어떤 정보'가 무엇인지와 이 정보를 '어떻게 활용하는가'에 대한 것

---

KMP 알고리즘의 동작 방식

어느 문자열이든 접두부(prefix)와 접미부(suffix)를 갖고 있음

 

접두부

: 문자열의 머리 부분

 

접미부

: 문자열의 꼬리 부분

 

경계

: KMP 알고리즘에서 빈 문자열이나 BAA처럼 문자열에서 일치하는 접두부와 접미부 쌍

*KMP 알고리즘은 이 경계를 활용해서 불필요한 문자 비교를 피한다*

 

 

ex) 가정해보면

본문 : BAABAABAB

패턴 : BAABAB

• 탐색을 시작해보면 본문과 패턴의 0~4번 문자열(BAABA) 까지는 서로 일치
• 그런데 5번 문자에서 불일치가 발생

 

• 불일치가 발생하기 전까지 본문과 일치했던 0~4번 문자열을 살펴본다
• BAABA는 빈 문자열과 BA, 이렇게 2개의 경계를 갖고 있다

 

• 본문 [0...4]와 패턴[0...4]는 서로 일치
• 이것은 곧 두 문자열의 경계가 서로 같다는 뜻
• 본문 [0...4]의 접미부는 패턴[0...4]의 접두부와 동일하다는 의미이기도 함
• 따라서 패턴 전체를 오른쪽으로 쭉 밀어서 패턴의 접두부와 본문[0...4]의 접미부를 일치하게 만들어두면 곧바로 5번부터 비교를 재개할 수 있게 된다.
• 이때 패턴의 탐색 위치 이동 거리는 일치하는 부분 문자열 (BAABA)의 길이 (5)에서 경계 (BA)의 길이 (2)를 뺀 값과 같다

 

• 이것이 고지식한 탐색이었다면 5번째 문자에서 불일치가 발견되더라도 다시 본문의 1번 문자(A)부터 탐색을 수행했을 것이다.
• 하지만 KMP 알고리즘은 사전에 파악해둔 패턴의 경계를 이용해서 1번, 2번 문자를 뛰어넘어 3번 문자부터 탐색을 시작한다
• 따라서 KMP 알고리즘은 본문의 길이가 n일 때 최대 n번만큼만 비교를 수행하면 본문에서 패턴과 일치하는 문자열의 위치를 알아낼 수 있다.

---

경계 정보 사전 계산 방법

KMP 알고리즘이 본문과 패턴을 서로 비교하다가 불일치가 발생할 경우 그 경계가 있는지 살펴보고 그 경계를 이용해서 불필요한 비교를 피해간다는 사실을 알았다

 

하지만

"경계를 찾는 데 소요되는 비용은 공짜가 아닐 텐데?"

 

맞다. 당연히 탐색 중간에 매번 경계를 찾는다면 그 비용은 만만치 않게 늘어난다.

그래서 KMP 알고리즘은 탐색을 수행하기 전에 미리 패턴으로부터 경계의 정보를 가진 테이블을 만든다.

 

ex)

• BAABABAA라는 패턴이 있고 이 패턴으로 탐색을 시도했을 때 첫 번째 문자부터 불일치가 일어난다고 가정해보자
• KMP 알고리즘에서는 불일치가 일어난 위치 이전의 일치 접두부에서 최대 경계를 찾고, 이 경계의 너비를 이용해서 비교할 필요가 없는 탐색 위치를 건너뛴다.
• 그런데 1 번째 문자는 일치 접두부가 아예 존재하지 않는다
• 그래서 1 번째 문자의 경계 너비는 항상 -1이다. 
• 0은 이전 접두부가 존재하지만 경계가 없을 때 경계의 너비로 사용하기 때문에 -1로 시작하는 것이다

 

• 이번에는 1 번째 문자가 일치하지만 2 번째 (인덱스: 1) 문자에서 불일치가 발생한다고 가정해보자
• 불일치가 일어난 2 번째 문자 앞에 있는 일치 접두부는 B 하나뿐이다.
• 따라서 경계가 존재하지 않으므로 일치 접두부의 최대 경계 너비는 0이 된다.
• 3 번째 (인덱스 : 2) 문자는 어떨까?
• 역시 경계가 존재하지 않으므로 경계 너비는 0이다.
• 4 번째 (인덱스: 3) 문자도 마찬가지로 경계 너비가 0이다

 

• 5 번째 (인덱스 : 4) 문자에서 불일치가 발생한 경우 일치 접두부는 BAAB이므로 최대 경계가 B이며 너비는 1이다
• 6 번째 (인덱스 : 5) 문자의 일치 접두부는 BAABA는 최대 경계가 BA로 너비가 2이다.
• 이런식으로 테이블을 완성해나가면 다음과 같은 결과를 얻을 수 있다.

 

• 이제 보니 경계 테이블의  크기가 패턴 크기보다 1만큼 더 크다.
• 테이블의 마지막 칸은 본문 내 문자열이 패턴과 일치하지만 이어서 탐색을 계속하고자 할 때 사용한다
• 예를 들어 패턴 전체와 일치하는 부분을 찾았는데, 그 부분 뒤에 이어지는 본문의 문자가 패턴의 첫 번째 문자와 일치하지 않는 경우 이 경계의 너비값을 사용하게 된다. 그렇다면 마지막 칸을 채워보자
• 일치 접두부는 BAABABAA이고 최대 경계는 BAA로 길이는 3이다.
• 이 값을 기입하면 테이블이 완성된다

 

 

탐색 위치의 이동 거리를 계산하기 위해 경계 테이블을 만들어뒀으니, 불일치가 발생했을 때 탐색 위치의 이동 거리는 다음과 같다

탐색 위치의 이동 거리 = 일치 접두부의 길이 - 최대 경계 너비

 

우리가 만들어둔 경계 테이블을 예로 들면, 본문과 패턴이 0~4번 문자까지는 일치하는데 5번 문자에서 불일치가 발생한 경우 패턴의 이동 거리는 5-2=3이 된다

---

KMP 알고리즘 예제 프로그램