@[toc]
在上篇部落格
從0到1打造正規表達式執行引擎(一) 中我們已經建構了一個可用的正規表達式引擎，相關源碼見 https://github.com/xindoo/regex ，但上文中隻是用到了NFA，NFA的引擎建圖時間複雜度是O(n)，但比對一個長度為m的字元串時因為涉及到大量的遞歸和回溯，最壞時間複雜度是O(mn)。與之對比DFA引擎的建圖時間複雜度O(n^2)，但比對時沒有回溯，是以比對複雜度隻有O(m)，性能差距還是挺大的。DFA和NFA
我們已經多次提到了NFA和DFA，它倆究竟是啥？有啥差別？
首先，NFA和DFA都是有限狀态機，都是有向圖，用來描述狀态和狀态之間的關系。其中NFA全稱是非确定性有限狀态自動機(Nondeterministic finite automaton)，DFA全稱是确定性有限狀态自動機(Deterministic finite automaton)。
二者的差異主要在于确定性和非确定性，何為确定性？ 确定性是指面對同一輸入，不會出現有多條可行的路徑執行下一個節點。有點繞，看完圖你就了解了。
圖示分别是一個NFA和DFA，上圖之是以是NFA是因為它有節點具備不确定性，比如0節點，在輸入"a"之後它分别可以到0 1 2 節點。還有，上圖有$\epsilon$邊，它可以在沒有輸入的情況下跳到下一個節點，這也帶來了不确定性。相反，下圖DFA中，每個節點對某一特定的輸入都隻有最多一條邊。
總結下NFA和DFA的差別就是，有ε邊或者某個節點對同一輸入對應多個狀态的一定是NFA。
DFA和NFA存在等價性，也就是說任何NFA都可以轉化為等價的DFA。由于NFA的非确定性，在面對一個輸入的時候可能有多條可選的路徑，是以在一條路徑走不通的情況下，需要回溯到選擇點去走另外一條路徑。但DFA不同，在每個狀态下，對每個輸入不會存在多條路徑，就不需要遞歸和回溯了，可以一條路走到黑。DFA的匹複雜度隻有O(n)，但因為要遞歸和回溯NFA的比對複雜度達到了O(n^2)。 這也是為什麼我們要将引擎中的NFA轉化為DFA的主要原因。
NFA轉DFA
算法
NFA轉DFA的算法叫做子集構造法，其具體流程如下。
- 步驟1: NFA的初始節點和初始節點所有ε可達的節點共同構成DFA的初始節點，然後對初始DFA節點執行步驟2。
- 步驟2: 對目前DFA節點，找到其中所有NFA節點對輸入符号X所有可達的NFA節點，這些節點溝通構成的DFA節點作為目前DFA節點對輸入X可達的DFA節點。
- 步驟3: 如果步驟2中找到了新節點，就對新節點重複執行步驟2。
- 步驟4: 重複步驟2和步驟3直到找不DFA新節點為止。
- 步驟5: 把所有包含NFA終止節點的DFA節點标記為DFA的終止節點。
語言描述比較難了解，我們直接上例子。 我們已經拿上一篇網站中的正規表達式 a(b|c) 為例，我在源碼
中加入了NFA輸出的代碼， a(b|c) 的NFA輸出如下。
from to input
0-> 1 a
1-> 8 Epsilon
8-> 9 Epsilon
8-> 6 Epsilon
6-> 2 Epsilon
6-> 4 Epsilon
2-> 3 b
4-> 5 c
3-> 7 Epsilon
5-> 7 Epsilon
7-> 9 Epsilon
7-> 6 Epsilon 繪圖如下：
我們在上圖的基礎上執行步驟1 得到了節點0作為DFA的開始節點。
然後對DFA的節點0執行步驟1，找到NFA中所有a可達的NFA節點(1#2#4#6#8#9)構成NFA中的節點1，如下圖。
我以dfa1為出發點，發現了a可達的所有NFA節點(2#3#4#6#7#9)和b可達的所有節點(2#4#5#6#7#9)，分别構成了DFA中的dfa2和dfa3，如下圖。
然後我們分别在dfa2 dfa3上執行步驟三，找不到新節點，但會找到幾條新的邊，補充如下，至此我們就完成了對 a(b|c)* 對應NFA到DFA的轉化。
可以看出DFA圖節點明顯少于NFA，但NFA更容易看出其對應的正規表達式。之前我還寫過DFA生成正規表達式的代碼，詳見文章
https://blog.csdn.net/xindoo/article/details/102643270代碼實作
代碼其實就是對上文流程的表述，更多細節見
。
private static DFAGraph convertNfa2Dfa(NFAGraph nfaGraph) {
DFAGraph dfaGraph = new DFAGraph();
Set<State> startStates = new HashSet<>();
// 用NFA圖的起始節點構造DFA的起始節點 步驟1
startStates.addAll(getNextEStates(nfaGraph.start, new HashSet<>()));
if (startStates.size() == 0) {
startStates.add(nfaGraph.start);
}
dfaGraph.start = dfaGraph.getOrBuild(startStates);
Queue<DFAState> queue = new LinkedList<>();
Set<State> finishedStates = new HashSet<>();
// 如果BFS的方式從已找到的起始節點周遊并建構DFA
queue.add(dfaGraph.start);
while (!queue.isEmpty()) { // 步驟2
DFAState curState = queue.poll();
for (State nfaState : curState.nfaStates) {
Set<State> nextStates = new HashSet<>();
Set<String> finishedEdges = new HashSet<>();
finishedEdges.add(Constant.EPSILON);
for (String edge : nfaState.next.keySet()) {
if (finishedEdges.contains(edge)) {
continue;
}
finishedEdges.add(edge);
Set<State> efinishedState = new HashSet<>();
for (State state : curState.nfaStates) {
Set<State> edgeStates = state.next.getOrDefault(edge, Collections.emptySet());
nextStates.addAll(edgeStates);
for (State eState : edgeStates) {
// 添加E可達節點
if (efinishedState.contains(eState)) {
continue;
}
nextStates.addAll(getNextEStates(eState, efinishedState));
efinishedState.add(eState);
}
}
// 将NFA節點清單轉化為DFA節點，如果已經有對應的DFA節點就傳回，否則建立一個新的DFA節點
DFAState nextDFAstate = dfaGraph.getOrBuild(nextStates);
if (!finishedStates.contains(nextDFAstate)) {
queue.add(nextDFAstate);
}
curState.addNext(edge, nextDFAstate);
}
}
finishedStates.add(curState);
}
return dfaGraph;
} public class DFAState extends State {
public Set<State> nfaStates = new HashSet<>();
// 儲存對應NFAState的id,一個DFAState可能是多個NFAState的集合,是以拼接成String
private String allStateIds;
public DFAState() {
this.stateType = 2;
}
public DFAState(String allStateIds, Set<State> states) {
this.allStateIds = allStateIds;
this.nfaStates.addAll(states);
//這裡我将步驟五直接內建在建立DFA節點的過程中了
for (State state : states) {
if (state.isEndState()) {
this.stateType = 1;
}
}
}
public String getAllStateIds() {
return allStateIds;
}
} 另外我在DFAGraph中封裝了有些NFA節點清單到DFA節點的轉化和查找，具體如下。
public class DFAGraph {
private Map<String, DFAState> nfaStates2dfaState = new HashMap<>();
public DFAState start = new DFAState();
// 這裡用map儲存NFAState結合是已有對應的DFAState, 有就直接拿出來用
public DFAState getOrBuild(Set<State> states) {
String allStateIds = "";
int[] ids = states.stream()
.mapToInt(state -> state.getId())
.sorted()
.toArray();
for (int id : ids) {
allStateIds += "#";
allStateIds += id;
}
if (!nfaStates2dfaState.containsKey(allStateIds)) {
DFAState dfaState = new DFAState(allStateIds, states);
nfaStates2dfaState.put(allStateIds, dfaState);
}
return nfaStates2dfaState.get(allStateIds);
}
} DFA引擎比對過程
dfa引擎的比對也可以完全複用NFA的比對過程，是以對之前NFA的比對代碼，可以針對DFA模式取消回溯即可(不取消也沒問題，但會有性能影響)。
private boolean isMatch(String text, int pos, State curState) {
if (pos == text.length()) {
if (curState.isEndState()) {
return true;
}
for (State nextState : curState.next.getOrDefault(Constant.EPSILON, Collections.emptySet())) {
if (isMatch(text, pos, nextState)) {
return true;
}
}
return false;
}
for (Map.Entry<String, Set<State>> entry : curState.next.entrySet()) {
String edge = entry.getKey();
// 如果是DFA模式,不會有EPSILON邊
if (Constant.EPSILON.equals(edge)) {
for (State nextState : entry.getValue()) {
if (isMatch(text, pos, nextState)) {
return true;
}
}
} else {
MatchStrategy matchStrategy = MatchStrategyManager.getStrategy(edge);
if (!matchStrategy.isMatch(text.charAt(pos), edge)) {
continue;
}
// 周遊比對政策
for (State nextState : entry.getValue()) {
// 如果是DFA比對模式,entry.getValue()雖然是set,但裡面隻會有一個元素,是以不需要回溯
if (nextState instanceof DFAState) {
return isMatch(text, pos + 1, nextState);
}
if (isMatch(text, pos + 1, nextState)) {
return true;
}
}
}
}
return false;
} 因為DFA的比對不需要回溯，是以可以完全改成非遞歸代碼。
private boolean isDfaMatch(String text, int pos, State startState) {
State curState = startState;
while (pos < text.length()) {
boolean canContinue = false;
for (Map.Entry<String, Set<State>> entry : curState.next.entrySet()) {
String edge = entry.getKey();
MatchStrategy matchStrategy = MatchStrategyManager.getStrategy(edge);
if (matchStrategy.isMatch(text.charAt(pos), edge)) {
curState = entry.getValue().stream().findFirst().orElse(null);
pos++;
canContinue = true;
break;
}
}
if (!canContinue) {
return false;
}
}
return curState.isEndState();
} DFA和NFA引擎性能對比
我用jmh簡單做了一個非嚴格的性能測試，随手做的 看看就好，結果如下:
Benchmark Mode Cnt Score Error Units
RegexTest.dfaNonRecursion thrpt 2 144462.917 ops/s
RegexTest.dfaRecursion thrpt 2 169022.239 ops/s
RegexTest.nfa thrpt 2 55320.181 ops/s DFA的比對性能遠高于NFA，不過這裡居然遞歸版還比非遞歸版快，有點出乎意料， 詳細測試代碼已傳至Github
，歡迎查閱。