（正則引擎已完成，Github）

最小化 DFA 是引擎中另外一個(gè)略繁瑣的點(diǎn)（第一個(gè)是構(gòu)建語(yǔ)法樹）。

基本思路是，先對(duì) DFA 進(jìn)行重命名，然后引入一個(gè)拒絕態(tài) 0，定義所有狀態(tài)經(jīng)過(guò)非接受字符轉(zhuǎn)到狀態(tài) 0，0 接受所有字符轉(zhuǎn)換為自身。也就是說(shuō)我們先建立一個(gè)轉(zhuǎn)換表，然后把第一行填寫為：

state	a	b	c	d	e	f	g	h	...
0	0	0	0	0	0	0	0	0	0

再之后，我們講 DFA 的其余狀態(tài)從 1 開始重命名，填入狀態(tài)表。代碼實(shí)現(xiàn)如下：

// rename all statesfor (Set<NFAState> nfaState : oriDFATransitionMap.keySet()) {if (initStateAfterRenaming == -1 && nfaState.equals(initClosure)) {initStateAfterRenaming = renamingStateID; // record init state id}stateRenamingMap.put(nfaState, renamingStateID++);}renamedDFATransitionTable.put(0, newRejectState()); // the reject state 0finalFlags.put(0, false);// construct renamed dfa transition tablefor (Map.Entry<Set<NFAState>, Map<Character, Set<NFAState>>> entry : oriDFATransitionMap.entrySet()) {renamingStateID = stateRenamingMap.get(entry.getKey());int[] state = newRejectState();for (Map.Entry<Character, Set<NFAState>> row : entry.getValue().entrySet()) {state[row.getKey()] = stateRenamingMap.get(row.getValue());}renamedDFATransitionTable.put(renamingStateID, state);if (entry.getKey().contains(finalNFAState)) {finalFlags.put(renamingStateID, true);} else finalFlags.put(renamingStateID, false);}

這里有一個(gè) finalFlags 用來(lái)記錄哪些 DFA 的終態(tài)包含了 NFA 的終態(tài) 1。（這些狀態(tài)都作為 DFA 的終態(tài)）

接下來(lái)，把所有狀態(tài)分為終態(tài)作為一個(gè) group，非終態(tài)作為另一個(gè) group：

// split states to final states and non-final statesMap<Integer, Integer> groupFlags = new HashMap<>();for (int i = 0; i < finalFlags.size(); i++) {boolean b = finalFlags.get(i);if (b) groupFlags.put(i, 0);else groupFlags.put(i, 1);}

我們定義任意 group 中的任意狀態(tài)的轉(zhuǎn)換規(guī)則為：接受某個(gè)字符轉(zhuǎn)移到某個(gè) group（區(qū)別于轉(zhuǎn)換到某個(gè)狀態(tài)）。

不停地遍歷所有的 group，把同一個(gè) group 中具有不同轉(zhuǎn)換規(guī)則的狀態(tài)分隔為不同的 group。

do { // splitting, group id is the final state idpreGroupTotal = groupTotal;for (int sensitiveGroup = 0; sensitiveGroup < preGroupTotal; sensitiveGroup++) {// <target group table, state id set>Map<Map<Integer, Integer>, Set<Integer>> invertMap = new HashMap<>();for (int sid = 0; sid < groupFlags.size(); sid++) { //use state id to iterateint group = groupFlags.get(sid);if (sensitiveGroup == group) {Map<Integer, Integer> targetGroupTable = new HashMap<>(CommonSets.ENCODING_LENGTH);for (char ch = 0; ch < CommonSets.ENCODING_LENGTH; ch++) {int targetState = renamedDFATransitionTable.get(sid)[ch];int targetGroup = groupFlags.get(targetState);targetGroupTable.put((int) ch, targetGroup);}Set<Integer> stateIDSet = invertMap.get(targetGroupTable);if (stateIDSet == null) {stateIDSet = new HashSet<>();invertMap.put(targetGroupTable, stateIDSet);}stateIDSet.add(sid); // gather all sids having the same target group table into this set}}boolean first = true;for (Set<Integer> stateIDSet : invertMap.values()) {if (first) {first = false;} else {for (int sid : stateIDSet) {groupFlags.put(sid, groupTotal);}groupTotal++;}}}} while (preGroupTotal != groupTotal);

如此分到不可再分，再把每一個(gè) group 中的所有狀態(tài)合并為同一個(gè)狀態(tài)，這樣我們就得到了 group 個(gè)狀態(tài)，就完成了 DFA 的最小化。

接著是再次確定整個(gè) DFA 的初態(tài)、終態(tài)和拒絕態(tài)。我們只要把包含這些狀態(tài)的 group 作為最小化之后的相應(yīng)狀態(tài)就可以了。

// determine initial group stateis = groupFlags.get(initStateAfterRenaming);// determine reject group staters = groupFlags.get(0);// determine final group statesSet<Integer> finalGroupFlags = new HashSet<>();for (int i = 0, groupFlagsSize = groupFlags.size(); i < groupFlagsSize; i++) {Integer groupFlag = groupFlags.get(i);if (finalFlags.get(i)) {finalGroupFlags.add(groupFlag);}}fs = new boolean[groupTotal];for (int i = 0; i < groupTotal; i++) {fs[i] = finalGroupFlags.contains(i);}

最后一步是把 DFA 轉(zhuǎn)換為一個(gè)以數(shù)組形式存放的狀態(tài)表，就可以用來(lái)進(jìn)行快速而準(zhǔn)確的正則匹配了。

// construct the final transition tabletransitionTable = new int[groupTotal][];for (int groupID = 0; groupID < groupTotal; groupID++) {for (int sid = 0; sid < groupFlags.size(); sid++) {if (groupID == groupFlags.get(sid)) {int[] oriState = renamedDFATransitionTable.get(sid);int[] state = new int[CommonSets.ENCODING_LENGTH];for (char ch = 0; ch < CommonSets.ENCODING_LENGTH; ch++) {int next = oriState[ch];state[ch] = groupFlags.get(next);}transitionTable[groupID] = state;break;}}}

至此，我們的整個(gè) DFA 正則表達(dá)式引擎就構(gòu)建完成了。

之后我用一個(gè) apache log 的正則做了一下性能測(cè)試，這個(gè)引擎的匹配速度比 JDK 自帶的正則要快至少一倍，還是有一定的實(shí)用性的，所以我把它放到了?Github?上，歡迎下載源碼。

個(gè)人水平有限，代碼中一定有不少尚待優(yōu)化的地方，如有建議請(qǐng)不吝賜教。

轉(zhuǎn)載于:https://www.cnblogs.com/zbdzzg/p/4509326.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的实现一个 DFA 正则表达式引擎 - 4. DFA 的最小化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。