티스토리 뷰

공부

String Matching Algorithms

전명우 2016. 6. 24. 14:07

1) Knuth-Morris-Pratt Algorithm

2) Aho-Corasick Algorithm

1) Knuth-Morris-Pratt Algorithm

KMP Algorithm은 패턴 $P$와 문자열 $S$가 있을 때, 문자열 $S$에 패턴 $P$가 부분문자열로 있는지, 혹은 몇 개 있는지 선형시간 $O(|S| + |P|)$에 확인하는 방법이다.

 

기본적인 아이디어는 실패 함수 f(i)에서 온다. 아래는 패턴 $P$가 "abracadabra" 일 때 실패 함수 값을 표로 나타낸 것이다.

i 1 2 3 4 5 6 7 8 9 10 11
P a b r a c a d a b r a
f 0 0 0 1 0 1 0 1 2 3 4

 

$P[i, j]$를 패턴 $P$의 $i$번째 문자부터 $j$번째 문자까지로 구성된 부분문자열이라 하자. 실패 함수 $f(i)$는 $i$ 보다 작은 값이며, $P[i-f(i)+1, i]$와 $P[1, f(i)]$가 같도록 되는 최대값으로 정의된다.

 

패턴 $P$의 실패함수는 아래처럼 $O(|P|)$에 계산할 수 있다.

위 방법의 시간복잡도가 $O(|P|)$라는 것을 쉽게 보이기 위해서는 4번째 줄의 while문에 집중할 필요가 있다. while문을 한 번 돌 수록 변수 k는 적어도 1 감소하게된다. 변수 k는 0에서부터 시작해서 최대 $|P|$ 만큼 증가하므로 감소 또한 최대 $|P|$번 일어날 수 있다. 따라서 전체 시간복잡도가 $O(|P|)$가 된다.

 

실패 함수를 계산하는 것과 문자열 $S$에 패턴 $P$가 존재하는지 확인하는 것은 완전히 똑같다.

실패 함수를 구할 때와 마찬가지의 이유로 시간복잡도가 $O(|S|)$이다.

2) Aho-Corasick Algorithm

Aho-Corasick Algorithm은 KMP Algorithm과 거의 흡사하다. 하나의 차이점이 있다면 패턴이 한 종류일 때 쓰는 KMP Algorithm과 달리 Aho-Corasick Algorithm은 패턴이 여러 개일 때 사용하는 방법이다. 시간복잡도는 $O(|S| + \sum{|P_i|})$이다.

 

Aho-Corasick Algorithm에서 패턴들을 Trie로 나타낼 수 있다. 예를 들어 패턴이 {"he", "she", "his", "hers"}라고 했을 때 아래처럼 Trie를 구성할 수 있다.

KMP Algorithm에서는 실패 함수 값을 하나의 수(길이값)로 표현하지만 Aho-Corasick Algorithm에서는 노드에서 비슷한 원리로 실패 링크를 만들 수 있다. 위 Trie에서 실패 링크를 포함 시키면 아래 그림처럼 된다. 아래 링크에서는 실패 링크를 점선으로 표현했다.

위 Trie를 구성하는 시간복잡도는 $O(\sum{|P_i|}$ 이다. Trie를 구현하고 문자열 $S$에 대해 탐색하는 것도 KMP Algorithm과 마찬가지로 하면 된다. 문자열에 대해 매칭을 검색하는 시간복잡도느 $O(|S|)$가 된다. 간단한 Aho-Corasick Algorithm 구현 문제로는 BOJ 9250번 - 문제열 집합 판별 문제가 있다.

 

Aho-Corasick Algorithm에서는 패턴이 여러 개이기 때문에 실패 링크 외에도 출력 링크라는 것이 필요하다. 어떤 패턴이 다른 패턴의 substring인 상황(위 그림에서 he는 she의 substring)인 경우에 패턴을 찾지 못할 수 있기 때문에 필요한 것이다. 어떤 노드의 출력 링크란 그 노드를 포함하여 실패 링크를 따라가다 만나는 패턴의 끝을 나타내는 노드를 향하는 링크를 의미한다.

 

아래 코드는 Aho-Corasick 구현 및 각 패턴이 문자열에 몇번 등장하는지 계산하는 코드다.

 

더보기

 

'공부' 카테고리의 다른 글

가장 먼 두 점 구하기  (6) 2016.07.17
Building Heap in Linear Time  (2) 2016.07.01
Persistent Segment Tree  (6) 2016.06.23
Divide & Conquer Optimization  (3) 2016.06.23
Knuth Optimization - Dynamic Programming  (4) 2016.06.23
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2023/09   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
글 보관함