문자열 매칭 알고리즘

A brute-force sub string search 알고리즘

1 function NaiveSearch(string s[1..n], string pattern[1..m])
2    for i from 1 to n-m+1
3       for j from 1 to m
4          if s[i+j-1] ≠ pattern[j]
5             jump to next iteration of outer loop
6       return i
7    return not found

시간 복잡도 : O(mn)

Rabin-Carp 알고리즘

1 function RabinKarp(string s[1..n], string pattern[1..m])
2 hpattern := hash(pattern[1..m]);  hs := hash(s[1..m])
3 for i from 1 to n-m+1
4   if hs = hpattern
5     if s[i..i+m-1] = pattern[1..m]
6       return i
7   hs := hash(s[i+1..i+m])
8 return not found

> 문자열 매칭 알고리즘

> pattern의 hash값을 계산해두고 text에서 pattern의 길이(m)에 해당하는 block의 hash값과 같은지를 판단하여 탐색한다.

단, hash값이 일치한다고 해도 다를수 있으므로 verify 과정이 필요하다.

> rolling hash 개념으로 DP를 사용하여 이전 text[i-1]까지 계산된 hash값을 재활용하기 때문에 전체 계산시간을 줄일 수 있다.

// ASCII a = 97, b = 98, r = 114. 
hash("abr") = (97 × 1012) + (98 × 1011) + (114 × 1010) = 999,509 

멀티 서치를 위해서는 아래와 같다.

 1 function RabinKarpSet(string s[1..n], set of string subs, m):
 2     set hsubs := emptySet
 3     foreach sub in subs
 4         insert hash(sub[1..m]) into hsubs
 5     hs := hash(s[1..m])
 6     for i from 1 to n-m+1
 7         if hs ∈ hsubs and s[i..i+m-1] ∈ subs
 8             return i
 9         hs := hash(s[i+1..i+m])
10     return not found

> k개의 hash 값을 미리 계산하여 hash table에 저장한 뒤 가장 짧은 패턴의 길이인 m이라 하면 pattern[0:m]에 대한 hash값만 계산한다.

> 총 k개의 pattern 탐색을 위한 시간 복잡도는 O(nk)가 아닌 O(n+k)이다.

http://carstart.tistory.com/97

https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

Knuth–Morris–Pratt 알고리즘

> 문자열 매칭 알고리즘

> 오토마타를 이용한 매칭과 동기가 유사함.

> 매칭에 실패했을 때 돌아갈 상태를 준비해두며 오토마타를 이용한 매칭보다 준비 작업이 단순함.

> 시간 복잡도 : O(n)

http://carstart.tistory.com/143

Boyer-Moore 알고리즘

> 패턴의 오른쪽부터 비교한다.
> 최악의 경우 O(mn), 일반적으로 O(n)보다 작다.

Aho-Corasick Algorithm(아호 코라식 알고리즘)

> 트리구조로 검색하는 방식의 문자열 매칭 알고리즘

http://www.slideshare.net/ssuser81b91b/ahocorasick-algorithm