Posted in Algorithm, coursera, NFA, regex
Regular Expression, NFA
Comment
Regular Expression
이전까지 배웠던 패턴매칭 기법들은 모두 단일 패턴만을 찾았었. (e.g substring search) 일치하는 집합 을 원한다면 어떻게 해야할까?
예를 들어 유전자 분석에서는 Fragile X syndrome 은 GCG(CGG|AGG)*CTG 패턴에서 더 많이 반복될수록 fragile x 신드롬일 확률이 높다. 이 경우에는 하나가 아니라 몇번 일치하는지가 중요한 결과값이 된다.
따라서 문자열 같은 단일 패턴이 아니라 집합 으로 지정된 패턴을 찾아낼 수 있는 알고리즘이 필요하다.
regex 의 응용은
- natural language processing
- scan for virus signatures
- syntax highlighting
- text filtering
- parsing text (compiler, crawler)
A regular expression is a notation to specify a set of string
사용 가능한 연산으로
(http://homepages.ius.edu/RWISMAN)
- concat (3)
- or (4)
- closure (2)
- parenthesis (1)
괄호 안은 우선순위다. 편의를 위한 연산으로
- wildcard
. - character class
[A-Za-z][a-z]* - at lest 1
+ - exactly k
[0-9]{5}
[A-E]+ 를 기본 연산으로 풀어쓰면 (A|B|C|D|E)(A|B|C|D|E)* 다.
정규표현식을 작성하는 것은 프로그램을 만드는 것과 비슷하다
- need to understand programming model
- can be easier to write than read
- can be difficult to debug
Res are amazingly powerful and expressive. but using them in applications can be amazingly complex and error-prone
REs and NFA
RE 와 DFA 는 dual 이다.
- RE: concise way to desribe a set of string
- DFA: machine to recognize whether a given string in a given set
Kleene's theorem 에 의하면
어떤 DFA 든 같은 문자열 집합을 기술하는 RE 가 존재하고, 역으로 어느 RE 에 대해서도 같은 문자열 집합을 인식할 수 있는 DFA 가 존재한다.
따라서 RE 로 부터 DFA 를 만들고, 이걸 인풋에 대해 돌리면 된다. 그리고 DFA 를 사용하기 때문에 KMP 알고리즘처럼
- no backup in text input stream
- linear-time guarantee
하지만 실제로는 DFA 를 사용하기가 어렵다. 이는 DFA 가 수 많은 상태를 가질 수 있기 때문이다. 따라서 DFA 대신 NFA 를 이용하는 방법이 개발되었다. NFA 를 이용하면 quadratic-time guarantee 다.
NFA, Nondeterministic finite-state automata 에서는
- RE enclosed in parentheses
- One state per RE character (start=
0, accpet=M) - ε-transition (change state, but dn't scan text)
- accept if any sequence of transitions ends in accpet state
뭔소린가 해서 구글링을 좀 해보니
If it’s a DFA, we know that each word completely determines the final state of the automaton, and we say that the word is accepted if that state is an acceptor state.
If it’s an NFA, there might be several possible final states that could result from reading a given word; as long as at least one of them is an acceptor state, we say that the automaton accepts the word.
DFA 는 입력에 대해 결과값이 항상 하나로 일정하지만, NFA 에서는 복수개의 final state 가 만들어질 수 있다. 그리고 이 때 하나라도 accept 되면, 입력값이 accept 된 것으로 본다.
이 때 다양한 final state 가 만들어 지는 이유는 스캔 없이 상태를 변경하는 ε-transition 때문이다. 따라서 같은 입력이라도, 올바르게 파싱할수도, 그렇지 않을수도 있다.
따라서 NFA 에서는 모든 가능한 경우에 대해 시뮬레이션 해야한다. 그런데, 하나씩 다 해보긴 비효율적이므로 매 문자를 읽을때마다 all possible states 를 유지하면서 match, ε-transition 을 적용해 나간다. 그리고 모든 문자를 다 읽었을때 possible state 에 accept 가 있으면 성공적으로 패턴이 매칭된 것이다.
따라서 possible state 를 얻기 위해 reachability 를 계산해야 하는데 digraph 를 사용하면 문제가 쉬워진다. 방문하지 않은 vertex 가 없을때까지 DFS 를 돌리면 된다. 러닝타임은 E + V
NFA Simulation
코드는
public class NFA {
private char[] re; // match transition
private Digraph G; // epsilon transition
private int M; // # of states
public NFA(String regex) {
M = regex.length();
re = regex.toCharArray();
G = buildEpsilonTransitionDigraph();
}
private Digraph buildEpsilonTransitionDigraph() {
// TODO Auto-generated method stub
return null;
}
public boolean recognizes(String txt) {
Bag<Integer> rs = new Bag<Integer>(); // reachable states
DirectedDFS dfs = new DirectedDFS(G, 0);
// get reachable states initially
for (int v = 0; v < G.V(); v++)
if (dfs.marked(v)) rs.add(v);
for (int i = 0; i < txt.length(); i++) {
// match transition
Bag<Integer> match = new Bag<Integer>();
for (int v : rs) {
if (v == M) continue;
if ((re[v] == txt.charAt(i)) || re[v] == '.')
match.add(v + 1); // add next state
}
// run epsilon transition with match
dfs = new DirectedDFS(G, match);
rs = new Bag<Integer>();
for (int v = 0; v < G.V(); v++)
if (dfs.marked(v)) rs.add(v);
}
for (int v : rs)
if (v == M) return true;
return false;
}
}
NFA simulation 은 N 길이의 텍스트, M 길이의 패턴에 대해서 worst case 일 때 MN 의 성능을 보인다.
이는 N 개의 텍스트에서, 한 문자를 스캔할때 마다 최대 M 개의 state 가 있을 수 있고, 여기에 대해 ε-transition 를 찾기 위해 DFS 를 돌리기 때문이다.
쉽게 말해서 노드 수가 M 인 그래프에 대해 DFS 를 돌리는데, N 번 돌리기 때문에 최악의 경우 MN 의 성능을 보여준다는 것이다.
그리고 뒤에서 자세히 언급하겠지만 NFA construction 에서 그래프의 edge 수가 <= 3M 임을 보장한다.
NFA Construction
regex 에 대응하는 NFA 를 만드는 과정은 match, ε-transition 로 이어진 그래프를 만드는것과 동일하다. regex 에서 각 연산들에 대해
- concatenation: add match-transition edge from state corresponding to chars in the alphabet to next state
알파벳으로부터만 연결하므로 ( -> ) 등은 match transition 으로 연결하지 않는다.
parentheses: add ε-transition edge from parentheses to next state
closure: add three ε-transition edges for each
*operator
예를 들어 A*B 의 경우, A -> *, * -> A, * -> B 3개의 ε-transition 을 추가한다.
- or: add two ε-transition edges for each
|operator
예를 들어 ( A | B ) 의 경우 ( -> B, | -> ) 로 ε-transition 을 추가한다.
NFA 를 만드는데 있어서 한 가지 어려운점은 closure 을 만들기 위해서는 ( 를 기억해야 하고, or 을 만들기 위해서는 ( 와 | 의 위치를 알고 있어야 한다는 점이다. 스택을 쓰면 된다.
(를 만나면(를 스택에 넣고|를 만나면|를 스택에 넣자)를 만나면(를 스택에서 빼고,|도 있다면 그것도 빼자. 스택엣 제거한(, |의 위치를 이용해 closure, or 을 만들 수 있다.
Regex to NFA 를 보는게 이해가 더 쉬울듯. (강의 끝부분에 약간 틀린곳이 있으니 댓글을 참조하자.)
구현은
private Digraph buildEpsilonTransitionDigraph() {
Digraph G = new Digraph(M + 1); // including the accept state
Stack<Integer> ops = new Stack<Integer>();
for (int i = 0; i < M; i++) {
int lp = i;
// keep '(', '|' to implement closure, OR
if (re[i] == '(' || re[i] == '|') ops.push(i);
// OR
else if (re[i] == ')') {
int or = ops.pop();
if (re[or] == '|') { // if '|' exists
lp = ops.pop();
G.addEdge(lp, or + 1);
G.addEdge(or, i);
}
else lp = or; // left paren
}
if (i < M - 1 && re[i + 1] == '*') {
G.addEdge(lp, i + 1);
G.addEdge(i + 1, lp);
}
if (re[i] == '*' || re[i] == '(' || re[i] == ')')
G.addEdge(i, i + 1);
}
return G;
}
만약 + 를 만들고 싶다면 * 과 같지만 i -> i + 1 또는 괄호가 있을때는 lp -> i + 1 edge 하나를 제거해야 한다. (바로 넘어가는 경우가 없기 때문)
NFA 를 만들때 M 길이의 패턴에 대해 시간과 공간 비용은 M 에 비례한다. 이는 아무리 많아봐야 한 state 에 대해 3개의 ε-transition, 2개의 스택 연산이 필요하기 때문이다.
Regex Application
String regex = ".*" + p + ".*";
NFA nfa = new NFA(regex);
while (stdin.hasNext) {
String line = stdin.readLine();
if (nfa.recognize(line))
println(line)
}
자주 쓰는 프로그램인 grep 도 regex 를 사용한다. 패턴을 p 를 받아 (.*p.*) 처럼 regex 를 만들어 라인마다 검사할 수 있다. 근데, worst case 에는 라인마다 MN 이니까 brute force substring search 랑 별 차이가 없다.
validation 을 위해 사용할수도 있다. 컴파일러에서 변수 이름이 규칙에 맞는지 검사하거나, 사용자의 입력이 올바른 이메일인지 등등.
regex 는 대부분의 언어에서 라이브러리 형태로 사용할 수도 있다. 자바에서도 지원하는데
import java.util.regex.Pattern;
import java.util.regex.Matcher
String regex = args[0];
Pattern p = Pattern.compile(regex) // create NFA from RE
Matcher m = p.matcher(input) // build NFA simulator
while (m.find()) {
do something using m.group()
}
Algorithmic complexity attacks
그리고 대부분의 구현(자바, 그렙, 펄을 포함해서)이 performance 를 보장하지 않는다고 한다.
java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaac 1.6 seconds
java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac 3.7 seconds
java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac 9.7 seconds
java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac 23.2 seconds
java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac 62.2 seconds
java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac 161.6 seconds
스팸 필터기에 spammer@x....................................... 따위의 주소로 이메일을 보낸다거나.
Back References
\1 은 보통 바로 전에 매칭된 부분을 의미한다. 대부분의 언어에서 지원하긴 하는데
Pattern matching with back-references in intractable
요것도 퍼포먼스 어택이 올 수 있다고 함.
Summary
language, abstract machine, non-deterministic 등은 컴퓨터 과학의 중요한 이론적 토대가 된다.
지금까지 공부한 알고리즘은 machine code 를 돌려주는 일종의 컴파일러라 볼 수 있다.
- KMP: string -> DFA
파서는 필요없고, DFA simulator 를 이용해 실행
- Grep: regex -> NFA
legal 인지 확인할 파서가 필요하며 NFA simulator 를 이용
- Javac: java langugage -> java byte code
마찬가지로 파서가 필요하며 JVM 을 이용해 실행
Reference
(1) Algorithms: Part 2 by Robert Sedgewick
(2) http://introcs.cs.princeton.edu
(3) http://homepages.ius.edu/RWISMAN
(4) Difference between NFA and DFA