String Matching

Pattern matching algorithms (=string matching algorithm)

- Brute-force (=Naive)

- Knuth-Morris-Pratt (KMP)

- Boyer-Moore (BM)

 * KMP와 Boyer는 pattern을 전처리(preprocessing)한다.

 - text: 긴 문자열, pattern: 짧은 문자열

 

Strings

- string은 0개 이상 char의 나열. 0개면 empty string

- P를 길이 m인 string이라 하면,

- substring P[i..j]: i와 j 사이의 임의의 연속된 char들의 나열

- prefix (접두사): P[0..i]인 substring

- suffix (접미사): P[i...m-1]인 substring

- pattern matching 문제는 string T(text)의 substring 중 P(pattern)와 같은 substring을 찾는 것

 

Brute-Force Algorithm

- match를 찾거나, pattern의 모든 placement를 시도할 때까지 비교한다. (한 칸씩 shift)

- O(nm)

- 최악의 경우, T=aaa...ah, P=aaah. DNA sequence에서 발생할 수 있고, 일반 영어에선 거의x-> O(n)에 가까움

 

KMP Algorithm

- mismatch가 일어났을 때, 중복비교를 피하기 위해 failure function의 값만큼 shift

- failure function F(j)는 P[0..j]의 prefix이자 P[1..j]의 suffix인 가장 긴 길이

-> ex) 패턴이 abaaba일 때

- F(0): a 중에 겹치는거 -> 0

- F(1): ab 중에 앞뒤 겹치는거 -> 0

- F(2): aba -> a 하나 있음. 1

- F(3): abaa -> a 하나 있음. 1

- F(4): abaab -> ab. 2

- F(5): abaaba -> aba. 3

- mismatch가 발생하면 (P[i] != T[i]), j를 F(j-1)로 업데이트

- KMP 알고리즘의 failure function은 O(m) 시간에 계산되는 array. (m은 p의 길이, n은 T의 길이)

- KMP 알고리즘은 O(m+n) 시간.

 

Boyer-Moore Heuristics

- 두 가지 heuristic(local 최적해를 빠르게 계산하는 알고리즘)에 기반한다.

1. Looking-glass heuristic (거꾸로의): T의 substring과 P를 거꾸로 계산한다.

2. Character-jump heuristic (bad-character “): T[i] = c 에서 mismatch가 발생하면,

- P가 c를 포함하면, P에서 c가 나타나는 마지막 위치와 T[i]를 맞춘다.

- 포함하지 않으면, P[0]와 T[i+1]을 맞춘다.

 

Last-Occurence Function

- 각 char들의 마지막 등장 인덱스.

- O(m+s) 시간에 계산 가능. (m: P의 size, s: 시그마의 사이즈. 시그마: 원소들의 집합(중복x))

 

- 분석

- 시간: O(nm+s)       // n: |T|, m: |P|, s: 집합 원소 개수

- preprocessing: O(m+s)

- searching: O(nm)

 -> O(nm+s)

- worst case 예시:

- T = aaa ... a

- P = baaa

- worst case는 DNA sequence처럼 집합 사이즈 작을 때 일어날 수 있음. 실제 영어에선 잘 발생x (mismatch가 잘 일어나기 때문)

- Eng text일 때 Boyer-Moore가 Brute-force보다 훨씬 빠름.

- worst는 Boyer가 KMP보다 나쁘지만 영어 text에선 보통 유리하다.