共计 5998 个字符,预计需要花费 15 分钟才能阅读完成。
本文原文地址 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 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
代码实现
代码其实就是对上文流程的表述,更多细节见 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 的方式从已找到的起始节点遍历并构建 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 https://github.com/xindoo/regex,欢迎查阅。
参考资料
- nfa 转 dfa
本文由博客一文多发平台 OpenWrite 发布!