1. Strings and Pattern Matching Algorithms
T : text (길이 n)
P : pattern (길이 m)
1) Brute Force Pattern Matching
: 가장 기초적인 방법. text의 처음부터 끝까지 alphabet 하나씩 옮겨가며 비교. 따라서, TC 는 O( (n-m+1)m ) = O(nm) => O(n^2)
2) The Boyer-Moore Algorithm
: P와 sizable fraction of T의 비교를 줄여준다.
Brute-Force 알고리즘은 unbounded alphabet에서도 사용 가능하지만, BM 알고리즘은 finite size에서만 가능하다.
=> alphabet이 moderately sized하고 pattern이 상대적으로 길 때 가장 빠르다.
(*) Two heuristics
1. Looking-Glass Heuristic : P의 제일 뒤부터 compare한다.
2. Character-Jump Heuristic : mismatch 일어나면 (T[i] = c),
pattern에서 'c' 포함하면 (역시 backward로 검사) 거기까지 pattern shifting,
pattern에 'c'가 없으면 그 다음까지 pattern 모~두 shifting
=> last occurrence function 만들어 사용.
(*) Last-Occurrence Function
L(c) = P[i]의 가장 큰 인덱스 i (pattern에 포함 안되면 -1)
Pattern을 뒤에서 앞으로 한 번 scan해야하고,
alphabet 전체도 한 번 scan해야하므로 (-1인 것 찾기)
last-Occurrence Function의 TC = O(m+s) // s는 alphabet size
(case1 은 last occurrence가 j를 pass 한 경우 그냥 한 칸만 shift 하는 것이다.)
worst-case : T = aaaa.....a, P = baaa....a 일 때.
O(nm + s) 가 된다. 거의, Brute-Force 알고리즘이랑 막상막하
그러나, English text와 같은 text에서는 skip이 많이 일어나서 효과적이다. experimental evidence로, 5 문자 pattern string에서는 비교가 0.24번 일어났다.
그리고, 이 것은 simplified된 BM 알고리즘이고, 실제는 다른 shift heuristic(KMP에서 아이디어)을 사용하여, running time은 O(n+m+s)이다.
3) The Knuth-Morris-Pratt Algorithm
: 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" 해주기 때문에 매우 중요하다.
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에 영향을 받지 않는다. )
T : text (길이 n)
P : pattern (길이 m)
1) Brute Force Pattern Matching
: 가장 기초적인 방법. text의 처음부터 끝까지 alphabet 하나씩 옮겨가며 비교. 따라서, TC 는 O( (n-m+1)m ) = O(nm) => O(n^2)
Brute-force pattern matching
2) The Boyer-Moore Algorithm
: P와 sizable fraction of T의 비교를 줄여준다.
Brute-Force 알고리즘은 unbounded alphabet에서도 사용 가능하지만, BM 알고리즘은 finite size에서만 가능하다.
=> alphabet이 moderately sized하고 pattern이 상대적으로 길 때 가장 빠르다.
(*) Two heuristics
1. Looking-Glass Heuristic : P의 제일 뒤부터 compare한다.
2. Character-Jump Heuristic : mismatch 일어나면 (T[i] = c),
pattern에서 'c' 포함하면 (역시 backward로 검사) 거기까지 pattern shifting,
pattern에 'c'가 없으면 그 다음까지 pattern 모~두 shifting
=> last occurrence function 만들어 사용.
(*) Last-Occurrence Function
L(c) = P[i]의 가장 큰 인덱스 i (pattern에 포함 안되면 -1)
Pattern을 뒤에서 앞으로 한 번 scan해야하고,
alphabet 전체도 한 번 scan해야하므로 (-1인 것 찾기)
last-Occurrence Function의 TC = O(m+s) // s는 alphabet size
Boyer-Moore pattern matching
worst-case : T = aaaa.....a, P = baaa....a 일 때.
O(nm + s) 가 된다. 거의, Brute-Force 알고리즘이랑 막상막하
그러나, English text와 같은 text에서는 skip이 많이 일어나서 효과적이다. experimental evidence로, 5 문자 pattern string에서는 비교가 0.24번 일어났다.
그리고, 이 것은 simplified된 BM 알고리즘이고, 실제는 다른 shift heuristic(KMP에서 아이디어)을 사용하여, running time은 O(n+m+s)이다.
3) The Knuth-Morris-Pratt Algorithm
: 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
(*) 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에 영향을 받지 않는다. )
