dfa算法(dfa算法)

女爷i 2023-09-26 11:57 57阅读 0赞

### dfa和nfa的基本概念及其区别? ###

基本概念：

1. 确定有限自动机(Deterministic Finite Automaton) 简称DFA。dfa是匹配速度，是确定的。

2. 非确定有限自动机(Nondeterministic Finite Automaton) 简称NFA,nfa是匹配结果，是不确定的。

1. DFA比较快，但不提供Backtrack(回溯)功能，NFA比较慢，但提供了Backtrack功能。

2. NFA是基于表达式的(Regex-Directed)，而DFA是基于文本的(Text-Directed)。

3. DFA引擎在任意时刻必定处于某个确定的状态，而NFA引擎可能处于一组状态之中的任何一个，所以，NFA引擎必须记录所有的可能路径(trace multiple possible routes through the NFA)，NFA之所以能够提供Backtrack的功能，原因就在这里。dfa或nfa是对计算机程序的行为的抽象模型。你编写的程序其实就对应了一个自动机。简单举例来说，如果a,b可以取值0或1; 程序： if(a==1) b=1;这个程序对应了一个自动机。

对应的自动机就有状态 (0,0), (0,1), (1,1), (1, 0)

比如你自动机的初始状态是 (1,0)即a=1,b=0时，运行程序的下一个状态就是(1,1)。

画图出来就是 这4个状态作为顶点，并且有下面几条边

(0,0) --> (0,0)(自环),(1,0)-->(1,1),(1,1)-->(1,1)(自环), (0,1)-->(0,1)自环

存在的意义就是一种理论模型，也可以认为是一种编程思想。词法分析系也离不开 if else， 这一系列的if else和条件也就组成自动机。。。

最经典体现自动机思想的算法就是kmp算法，你肯定学过，字符串子串匹配的算法。 回忆这个算法的过程：算法第一步构造的next表(数据结构教材的说法)其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。

![dfa算法(dfa算法)\_dfa算法(dfa算法)][dfa_dfa_dfa_dfa]

### dfa和nfa的基本概念及其区别? ###

基本概念：

1. 确定有限自动机(Deterministic Finite Automaton) 简称DFA。dfa是匹配速度，是确定的。

2. 非确定有限自动机(Nondeterministic Finite Automaton) 简称NFA,nfa是匹配结果，是不确定的。

1. DFA比较快，但不提供Backtrack(回溯)功能，NFA比较慢，但提供了Backtrack功能。

2. NFA是基于表达式的(Regex-Directed)，而DFA是基于文本的(Text-Directed)。

3. DFA引擎在任意时刻必定处于某个确定的状态，而NFA引擎可能处于一组状态之中的任何一个，所以，NFA引擎必须记录所有的可能路径(trace multiple possible routes through the NFA)，NFA之所以能够提供Backtrack的功能，原因就在这里。dfa或nfa是对计算机程序的行为的抽象模型。你编写的程序其实就对应了一个自动机。简单举例来说，如果a,b可以取值0或1; 程序： if(a==1) b=1;这个程序对应了一个自动机。

对应的自动机就有状态 (0,0), (0,1), (1,1), (1, 0)

比如你自动机的初始状态是 (1,0)即a=1,b=0时，运行程序的下一个状态就是(1,1)。

画图出来就是 这4个状态作为顶点，并且有下面几条边

(0,0) --> (0,0)(自环),(1,0)-->(1,1),(1,1)-->(1,1)(自环), (0,1)-->(0,1)自环

存在的意义就是一种理论模型，也可以认为是一种编程思想。词法分析系也离不开 if else， 这一系列的if else和条件也就组成自动机。。。

最经典体现自动机思想的算法就是kmp算法，你肯定学过，字符串子串匹配的算法。 回忆这个算法的过程：算法第一步构造的next表(数据结构教材的说法)其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。

[dfa_dfa_dfa_dfa]: https://img2.baidu.com/it/u=2353016592,2072562144&fm=26&fmt=auto

发表评论取消回复

表情：

评论列表（有 0 条评论，57人围观）

还没有评论，来说两句吧...

相关阅读

相关基于DFA算法的敏感词检测算法

敏感词检测，几乎是所有博客、文章、日志等这类公开性发表的以文字形式记录的作品都绕不过去的产品需求，那么，是否有一些比较高效的方法来检测文章的敏感词呢？`DFA算法`，全称...

野性酷女/ 2024年04月17日 06:15/ 0 赞/ 81 阅读

相关 Java使用DFA算法实现敏感词过滤

1 前言敏感词过滤就是你在项目中输入某些字（比如输入xxoo相关的文字时）时要能检测出来，很多项目中都会有一个敏感词管理模块，在敏感词管理模块中你可以加入敏感词，然后根

怼烎@/ 2023年10月04日 22:27/ 0 赞/ 34 阅读

相关 dfa算法(dfa算法)

dfa和nfa的基本概念及其区别? 基本概念： 1. 确定有限自动机(Deterministic Finite Automaton) 简称DFA。dfa是匹配速度，是确

女爷i/ 2023年09月26日 11:57/ 0 赞/ 58 阅读

相关 dfa与ndfa_DFA和NDFA之间的区别| 目录

dfa与ndfa DFA stands for Deterministic Finite Automata and NDFA stands for Non-Determini

﹏ヽ暗。殇╰゛Y/ 2023年03月05日 09:57/ 0 赞/ 23 阅读

相关 java基于Map实现DFA算法

package com.yangkaile.generator; import lombok.extern.slf4j.Slf4j; impo

快来打我*/ 2022年08月31日 15:25/ 0 赞/ 229 阅读

相关 DFA算法的简单说明与案例实现

1.背景项目中需要对敏感词做一个过滤，首先有几个方案可以选择： a.直接将敏感词组织成String后，利用indexOf方法来查询。 b.传统的敏感词入库后SQL查

我不是女神ヾ/ 2022年06月13日 10:17/ 0 赞/ 218 阅读

相关 Java利用DFA算法实现敏感词过滤

前言：敏感词文字过滤是一个网站必不可少的功能，如何设计一个好的、高效的过滤算法是非常有必要的。作为一般开发人员来说首先考虑的肯定是简单的匹配，这样是可以实现功能，但效率

逃离我推掉我的手/ 2022年05月08日 11:34/ 0 赞/ 262 阅读

相关利用DFA算法实现敏感词过滤（java）

1、问题描述当初找实习面试时一面试官问一段话如何判断其中是否包含敏感词，当时经验跟能力不足，也只能想到使用正则表达式或者双重循环蛮力实现，但是肯定不能满足要求。现在工

小咪咪/ 2022年03月31日 15:16/ 0 赞/ 724 阅读

相关 DFA算法实现的敏感词过滤器

遇到一个过滤敏感词的需求,根据网上查询的资料整理了一下,代码如下 import java.io.BufferedReader; import java.io.

梦里梦外;/ 2022年03月18日 15:27/ 0 赞/ 284 阅读

相关 DFA与NFA

正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。两类引擎要顺利工作，都必须有一个正则式和一个文本串，一个捏在手里，一

小咪咪/ 2021年06月24日 15:58/ 0 赞/ 358 阅读