주어진 text에서 주어진 특정 pattern이 존재하는지, 필요시 몇번 등장하는지를 알 수 있는 알고리즘들을 말한다.
Brute-force의 발상을 따르면, 텍스트의 1번 string부터 시작하여 패턴과 일치하는지 일일히 비교하는 방법을 쓸 수 있다. 이 경우, 패턴의 길이가 m, text의 길이가 n이면 시간복잡도는 O(mn)이 필요하다.
이보다 조금 더 발전한 알고리즘은 Boyer-Moore, Knuth-Morris-Pratt, Rabin-Karp등 다양하나, 이 글에서는 Boyer-Moore, Knuth-Morris-Pratt 알고리즘을 다룰 것이다.
Brute-Force에 기반한 알고리즘은 text의 1번 string부터 끝에 이르기까지 하나하나 전부 탐색한다. 하지만, pattern과 text의 1번 string이 일치하지 않는다면, 이후의 몇몇 string은 통째로 건너뛰어도 되는 경우가 많다.
Boyer-Moore는 불일치가 발생했을 경우, 얼마나 건너뛰어도 되는지를 계산하여 건너뛰는 것을 통해 시간복잡도를 일부 개선하려는 시도를 한 알고리즘이다.
우선, pattern에 있는 문자가 마지막으로 나타난 것이 몇번째 index이었는지 확인할 수 있는 HashMap을 만든다. 이를 Last occurance table이라고 한다. 예를 들어, pattern으로 테이블을 만들 경우, <p, 0> <a, 1> <t, 3>, <e, 4> <r, 5> <n, 6>이 기본이고, 존재하지 않는 문자는 <*, -1>로 만든다. Pseudo code는 다음과 같다.
LOT(pattern)
m = pattern.length
last = HashMap<character, index>
for 0~m-1
last = put(pattern[i], i)
return last
이때 HashMap에서는 패턴에 존재하는 문자면 index를 반환하고, 존재하지 않는 문자면 -1을 반환하도록 method를 짜주어야 한다.
이 상태에서, pattern의 뒷부분부터 text와 비교한다. 일치하면 계속 비교하지만, 불일치가 발생할 경우, 불일치가 발생한 text의 문자를 LOT에 넣어 반환값을 확인한다. 반환 값이 -1이면은 완전 불일치이므로, 문자를 기준으로 pattern을 통째로 건너뛰어 다시 비교한다. 반환값이 -1이 아니면, 반환된 숫자를 index로 하여, pattern의 해당 index로 이동하여 다시 비교한다.
BoyerMoore(text, pattern)
last = LOT(pattern)
i = 0
while i <= text.length - pattern.length
j = pattern.length - 1
while j >= 0 && text[i+j] = pattern[i]
j = j-1
if j = -1
return i //pattern found
else
shift = last[text[i+j]]
if shift < j
i = i+j-shift
else
i = i + 1
return pattern not found
위의 code에서, 패턴을 찾았을 경우 return을 바로하는 것이 아니라, array, 혹은 그 외의 자료구조를 따로 선언하고 여기에 i를 add 하도록 한 후, 최종적으로 array를 반환하도록 하면, 패턴이 일치하는 모든 텍스트 index를 얻을 수 있다.
기본적으로 시간복잡도는 O(mn)이지만, 최선의 경우 O(m+(n/m))으로 끝낼 수 있으며, 평균적으로도 brute-force에 비해 나은 성능을 보인다.
이 알고리즘 또한 발상은 Boyer-Moore와 비슷하다. 패턴을 비교하는 과정을 좀 더 개선하는 것이 목표이다.
우선 패턴을 기반으로 failure table을 만들어야 한다. 패턴의 첫 문자를 0으로 하고, 두번째 문자부터 첫번째 문자와 비교를 한다. 이때, 일치하면 1을 부여함과 동시에, 이후의 문자 그 다음 문자와 같으면 2, 그다음과도 같으면 3을 부여한다.
r e v r e v a b c r e v r
0 0 0 1 2 3 0 0 0 1 2 3 4
FailureTable(pattern)
ft[0] = 0
i = 0
j = 1
while j < pattern.length
if pattern[i] = pattern[j]
ft[j] = i + 1
i = i + 1
j = j + 1
else if pattenr[i] != pattern[j] && i = 0
ft[j] = 0
j = j + 1
else
i = ft[i-1]
return ft
KMP(text, pattern, ft)
j = 0
k = 0
while k < text.length
if p[j] = text[k]
if j = pattern.length - 1
return k // pattern match
else
j = j + 1
k = k + 1
else if p[j] != text[k] && j = 0
k = k + 1
else
j = ft[j - 1]
이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.