[Algorithm Part 2] 9. Pattern Matching

이전 글에서는, "특정 문자열(one string)을 탐색하는 문제"에 대해 살펴봤다. (substring search)

본문에서는, "특정 문자열 집합(one of specified set of string)을 탐색하는 문제"에 대해 살펴볼 것이다. (pattern matching)

문자열 집합을 표현하는 대표적인 방법에는 정규표현식(=regular expression)이 있다.

---

Regular expressions

Definition

Regular expressions is a notation to specify a set of strings.

Operations

operation	order	example RE	matches
concatenation	3	AABAAB	AABAAB
or	4	AA | BAAB	AA, BAAB
closure	2	AB*A	AA, ABBBA
parentheses	1	A(A|B)AAB	AAAAB, ABAAB
wildcard		.A.A.A	CAEAGA
character class		[A-Za-z][a-z]*	word, Capitalized
at least 1		A(BC)+DE	ABCED, ABCBCED
exactly k		[0-9]{5}-[0-9]{4}	03413-2341

---

Duality between RE and DFA

RE는 특정 문자열 집합을 표현하는 방법이고, DFA는 특정 문자열 집합을 말뭉치에서 탐색하는 기계다.

즉, 임의의 말뭉치를 scan하면서 특정 문자열 집합과 일치하는 말뭉치의 부분 문자열을 찾는 기계다.

Kleene 이론에 따르면, DFA의 탐색 범위(=문자열 집합)를 RE로 표현할 수 있을 뿐만 아니라,

RE으로 표현한 문자열 집합을 탐색하는 DFA를 만들 수 있다.

Kleene's theorem

For any DFA, there exists a RE that describes the same set of strings

For any RE, there exists a DFA that recongizes the same set of strings

Basic algorithm

Kleene 이론에 의해, pattern matching 알고리즘은 KMP 알고리즘과 같다.

RE를 기반으로 DFA를 설계한 후, DFA로 말뭉치를 탐색(in linear-time)한다. 

 

하지만, 위 방법은 구현 불가하다. DFA가 기하급수적인 state의 개수를 가질 수 있기 때문이다.

---

위 한계점을 해결하기 위해, DFA가 아닌 NFA를 사용할 것이다.

NFA를 사용하면 말뭉치 탐색이 quadratic하게 작동한다.

NFA(Nondeterministic Finite-state Automata)

DFA는 input stream에 대한 transition이 명확하다. 즉, 경로가 한 개다.

그에 반해 NFA는 input stream에 대한 transition이 명확하지 않다. 즉, 경로가 여러 개다.

RE-matching NFA

• 모든 RE는 괄호로 감싸져 있다.
• RE 문자 당 하나의 state가 있다.
• Red $\epsilon$-transition은 corpus 문자 탐색(=event) 없이, transition 가능하다.
• Black match transition은 corpus 문자 탐색 후, transition 가능하다.
  탐색 문자와 일치하는 state만 transition이 가능하다.
• "임의의 transition 경로가 accept state에서 끝나면, match되었음"을 의미한다.
  즉, "input stream에 대한 여러 가지 transition 경로 중 하나라도 accept state에 도달하면, match되었음"을 의미한다.

위 방법대로 NFA를 설계한 후, corpus에 대한 모든 transition 경로를 고려하면, 위 문제를 풀 수 있다.

이제부터, NFA 설계 방식과 simluate 방법에 대해 살펴보겠다.

---

State machine

• State = 0 ~ M (RE의 symbol 개수 + accept state)
• Match-transitions: re[] 배열이 암시적으로 표현하고 있다.
  즉, 탐색 symbol c가 re[]에 있을 시, 다음 state로 이동한다.
• $\epsilon$-transition: digraph에 저장한다.

---

NFA simulation

Algorithm

• 각 step(=reading $i$th symbol)마다, 도달할 수 있는 모든 states을 유지한다.
  
  1. match-transition 실행: 현재 모든 state 중, $i$th symbol과 일치하는 state(re[] == c)만 다음 state로 이동하고, 나머지 state(re[] != c)는 삭제된다.
  2. $\epsilon$-transition 실행: 살아남은 state에서 $\epsilon$-transition를 이용해 갈 수 있는 모든 state를 찾는다.
     (Digraph reachability)
• corpus의 모든 symbol을 읽은 후, 하나라도 accept state에 도달하면 accept가 된다.
  그렇지 않을 경우, reject가 된다.

Digraph reachability

• problem: 특정 정점 또는 정점 집합에서 도달할 수 있는 모든 정점을 찾는 문제
• algorithm: 각 정점마다, DFS를 실행시켜, 방문한 모든 정점을 반환

---

NFA construction

States: M + 1개의 state로 구성되어 있다. (RE의 symbol 개수 + accept state)

Building transition

• Concatenation: 다음 state로 가는 match-transition edge를 추가한다.
• Parentheses: 다음 state로 가는 $\epsilon$-transition edge를 추가한다.
• Closure: $\epsilon$-transition edge 3개를 추가한다.
  1. 다음 state로 가는 $\epsilon$-transition edge
  2. 반복 문자열의 첫 문자로 가는 $\epsilon$-transition edge
  3. 반복 문자열의 첫 문자에서 오는 $\epsilon$-transition edge
• Or: $\epsilon$-transition edge 3개를 추가한다.
  1. right parentheses로 가는 $\epsilon$-transition edge
  2. left parentheses에서 오는 $\epsilon$-transition edge

(그 외의 operations은 생략하겠다.)

위 closure과 or-transition을 추가하기 위해선, left parentheses를 기억하고 있어야 한다.

방법 중 하나로 left parentheses 위치를 stack에 저장하는 방법이 있다.

Performance

	NFA construction	NFA simulation
time-complexity	M	MN(=worst case)

---

Applications

Grep(Generalized Regular Expression Print)은 대표적인 pattern matching application으로,

RE와 corpus가 주어졌을 때, RE와 일치하는 corpus의 부분 문자열을 출력하는 프로그램이며, NFA로 풀 수 있다.

이때, worst case time-complexity는 MN이다.

 

대부분의 언어(unix-grep, python, java, javascript)는 pattern matching application이 내재되어 있다.

하지만, 이들은 quadratic-time을 보장해주지 않고, expontial-time을 가진다. (비효율적인 알고리즘(DFA)을 사용한 듯하다.)

뿐만 아니라, RE로 표현할 수 있지만 non-regular한 pattern(e.g., back-reference)은 못 찾는다. (이건 우리가 공부한 알고리즘에서도 못 찾는다.)

KMP vs Grep vs Javac

	KMP	Grep	Javac
pattern	string	RE	program
parser		check if legal	check if legal
compiler output	DFA	NFA	byte code
simulator	DFA simulator	NFA simulator	JAM

---

결론: RE(String)를 NFA(DFA)로 추상화하여, pattern matching(substring search)이라는 문제를 풀 수 있다.