- 综合排序
- 最热优先
- 最新优先
- 来自专栏Java架构师必看
DFA和NFA
2.DFA和NFA 引用 理解DFA和NFA 正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。 DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。 DFA与NFA机制上的不同带来5个影响： 1. 如果是DFA，它是以文本为导向，手里捏着文本，眼睛看着正则式，一口一口的吃。吃到/p/，就在手里的 ‘p’ 上打一个钩，记上一笔，说这个字符已经匹配上了，然后往下吃。 通过以上例子，可以理解为什么NFA是最左子式匹配，而DFA是最长左子式匹配。实际上，如果仔细分析，关于NFA和DFA的不同之处，都可以找出道理。
1.1K20发布于 2021-07-13 - 来自专栏PHP学习网
PHP DFA算法实现敏感词过滤包 php-dfa-sensitive
DFA算法（确定有穷自动机） 安装包地址：https://packagist.org/packages/lustre/php-dfa-sensitive github地址：https://github.com /FireLustre/php-dfa-sensitive 安装扩展 composer require lustre/php-dfa-sensitive 引人 use DfaFilter\SensitiveHelper
2.1K10编辑于 2022-12-17 - 来自专栏全栈程序员必看
DFA算法简单理解实现
背景：因为最近项目要使用到敏感词过滤服务，在网上了解到dfa实现这个功能性能还不错，特此学习了一下 1. 什么是DFA算法 引用 简书作者：浪人与酒丶的解释 原文链接：https://www.jianshu.com/p/c67f917c9363 DFA全称为：Deterministic Finite 但不同于不确定的有限自动机，DFA中不会有从同一状态出发的两条边标志有相同的符号。 确定：状态以及引起状态转换的事件都是可确定的，不存在“意外”。 有穷：状态以及事件的数量都是可穷举的。 DFA算法模型 state_event_dict = { "匹": { "配": { "算": { 通过java程序加载敏感词库，构建一个DFA算法模型 private static void addSensitiveWordToHashMap(Set<String> keyWordSet) {
2.1K11编辑于 2022-07-23 - 来自专栏姓王者的博客
编译原理:NFA转DFA
DFA 确定有限自动机(Deterministic Finite Automaton,DFA)是一种计算模型,常用于模式匹配、词法分析等领域。 定义 一个 DFA 可以用一个五元组 (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F)(Q,Σ,δ,q0,F) 来表示,其中： QQQ 是一个有限的状态集合。 也就是说,对于当前状态和输入符号,DFA 有唯一的下一个状态。 q0q_0q0 是初始状态,q0∈Qq_0 \in Qq0∈Q。 FFF 是接受状态集合,F⊆QF \subseteq QF⊆Q。 工作原理 DFA 从初始状态开始,根据输入符号和状态转移函数不断地转移状态。当输入字符串处理完毕后,如果 DFA 处于接受状态集合中的某个状态,则认为该字符串被 DFA 接受；否则,该字符串被拒绝。 ： 通过以上步骤,我们成功地将 NFA 转换为了 DFA。
63110编辑于 2025-03-26 - 来自专栏JMCui
利用 DFA 算法实现文字过滤
一、DEA 算法简介 在实现文字过滤的算法中，DFA是唯一比较好的实现算法。 DFA 全称为：Deterministic Finite Automaton，即确定有穷自动机。 但不同于不确定的有限自动机，DFA 中不会有从同一状态出发的两条边标志有相同的符号。 ? /** * 读取敏感词库，将敏感词放入HashSet中，构建一个DFA算法模型 * * @param keyWordSet 敏感词库 */ public
1.9K10发布于 2019-11-27 - 来自专栏龙进的专栏
编译原理:DFA的最小化
书本上关于DFA最小化的方法的文字说明比较晦涩,因此在这里举个实例来说明. 题目:最小化下图所示的DFA 1.写出DFA的状态转换矩阵 2.初始状态划分 把所有状态按照”是否为终结状态”,划分为2个集合: 3.考察每个元素数量大于2的集合 判断这些集合的元素经过推导后,所到达的状态的集合 在经过切分后,当前所有集合变为{1,2}{3}{4}{5}{6,7} 再进行验证可发现,到这一步为止,不再有新的切分,因此切分完成. 4.重命名状态,画出新的转换矩阵及DFA 重命名: 新的转换矩阵, 最小化后的DFA:
1.8K30编辑于 2023-10-18 - 来自专栏全栈程序员必看
dfa算法c语言,用c语言采用模拟dfa算法编写一个扫描器.docx
用C语言米用模拟DFA算法编写一个扫描器 /* 第一章：相关知识 DFA定义：一个确定的有穷自动机(DFA) M是一个五元组：M= ( K,厶f, S, Z)其中 0K是一个有穷集，它的每个元素称为一个状态 第二章：题目 用C语言米用模拟DFA算法编写一个扫描器(词法分析器)用来识别： 由任意个a或b开始后接aa再自加或自减1的字符串，即正规式r=(a|b)*aa(+|-)1描述的语 言 L (r) 该词法分析器的任务
1.3K20编辑于 2022-07-23 - 来自专栏用户10805953的专栏
LeetCode 65：有效数字 DFA自动机解法
（需求都不好好提，这样的甲方还是刷上面包糠带到河边吧） 最后，我弄出了这样的DFA图 图片 其中，1 3 4 6 9 是可接受状态，0是初始状态~ 然后就快乐的跑起来咯~ D是指数字，这个可以先转换一下再跑 DFA，最后跑出了0ms的效果，也有可能LeetCode日常抽风~~ 图片 代码放这咯~ #include <string> #include <vector> #include <algorithm>
30810编辑于 2023-10-26 - 来自专栏小樱的经验随笔
简单的词法设计——DFA模拟程序
实验一、简单的词法设计——DFA模拟程序 一、实验目的 通过实验教学，加深学生对所学的关于编译的理论知识的理解，增强学生对所学知识的综合应用能力，并通过实践达到对所学的知识进行验证。 通过对 DFA 模拟程序实验，使学生掌握词法分析的实现技术，及具体实现方法。通过本实验加深对词法分析程序的功能及实现方法的理解 。 三、实验内容 1、自己定义一个 DFA 或者一个右线性正规文法 示例如(仅供参考) G[S]：S→aU|bV U→bV|aQ V→aU|bQ Q→aQ|bQ|e 2、利用合适数据结构存储自动机，如 ? 设计思路：我们主要是用 Java 语言实现词法分析的过程，需要处理 DFA 和 NFA 两种状态，所以在文末我们给出了测试样例以及测试截图，部分代码给出了详细的注释。 edge [PriorityState=" + PriorityState + ", ch=" + ch + ", NextState=" + NextState + "]"; } } /**DFA
2.2K30发布于 2019-01-07 - 来自专栏计算机视觉与深度学习基础
Leetcode 65 Valid Number DFA有限状态机
用有限状态机DFA解决，将每一位看成一种状态转移条件，每次读取的一位，就根据转移矩阵进行状态转移，若转移到不合法的状态则返回false。
1.1K60发布于 2018-01-12 - 来自专栏CSDN搜“看，未来”
【C++】算法集锦（11）：敏感词过滤算法（DFA）
文章目录 什么是 确定的、有穷状态、机 跟我一起看个栗子 DFA图解 DFA示例实现代码 DFA：确定的 有穷 状态机 如果 设计模式 中的状态模式比较熟的话，这个就很清楚了。 DFA常用于敏感词过滤。 ---- 什么是 确定的、有穷状态、机 啊，看这个名字，就通俗易懂了嘛。首先它是个机，干嘛用的机我说一下：模式串筛选用的机。 我觉得，DFA的机制很适合用于动态流程图的实现，特别是复杂的，动态流程图。当然，动态流程图是可以暴力硬写的，就是代码肥了点而已。 ---- DFA图解 我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s’。 ---- DFA示例实现代码 #include<iostream> #include<vector> using namespace std; int DFA(vector<char>& cvec
1K20发布于 2021-09-18 - 来自专栏Coding迪斯尼
自己动手写编译器:从NFA到DFA
节点记作DFA state 3, move({10, 20, 9,12,13,21}, . } = {14, 22} 于是我们再产生新的DFA节点记作DFA state 4,于是就有: 这个过程以此类推 接下来看看代码如何实现，我们添加一个名为nfato_dfa.go的文件，然后添加代码如下： go import "fmt" const ( DFA_MAX = 254 //DFA 最多节点数 在上面代码中我们定义了DFA节点，由于一个DFA节点由一组NFA节点转换而来，因此在它的定义中有一个NFA节点的指针数组。 DFA节点编号，dstates用于存储当前已经创建了的DFA节点。 DFA) { fmt.Printf(“DFA state : %d, it is nfa are: {“, dfa.state) for , nfa := range dfa.set { fmt.Printf
1K20编辑于 2023-02-26 - 来自专栏iOS代码混淆
算法-DFA算法-敏感词过滤算法（OC、Swift、Python）
一般的思路可能是遍历敏感词库，然后把一段文字的敏感词过滤掉，但是针对比较大的词库时（比如我们的敏感词库10万），这样非常耗时和耗内存，在电脑上还能跑跑，但是在手机上分分钟钟被系统杀死掉，这样肯定是不行的，这里就用到一种DFA 但是使用了DFA算法，十万的敏感词库过滤一句话只需要【0.434510秒】！ 2019-10-23 14:34:08.316380+0800 DFAFilterDemo[4728:4650502] 总共耗时: 0.434510 DFA算法 简介 何谓DFA，它的全称是Deterministic 但不同于不确定的有限自动机，DFA中不会有从同一状态出发的两条边标志有相同的符号；DFA算法的核心是建立了以敏感词为基础的许多敏感词树。 过滤算 ---------- import time time1 = time.time() class DFAFilter(object): """DFA过滤算法""" def __init_
6.7K10发布于 2019-10-23 - 来自专栏java老实人
python实现DFA模拟程序(附java实现代码)
DFA（确定的有穷自动机） 一个确定的有穷自动机M是一个五元组： M=(K，∑，f，S，Z) K是一个有穷集，它的每个元素称为一个状态。 代码实现 -*- coding: utf-8 -*- # #@author: chlinlearn #@createTime: 2019/4/13 14:12 #@fileName: DFA class DFA(): def __init__(self): #状态集 self.listEdge = [] #初态 self.S print("再次判断请输入字符串(退出程序输入#):") if __name__ == '__main__': DFA = DFA() DFA.input() DFA.judgeDFA (); DFA.judeDFA(); } }
78820编辑于 2022-05-10 - 来自专栏小石头记
sensitive-words 基于DFA算法实现的敏感词过滤算法
在实现文字过滤的算法中，DFA是唯一比较好的实现算法。 DFA 全称为：Deterministic Finite Automaton，即确定有穷自动机。 但不同于不确定的有限自动机，DFA 中不会有从同一状态出发的两条边标志有相同的符号。 二、 DFA 算法实践敏感词过滤 敏感词库构造 以王八蛋和王八羔子两个敏感词来进行描述，首先构建敏感词库，该词库名称为SensitiveMap，这两个词的二叉树构造为： [20211116231237
2.3K20发布于 2021-11-16 - 来自专栏小工匠聊架构
OpenSource - 基于 DFA 算法实现的高性能 java 敏感词过滤工具框架
sensitive-word sensitive-word 基于 DFA 算法实现的高性能敏感词工具。 The sensitive word tool for java. 基于 DFA 算法实现的高性能 java 敏感词过滤工具框架。请勿发布涉及政治、广告、营销、翻墙、违反国家法律法规等内容。 基于 DFA 算法实现，目前敏感词库内容收录 6W+（源文件 18W+，经过一次删减）。 后期将进行持续优化和补充敏感词库，并进一步提升算法的性能。 特性 6W+ 词库，且不断优化更新 基于 fluent-api 实现，使用优雅简洁 基于 DFA 算法，性能为 7W+ QPS，应用无感 支持敏感词的判断、返回、脱敏等常见操作 ; Assert.assertTrue(wordBs.contains(text)); 备注：init() 对于敏感词 DFA 的构建是比较耗时的，一般建议在应用初始化的时候只初始化一次。
73700编辑于 2024-05-25 - 来自专栏前端之旅
编译原理学习笔记-4：词法分析(二)等价转换与DFA的化简
确定有限自动机的化简 在上一篇笔记中，将非确定有限自动机 NFA 确定化之后，得到了确定有限自动机 DFA，接下来考虑 DFA 的化简。 DFA 的化简指的是找到这么一个 DFA，它的状态数比原 DFA 更少，但是整体与原 DFA 是等价的。 用一个例子来说明： image.png 将这个 DFA 进行化简的步骤是这样的： ① 划分非终态集和终态集： 根据非终态和终态，划分出了两个集合：{1,2,3,4} 和 {5,6,7}。 最终化简得到的 DFA 如下： image.png 注意： DFA 化简之后一定要进行检查，确定每一个状态集合的每一个状态经过 ab 后到达的状态的集合都是当前已划分集合的子集。
4.5K42发布于 2020-04-26 - 来自专栏DearXuan的博客文章
DFA算法-简易Java敏感词过滤(含源文件和上万敏感词列表)
敏感词过滤说白了就是简单的字符串替换，Java本身已经提供了相关函数，但是一旦遇到长文本，或者敏感词数量庞大，效率下降就会非常明显。本文将介绍利用多叉树进行敏感词存储和过滤的方法。
8.8K33编辑于 2022-01-19 - 来自专栏CSDN搜“看，未来”
确定的有穷状态机（DFA） -- 你来看也能懂的C++代码示例
我觉得，DFA的机制很适合用于动态流程图的实现，特别是复杂的，动态流程图。当然，动态流程图是可以暴力硬写的，就是代码肥了点而已。 跟我一起看个栗子 这也是我最初接触到DFA的栗子，当时我就是暴力硬写，当然，代码肥的我都没脸贴当时那篇博客里去。 请你来实现一个 atoi 函数，使其能将字符串转换成整数。 DFA图解 我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s’。 DFA示例实现代码 #include<iostream> #include<vector> using namespace std; int DFA(vector<char>& cvec) { vector<vector<int>> vec = { {0,1,2,3},{3,3,2,3},{3,3,2,3},{3,3,3,3} }; //DFA int stat = 0;//实时状态，初始化为
1.6K10发布于 2020-08-26 - 来自专栏Lvshen的技术小屋
使用DFA自动机算法屏蔽敏感词以及进阶算法AC自动机的思考
这里介绍使用DFA算法匹配敏感词，并进行处理。性能要优于常规处理方法。 什么是DFA算法 “在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。 当然这里只是简单的介绍DFA是什么，想深入的童鞋可以看看这篇文章： “常用的DFA最小化算法？ 进阶-一种基于AC自动机的高性能匹配算法 关于DFA算法的问题，这里又有一种AC自动机的算法，也可以实现敏感词匹配。 算法的耗时： AC自动机耗时低于1ms，而DFA自动机的耗时大于了1ms，当然这里只是初略的测试。
4.3K10编辑于 2022-05-05
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号