coolx.net

Programming

No.

505

Name.

swindler

Subject.

The Knuth-Morris-Pratt Algorithm

Main Cate.

개발일반

Sub Cate.

Date.

2008-12-04 10:16

Hit.

4309 (210.182.190.136)

File.

kmp.gif

: Brute-Force와 BM 알고리즘에서는, match가 실패하면, 그 전에 compare 했던 information을 다 버리고 from scratch로 알고리즘을 수행했다. 그러나 KMP 알고리즘에서는 전에 비교했던 정보를 다 이용하여, O(n+m)의 수행시간을 갖는다. 이것은, worst case에 text와 pattern 전 체를 최소 한 번 읽어들인다는 것이다. 그래서 left-to-right로 pattern을 text와 비교하지만, shift를 더 지능적으로 하기 때문에 Brute-Force 알고리즘 보다는 훨씬 효율적이다. (어떤 경우에서는 BM 보다 못하기 때문에, BM 보다 효율적이라 말할 수는 없다. )

KMP 알고리즘의 핵심은, Failure Function이다. f(j)는 P[1..j]의 suffix인 가장 긴 P의 prefix 길이이다. (convention으로, f(0) = 0 ) 이 Failure Function은 pattern 내에서 repeated substring을 "encodes" 해주기 때문에 매우 중요하다.

Knity-Morris-Pratt pattern matching

i never goes back!

(*) Performance 증명
failure function 계산시간 제외하면, KMP의 running time은 while-loop의 iteration 수에 비례한다. 분석을 위해서 k (= i-j)를 두어 T에서 pattern P가 shift된 total amount 라 하면, k<=n임을 알 수 있다. loop 실행중에는 다음 세 가지 경우 중 하나이다.
case 1: T[i] = P[j] -> i++, k는 그대로 (j++ 이므로)
case 2: T[i] =/= P[j] AND j>0 -> i는 그대로, k는 최대 1증가 (k가 i-j에서 i-f(j-1)이 되고, f(j-1) < j 이기 때문)
case 3: T[i] =/= P[j] AND j = 0 -> i++, k++ (j가 그대로임)
따라서, KMP에서 while-loop의 총 실행 수는 최대 2n 이다.

(*) KMP Failure Function 만들기
여기에 사용된 알고리즘은, KMPMatch 알고리즘과 비슷한, "bootstrapping" 프로세스이다. else if j>0 then 부분에서, f(j-1)을 사용하고 있는데, i>j 이기 때문에 f(j-1)은 항상 정의되어있다.

전체적으로, KMP 알고리즘의 running time = O(n+m) 이다.
(s에 영향을 받지 않는다. )

[바로가기 링크] : http://coolx.net/cboard/develop/505


[Modify] [Delete]		[Reply] [List]