[Algorithm]Regular Expression and NFA

这篇文章主要介绍正则表达式(Regular Expression)，与如何运用NFA来解决其匹配的问题，主要参考了Princeton Algorithm一书的相关章节。首先我们定义的正则表达式(RE)如下:

• 空串
• 单个字符，其中.可以match任意单个字符
• 被括号括起来的RE
• 两个或两个以上的RE连接
• 两个或两个以上的RE用or(|)隔开
• RE后面跟着closure(*)符号

以上规定了一个正则表达式的语法。具体来说，正则表达式是一系列的字符串的集合，定义如下：

• 空串代表空集
• 单个字符就代表他本身，.代表所有合法字符的集合
• 多个RE相连表示了这多个个集合的叉乘，也就是说每个集合我们都遍历所有的可能
• 多个RE用or隔开表示这多个集合的并集
• closure代表空集或者，RE重复任意多次所构成string的集合

比如对于正则表达式(.B|C(DE)*):

• AB, BCDE, ZBDEDEDE都可以match
• ABC, BDE, CDEDE都不match

那么现在的问题就是对于给定的正则表达式，我们有效的判定每一个输入字符串是否match。在KMP算法当中，我们是用DFA自动机的思想，对于给定的输入的每一个字符，我们根据建立的next数组转移到对应的状态，每接受一次输入，自动机的状态是确定的，所以叫做Deterministic Finite Automata。

但是对于正则表达式，我们没有办法做到这一点，因为or的存在，我们没办法根据当前输入的单个字符确定是否match；同样因为closure，我们不确定要扫多少个字符才能确定不能match。所以DFA是没有办法帮我们解决RE问题的，我们需要更强力的武器，NFA(Non-Deterministic Finite Automata)。

为了理解什么是NFA，我们用正则表达式((A*B|AC)D)举例:

图一就是((A*B|AC)D)所对应的NFA，NFA有如下性质:

• 对于长度为N的RE(每个RE我们用括号括起来)有N + 1个状态，每一个char对应一个状态，最后为accept的状态
• 每一个字母都有一个出向边指向下一个字符所对应的状态(图中黑色边)
• (, ), *, | 都有至少一个出向边，可能指向任何一个其他的状态(图中红色边)
• 有的状态可能有多个出向边，但是只会有一个黑色的出向边

对于所有的RE，我们都在其外圈加一个括号，这样我们每次就都会从左括号出发。同DFA一样，我们每次也读一个字符:

• 如果我们现在处于某个字母所表示的状态，并且读入的字符和其match，我们从黑色的边转移到下一个状态，我们称其为match transition。
• 我们可以在不扫描输入字符的情况下，直接沿着红边进行状态转移。比如我们在start state 0的时候，我们可以不match任何输入字符，到达1, 2, 3, 4, 6。我们称之为ε-transition

因为ε-transition的存在我们事实上是从一个状态的集合向另一个状态的集合转移。这样我们每一次的match输入字符串的步骤为:

1. DFS找到所有可能的初始状态的集合
2. 每一次扫描输入字符，对于当前的集合，找到对应进行match transition的之后的状态集合，
3. 再DFS找到所有进行ε-transition可以到达的集合。重复步骤2和3，直到扫描完所有输入字符
4. 看当前状态的集合是否包括accpet状态

我们拿((A*B|AC)D)和AABD举例，下图表示了每个步骤具体的操作：

时间复杂度分析，假设RE长为M，待匹配串长度为N，时间复杂度为O(N * M)，对于每一个输入字符，我们最多需要找N个状态。

那么剩下的问题，就是对于一个RE，我们如何建立对应的NFA。我们需要一个栈来存一些特殊的字符，比如括号和or，对于每一个不同的字符:

• 当前字符如果是普通字母或者是. ，这是最简单的状况，会有一条黑色的出向边连接下一个状态
• 当前字母是括号，对于左括号，我们直接放上stack。对于右括号，我们pop栈上的字符直到左括号，对应字符的操作见下文
• 对于包含or的RE，例如(A | B)，我们需要建立两条对应ε-transition的边，一条从左括号到B，对应我们可以直接跳过A到达B；另一条从| 到达右括号，对应我们如果match了A就要跳过之后的。如果有多个or的符号也是一样的。我们每次push or对应的index到栈上，碰到右括号之后，就一直pop直到左括号，碰到or符号的话，我们就建立对应的两条边
• 对于closure，其有两种情况
• 单个字符后面接closure，这样我们建一条从字符到closure的边，另一条从closure回到字符的边，两条ε-transition边
• RE带括号后面接closure，这样我们需要从左括号到closure建立两条对应的边

下图表明了对应不同符号应该建立的边：

值得一提的是，在我们真正建图的时候，只需要建立所有的ε-transition，matching transition并不需要刻意建，因为其事实上就是从当前字符转移到下一个字符。

我们仍然拿((A*B|AC)D)距离，对应的步骤如下：

时间复杂度方面，对于长度为N的RE，时间复杂度为O(N)，因为我们每次最多加三条边。空间复杂度也是O(N)，代码如下

	#include <iostream>
	#include <vector>
	#include <string>
	#include <stack>
	#include <deque>
	#include <algorithm>
	using namespace std;
	class NFA
	{
	public:
	NFA()
	{
	}
	//we always assume the input is valid
	NFA(string p)
	{
	remove_if(p.begin(), p.end(), ::isspace);
	pattern = "(" + p + ")";
	N = pattern.size();
	graph = vector<vector<int>>(N + 1);//extra success state
	init();
	}
	bool Match(string input)
	{
	if(!N)return false;
	//maintain reachable states
	deque<int> reachable;
	vector<bool> visited(N + 1, false);
	dfs(reachable, visited, 0);//intialize start states
	for(auto& c : input)
	{
	//moves along black edges
	int len = reachable.size();
	for(int i = 0; i < len; ++i)
	{
	int state = reachable.front();
	reachable.pop_front();
	if(pattern[state] == c || pattern[state] == '.')
	reachable.push_back(state + 1);
	}
	//dfs epislon edges, update reachable states
	vector<int> currStates;
	while(reachable.size())
	{
	currStates.push_back(reachable.front());
	reachable.pop_front();
	}
	for(int i = 0; i < N + 1; ++i)visited[i] = false;
	for(auto& curr : currStates)
	dfs(reachable, visited, curr);
	}
	for(auto& state : reachable)
	if(state == N)return true;
	return false;
	}
	private:
	vector<vector<int>> graph;
	string pattern;
	int N;
	void dfs(deque<int>& states, vector<bool>& visited, int u)
	{
	if(visited[u])return;
	visited[u] = true;
	states.push_back(u);
	for(auto& v : graph[u])
	dfs(states, visited, v);
	}
	//from u to v
	void addEdge(int u, int v)
	{
	graph[u].push_back(v);
	}
	//what we support
	//A regular expression (RE) is either
	//1. Empty
	//2. A single character
	//3. A regular expression enclosed in parentheses
	//4. Two or more concatenated regular expressions
	//5. Two or more regular expressions separated by the or operator (|)
	//6. A regular expression followed by the closure operator (*)
	//we only need to constrct epsilon path, black path can be easily handled
	//when we take input
	void init()
	{
	stack<int> ops;
	for(int i = 0; i < N; ++i)
	{
	char c = pattern[i];
	int leftP = i;//position of left paren of char
	if(c == '(' || c == '|')
	ops.push(i);
	else if(c == ')')
	{
	vector<int> ors;
	while(pattern[ops.top()] != '(')
	{
	int idx = ops.top();
	ops.pop();
	if(pattern[idx] == '|')
	ors.push_back(idx);
	}
	//we assume the input is always valid and we always can find a left paren
	leftP = ops.top();
	ops.pop();
	//we need to connect edge for each or
	for(auto pos : ors)
	{
	addEdge(leftP, pos + 1);
	addEdge(pos, i);
	}
	}
	//since closure(*) may appear after right parenthesis, we always look head
	//since it is easier to handle
	if(i < N && pattern[i + 1] == '*')
	{
	addEdge(leftP, i + 1);
	addEdge(i + 1, leftP);
	}
	//we always have an edge to the next state for * and parenthesis
	if(c == '(' || c == ')' || c == '*')
	addEdge(i, i + 1);
	}
	if(ops.size())throw 1;
	}
	};
	int main()
	{
	int n;
	cin >> n;
	while(n--)
	{
	int validPattern = false;
	NFA nfa;
	while(!validPattern)
	{
	try
	{
	cout << "Please enter pattern string:" << endl;
	string p;
	cin >> p;
	nfa = NFA(p);
	validPattern = true;
	}
	catch(...)
	{
	cout << "Invalid pattern detected! Please re-enter..." << endl;
	validPattern = false;
	}
	}
	cout << "Please enter string to match:" << endl;
	string s;
	cin >> s;
	bool match = nfa.Match(s);
	if(match)
	cout << "Matched!" << endl;
	else
	cout << "Not Match!" << endl;
	}
	return 0;
	}

view raw NFA_Regular Expression Matching.cpp hosted with ❤ by GitHub