티스토리 뷰

공부

String Matching Algorithm

전명우 2016.06.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 구현 및 각 패턴이 문자열에 몇번 등장하는지 계산하는 코드다.


코드 보기


저작자 표시
신고

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

가장 먼 두 점 구하기  (3) 2016.07.17
Building Heap in Linear Time  (2) 2016.07.01
String Matching Algorithm  (4) 2016.06.24
Persistent Segment Tree  (4) 2016.06.23
Divide & Conquer Optimization  (0) 2016.06.23
Knuth Optimization - Dynamic Programming  (2) 2016.06.23
댓글
  • 프로필사진 궁금증 아호코라식에서 dfs로 패턴 등장 회수 누적계산은 왜하는 건가요? 2016.08.11 04:40 신고
  • 프로필사진 전명우 패턴이
    ab
    abab
    ababc
    세 개 있고, 전체 문자열이 ababc라고 합시다.
    첫번째 패턴인 ab인 경우 2번으로 세어져야하는데, 질문하신 작업이 없으면 1번으로 세어집니다.
    2016.08.17 05:21 신고
  • 프로필사진 KJBS2 코드에서
    she 3
    she
    he
    e
    를 입력하면
    1
    1
    0
    으로 나옵니다.

    등장 회수 누적계산 할 때, 단순 dfs가 아니라 길이가 긴 패턴부터 봐야하지 않을까요??
    2017.03.01 10:57 신고
  • 프로필사진 전명우 맞습니다. 처음에 왜 저렇게 짰는지 잘 모르겠네요. BFS 역순으로 더해주면 간단할 것 같습니다. 2017.03.21 20:19 신고
댓글쓰기 폼