本文原文地址https://blog.csdn.net/xindoo/article/details/106458165

在上篇博客從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)* 為例，我在源碼https://github.com/xindoo/regex中加入了NFA輸出的代碼， a(b|c)* 的NFA輸出如下。

from to input0-> 1 a1-> 8 Epsilon8-> 9 Epsilon8-> 6 Epsilon6-> 2 Epsilon6-> 4 Epsilon2-> 3 b4-> 5 c3-> 7 Epsilon5-> 7 Epsilon7-> 9 Epsilon7-> 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

代碼實現

代碼其實就是對上文流程的表述，更多細節見https://github.com/xindoo/regex。

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的方式從已找到的起始節點遍歷并構建DFAqueue.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的集合,所以拼接成Stringprivate 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 https://github.com/xindoo/regex，歡迎查閱。

參考資料

• nfa轉dfa

總結

以上是生活随笔為你收集整理的dfa转正则表达式_从0到1打造正则表达式执行引擎(二)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。