精华内容
下载资源
问答
  • 需求背景 大家有没有做过屏蔽敏感词的需求呢,这个需求一般来说很常见了。比如,系统中有一段话: 我爱吃肯德基 要求【肯德基】三个词给屏蔽掉,屏蔽...在计算理论中,确定有限状态自动机或确定有限自动机(英语:

    需求背景

    大家有没有做过屏蔽敏感词的需求呢,这个需求一般来说很常见了。比如,系统中有一段话:

    我爱吃肯德基
    

    要求【肯德基】三个词给屏蔽掉,屏蔽后的语句显示为:

    我爱吃***
    

    常规的做法可能是查询敏感词库中的敏感词,循环每一个敏感词,然后去输入的文本中从头到尾搜索一遍,看是否存在此敏感词。

    但是如果敏感词很多,对于匹配也是很耗性能的。

    这里介绍使用DFA算法匹配敏感词,并进行处理。性能要优于常规处理方法。

    什么是DFA算法

    在计算理论中,确定有限状态自动机或确定有限自动机(英语:deterministic finite automaton, DFA)是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表E的字符,它都能根据事先给定的转移函数转移到下一个状态(这个状态可以是先前那个状态)。

    ——来自维基百科

    这里的确定意思为:状态以及引起状态转换的事件都是可确定的,不存在"意外"。有限指的是:状态以及事件的数量都是可穷举的。

    DFA算法在匹配关键字上面有广泛的应用。

    图片

    比如上面的关键词【肯德基】,【肯尼玛】。我们可以抽取成上面的树状模型。椭圆表示状态,状态与状态之间的连线叫事件。

    当然这里只是简单的介绍DFA是什么,想深入的童鞋可以看看这篇文章:

    常用的DFA最小化算法?- 知乎 -https://www.zhihu.com/question/39767421

    里面介绍了如何将正常数据构造成DFA形式。

    Java代码实战

    现在我们开始做一个示例吧

    现在我们指定了敏感词【"二愣子","二蛋","狗娃"】,我们按照上面的方式重新构造数据结构:

    图片

    如上图,我们构造了3组数据,每个节点有一个状态标记,1代表节点结束,也就是敏感词结束,0代表还未结束。

    数据结构Json形式如下:

    图片

    接下来就是如何实现代码了。

    首先我们将敏感词汇添加进入set集合中:

    private Set<String> readSensitiveWordFile() {
       Set<String> set = Sets.newHashSet();
       set.add("二愣子");
       set.add("二蛋");
       set.add("狗娃");
       return set;
    }
    

    当然,实际情况需要从数据库中读取,或者从文件中读取,然后在加载进入set集合。接下来我们将set中的数据重新构造成上面Json格式的,Java这里需要使用Map来存储。

    图片

    我们创建一个sensitiveWordMap来存储敏感词,这里实际就是map套map的过程,我们来调试看看map的结构:

    图片

    上面的数据结构Map是不是看晕了,其实就是我之前提到Json格式。

    图片

    在系统初始化时就将敏感词构造好。

    图片

    我们将敏感词的结构构造好后,就开始匹配句子了。

    图片

    如上代码,我们需要将句子中的字符一个一个的循环,如果(Map) nowMap.get(word) != null,说明匹配到了敏感词,这里如果isEnd的结束符为1,代表敏感词结束,即匹配到了一个敏感词。

    图片

    我们还会遇到上图的情况,【二蛋】是一个敏感词,【蛋疼】也是一敏感词。在【蛋】这个节点中,是【二蛋】的结束节点,是【蛋疼】的开始节点。我们通过代码:

    SensitiveWordFilter.minMatchTYpe == matchType
    

    判断,如果为true,我们在【蛋】结束之后就不再往下匹配,并将匹配到的index返回。之后再进入下一个循环了。反之。

    上面我们拿到匹配到的敏感词的index,接下来就要将句子中的敏感词显示出来了。

    图片

    我们将其存入set集合中:

    Set<String> sensitiveWordList = new HashSet<>();
    

    这里大家发现一个问题没有:

    获取敏感词index循环了一次txt句子,获取敏感词字符又循环了一次,大家有没有办法减少一次循环呢😀

    这个问题大家可以思考一下。

    然后我们将句子中的敏感词替换成指定的字符。

    图片

    比如我们将敏感词替换成 "*"。

    测试代码

    我们来测试下代码

    图片

    我们选取了《凡人修仙传》中的一段句子:

    "韩立被村里人叫作“二愣子”,可人并不是真愣真傻,反而是村中首屈一指的聪明孩子,但就像其他村中的孩子一样,除了家里人外,他就很少听到有人正式叫他名字“韩立”,倒是“二愣子”“二愣子”的称呼一直伴随至今。而之所以被人起了个“二愣子”的绰号,也只不过是因为村里已有一个叫“愣子”的孩子了。这也没啥,村里的其他孩子也是“狗娃”“二蛋”之类的被人一直称呼着,这些名字也不见得比“二愣子”好听了哪里去。"
    

    测试的结果为:

    图片

    关于DFA的思考

    这里我们将敏感词构造成map,相对于普通的方法,我们不用循环敏感词,直接用hash表的形式。效率会快很多。但是我们循环了两次句子txt,如果我们的句子很大,那就对性能有影响,如果我们的敏感词库很大,构建的map集合就会很大,这样就会很占用内存。

    进阶-一种基于AC自动机的高性能匹配算法

    关于DFA算法的问题,这里又有一种AC自动机的算法,也可以实现敏感词匹配。网上有关于AC自动机的论文,有兴趣的童鞋可以下载看看:

    PARA-AC:一种基于AC自动机的高性能匹配算法-AET-电子技术应用 -http://www.chinaaet.com/tech/designapplication/3000125061

    什么是AC自动机呢?

    AC自动机全称是Aho-CorasickAutoMaton,和Trie树一样是多模式字符串匹配算法。并且它与Trie树的关系就相当于KMP与BF算法的关系一样,AC自动机的效率要远远超出Trie树

    AC自动机对Trie进行了改进,在Trie的基础上结合了KMP算法的思想,在树中加入了类似next数组的失效指针。

    AC自动机的构建主要包含以下两个操作

    1. 将多个模式串构建成Trie树

    2. 为Trie树中每个节点构建失败指针

    图片

    AC自动机

    这里给大家推荐一个项目,基于AC自动机的高性能敏感词匹配:

    GitHub - toolgood/ToolGood.Words: 一款高性能敏感词(非法词/脏字)检测过滤组件,附带繁体简体互换,支持全角半角互换,汉字转拼音,模糊搜索等功能。-https://github.com/toolgood/ToolGood.Words

    感谢这个大佬提供的开源项目。

    敏感词构造的数据结构:

    图片

    封装的数据结构为

    图片

    匹配替换敏感词代码如下:

    图片

    代码中的TrieNode2为存储的敏感词结合构

    我们用AC自动机算法测试敏感词

    图片

    如上代码,test为我们要测试的句子,list为设置的敏感词,测试结果如下:

    图片

    我们对比DFA算法的耗时:

    图片

    AC自动机耗时低于1ms,而DFA自动机的耗时大于了1ms,当然这里只是初略的测试。需要有意义的性能测试还需要加大敏感词库和测试句子的量。

    好了,今天的文章到这里就结束了,文章介绍了AC与DFA两种算法屏蔽敏感词以及其性能,当然AC自动机的原理还是比较复杂的,本文就不做详细介绍了,有兴趣的同学可以多了解下相关知识。

    参考

    AC自动机:如何实现敏感词过滤? - https://blog.csdn.net/qq_35423154/article/details/109181973

    往期推荐

    扫码二维码,获取更多精彩。或微信搜Lvshen_9,可后台回复获取资料

    回复"java" 获取java电子书;
     
    回复"python"获取python电子书;
     
    回复"算法"获取算法电子书;
     
    回复"大数据"获取大数据电子书;
     
    回复"spring"获取SpringBoot的学习视频。
     
    回复"面试"获取一线大厂面试资料
     
    回复"进阶之路"获取Java进阶之路的思维导图
     
    回复"手册"获取阿里巴巴Java开发手册(嵩山终极版)
     
    回复"总结"获取Java后端面试经验总结PDF版
     
    回复"Redis"获取Redis命令手册,和Redis专项面试习题(PDF)
     
    回复"并发导图"获取Java并发编程思维导图(xmind终极版)

    另:点击【我的福利】有更多惊喜哦。

    展开全文
  • 编译原理之DFA自动机

    千次阅读 2015-03-18 18:58:37
    这便是常数的描述,这里边包含了无符号整数,带符号整数,实数
    
    
    
    
    
    
    
    
    
    
    
    
    
    这便是常数的描述,这里边包含了无符号整数,带符号整数,实数
    
    
    
    
    
    
    
    
    
    
    
    
    
    展开全文
  • 设计DFA是编译原理中非常重要的一环,在词法分析中占有很重要的地位。一般而言,我们会先求正则表达式,然后根据正则表达式来求DFA。所以,在设计DFA之前,首先要确保你的正规文法正确。 简单的正规表达式可以直接...

    1.前言

    设计DFA是编译原理中非常重要的一环,在词法分析中占有很重要的地位。一般而言,我们会先求正则表达式,然后根据正则表达式来求DFA。所以,在设计DFA之前,首先要确保你的正规文法正确。

    简单的正规表达式可以直接求出DFA,但是稍微复杂的就困难了。一般而言DFA的设计需要经过三步,第一步,设计符合要求的ε-NFA;第二步,转化成DFA;第三步(如果没要求可省略),DFA的化简

    2.算法

    2.1 ε-NFA设计

    ε-NFA的定义:非确定性有限自动机。条件:1.自动机在某个状态下读取一个符号后转移的状态不唯一;2.符号含ε(空转换,表示不读入任何符号就转换状态)。

    三种结构,分别是顺序、选择、循环,对应三个DFA模板:

    1.顺序结构

    2.选择结构,M1、M2是被选择部分。

    3.循环结构,M1是循环部分。

    按照这三个模板去实现正则表达式,然后你就会发现有很多ε和很多“无用”状态,正是这些边和顶点的加入才使得ε-NFA的设计变得直观。实际上,上述给出的模板足够严谨却没有极致精简,在例题中我们将进一步精简表达。

    2.2 ε-NFA转化DFA

    DFA定义:确定性有限自动机。条件:有限状态机在读取一个符号后转移的状态唯一

    根据定义,DFA里不会出现空转移,也不会出现某状态读取相同符号后转移到不同的状态。

    设原自动机ε-NFA={Pn,Vt,p1,pe,Q}.Pn为状态集合;Vt为转移符号xi集合(含ε);p1为开始状态;pe为终止状态;Q为转换规则。
    设转换后的自动机DFA={Sn,Vt,s1,se,Q}.Sn为新状态集合;Vt为转移符号(不含ε);s1为新开始状态;Se为新终止状态集合;Q为新的转换规则。
    1.S置为空。
    2.从p1开始记录所有ε可以转移到的状态,记为s1={P0,Pi,...,Pj},s1∈Sn.
    3.遍历Vt中所有非终结符。对于xi∈Vt(非终结符)记录下s1中状态能到达的状态集合,记为si={Pk,...Pj}。若si不为空,则si∈Sn。
    4.对3中S增添的新状态重复3的操作。
    5.反复执行3、4直到Sn不会增添新的元素。
    
    ps:
    对于新的DFA状态集合中元素si,如果含有原NFA的终止状态,则它是DFA的终止状态。
    DFA的状态转移函数在3中求过了,如s1->as2。

     如果算法看起来难懂,没关系,下面我们有例子进行详解。

    2.3 DFA的化简

    DFA的化简主要是进一步删除具有相同功能的状态以及无用状态

    删除相同功能的状态的依据是状态是否可区分。直接观察DFA有时也能看出来哪些状态“具有相同的功能”。大多时候很难直接找到哪些状态是“有相同功能”的,于是我们从反面出发,研究哪些状态是具有不同的功能(可区分)。

    设原自动机DFA={Pn,Vt,p1,pe,Q}.Pn为状态集合;Vt为转移符号xi集合(含ε);p1为开始状态;pe为终止状态;Q为转换规则。
    
    定义状态的可区分:如果两个状态(p1,p2)分别属于Kn和Pn-Kn,那么这两个状态(p1,p2)可区分;如果两个状态(p1,p2)都属于Kn或者Pn-Kn,但是分别读取一个相同的符号x后转移到的两个新状态(p3,p4)分别处于Kn和Pn-Kn中,那么这两个状态仍然可区分。
    
    根据可区分关系划分Pn的商集:
    1.首先划分两个集合Kn与Pn-Kn,这两个集合的元素互相可区分。
    2.对于剩下的、同处于相同集合的元素pi、pj执行:
      每次尝试读取一个转移符号xi,观察转移后的状态pi'、pj'是否处于Kn与Pn-Kn两个状态集合。如果是,就判定pi,pj这两个状态可区分,否则对pi、pj尝试一个新的转移符号。如果所有的转移符号都尝试完,这pi、pj依旧不可区分,那么pi、pj不可区分,记为pi≡pj。
    
    最终,记录下哪些状态对不可区分。
    

    3.例题&代码

    实现常数识别机:能够识别的数的形式包括整数、浮点数、科学计数。

    首先确定符合要求的正规表达式,大概是d+ [. d+ [ (e | E) (+ | -) d+ ] ]

    注意的一点是,这里我没有讨论识别负数,这是因为如果在常数识别这个任务识别了“-”,会给将来的语法分析带来麻烦。举例说:a-b,这个表达式在语法分析中是“《因式》《运算符》《因式》”的结构,也就是说结构合理。而如果过早识别了-,这个式子的结构就会变成“《因式》《因式》”,会被判错。所以,在常数识别的时候,不识别负数。

    制作一个符合要求的DFA(下图-1表示无效输入,如空格等)。

    然后根据DFA写一个简单的程序。

    string judgeConst(char &ch, ifstream &infile)
    {
        string str = "";
        int state = 0;
        bool flag = false;
        while (state != 7) //有限状态自动机,7为终止状态
        {
            switch (state)
            {
            case 0:
                if ((ch >= '0' && ch <= '9') || ch == '-')
                {
                    state = 1;
                    str += ch;
                    infile >> ch;
                }
                break;
            case 1:
                if (ch >= '0' && ch <= '9')
                {
                    state = 1;
                    str += ch;
                    infile >> ch;
                }
                else if (ch == 'e' || ch == 'E')
                {
                    state = 4;
                    str += ch;
                    infile >> ch;
                }
                else if (ch == '.')
                {
                    state = 2;
                    str += ch;
                    infile >> ch;
                }
                else
                {
                    state = 7;
                    flag = true;
                }
                break;
            case 2:
                if (ch >= '0' && ch <= '9')
                {
                    state = 3;
                    str += ch;
                    infile >> ch;
                }
                break;
            case 3:
                if (ch == 'e' || ch == 'E')
                {
                    state = 4;
                    str += ch;
                    infile >> ch;
                }
                else if (ch >= '0' && ch <= '9')
                {
                    state = 3;
                    str += ch;
                    infile >> ch;
                }
                else
                {
                    flag = true;
                }
                break;
            case 4:
                if (ch == '+' || ch == '-')
                {
                    state = 5;
                    str += ch;
                    infile >> ch;
                }
                else if (ch >= '0' && ch <= '9')
                {
                    state = 6;
                    str += ch;
                    infile >> ch;
                }
                break;
            case 5:
                if (ch >= '0' && ch <= '9')
                {
                    state = 6;
                    str += ch;
                    infile >> ch;
                }
                break;
            case 6:
                if (ch >= '0' && ch <= '9')
                {
                    state = 6;
                    str += ch;
                    infile >> ch;
                }
                if (ch < '0' || ch > '9')
                {
                    state = 7;
                }
                break;
            case 7:
                flag = true;
                break;
            }
            if (flag)
                break;
        }
        return str;
    }

     

    展开全文
  • 自动机可以写成 M=(K,Σ,δ, q0 ,F) 的五元组形式,其中 K 表示自动机的所有状态组成的集合;Σ 表示字母表集合, δ 表示状态转移函数, q0 自动的初始状态, F 为自动机的结束状态集。 例如: 注意...

    版权声明:本文为博主原创文章,未经博主允许不得转载。https://blog.csdn.net/qq_38812171


    1.自动机的概念:

    自动机用于识别满足特定文法的串。自动机可以写成 M=(K,Σ,δ, q0 ,F) 的五元组形式,其中 K 表示自动机的所有状态组成的集合;Σ 表示字母表集合, δ 表示状态转移函数, q0 自动的初始状态, F 为自动机的结束状态集。

    例如:

    注意: 在自动机的实现中,最主要的就是考虑状态转移函数的表示,在此我构造了一个状态转换表来存储所有的状态转移过程!

     

    当然也可以用压缩变换表的方式,其实就是一个简单的链表,因为每个状态不可能对所有字符都有状态转换函数!

    有了状态转换表,加上控制程序就可以简单实现一个小型DFA了!

    控制程序如下:

    2. Java 实现 一个小DFA

       2.1 状态转换图:

      

       2.2 包

                                                        

    2.3 状态转移函数

    2.4 控制程序

    2.5 main 函数

    展开全文
  • 产品-Dfa 自动机项目 特征 产品 DFA 计算 产品 DFA 决策属性实现,即包含、差异等。 专有的基于 GUI 额外功能:语言生成、语言无限性检查
  • 设计、编制、调制一个具体的词法分析程序,加深对词法分析原理的理解,编译原理DFA的实验报告和代码,请需要的下载。这是个测试字符和字符串的实验代码,请斧正,通过理解正规式、有限自动机原理,编制一个词法分析...
  • dfa确定有限自动机定义In Deterministic Finite Automata (DFA), for a given input symbol the machine will move to which next state can be determined and hence it is named as deterministic automata....
  • 一,算法:从NFA构造DFA(子集法) 输入: 一个NFA N 输出 : 一个接受同一正规集的DFA D # 构造NFA class NFA: # 初始化NFA def __init__(self, S, s0, F, move): self.S = S # 状态集(list) self.s0 =...
  • 有限自动机DFA

    2014-03-07 14:34:17
    Java实现有限自动机相关功能的工具包,包含:正则式与NFA,DFA的相互转化;DFA的交、并、差、补运算;判断一个DFA对应的正则集是否是无限集;列出一个有限正则集所包含的所有字符串,以及包含字符串的最小长度和最大...
  • 使用Java模拟DFA 有穷自动机的执行过程。给出一个字符,判断是否能够被接受 使用Java模拟DFA 有穷自动机的执行过程。给出一个字符,判断是否能够被接受
  • 确定有限自动机DFA&非确定有限自动机NFA Part 1_自动机介绍:有穷自动机(finite state automata)是一个识别器,它对每个输入的字符做识别和判断,以确定其能到达的最终状态或状态集和路径,有穷自动机分为两类,...
  • 给定由若干 0 和 1 组成的数组 A。我们定义 N_i:从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数(从最高有效位到最低有效位)。 返回布尔值列表 answer,只有当 N_i 可以被 5 整除时,答案 answer[i] 为 ...
  • 确定自动机DFA 定义: 两种表示方式 状态转换图 三种节点:终止状态,非终止状态,开始状态 边:状态转换函数 举例: 状态转换矩阵 概括:用二维数组的方式表示状态机 注意:右上角+号代表初始状态,右上角...
  • 在计算理论中,确定有限状态自动机或确定有限自动机(英语:deterministic finite automaton, DFA)是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符,它都能根据...
  • A - Non Absorbing DFA Time Limit: 10000/5000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others) SubmitStatus Problem Description  In the theory of compilers and languages fini
  • 有穷自动机DFA

    2015-12-06 22:29:59
    DFA.java 中的DFA 类实现成员函数boolean recongnizeString(int move[][], int accept_state[], String word)
  • 自动机 DFA java程序

    2014-11-17 03:06:57
    输入DFA的信息和两个trace。 给出一个accept和一个reject
  • 自动机初步之DFA

    千次阅读 2016-08-02 16:12:36
    这里提到的自动机特指有限状态自动机,简称为FA,根据状态转移的性质又分为确定的自动机DFA)和非确定的自动机(NFA)。FA的表达能力等价于正规表达式或者正规文法。FA可以看做是一个有向带权图,图的顶点集合称为...
  • 确定有限自动机DFA

    2020-12-29 18:07:31
    文章目录场景举例cp官解 场景 确定有限状态机定义: ...这个问题是个典型的dfa的用法 请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空
  • C语言 确定有限状态自动机 DFA

    千次阅读 2018-06-18 02:00:14
    确定有限状态自动机简介 实现过程 实现分析 代码实现 ...确定有限状态自动机简介 ...关于什么是DFA,可参考链接:有穷自动机DFA&amp;NFA 本篇的主要目的是实现DFA。 实现过程 下面是一个字符串ABABAC的DF...
  • 下列是判断某个语法是否是DFA有穷自动机代码的一个例子,判断的例子如图下图: import java.util.*; public class DFA { char startState; //保存开始符 char[] test; //保存非终结符a,b,c,d char[] state; //...
  • BUPT 自动机实验,NFA转化DFA,java代码加实验报告
  • 形式语言与自动机的实验课资源,是描述DFA的检测的。
  • 一、非确定性有限自动机 ( NFA ) 转为 确定性有限自动机 ( DFA )、 二、转换方法与要点
  • 一个方便的工具,可以可视化将正则表达式(RE)转换为不确定性自动机(NFA),确定性自动机DFA)和最小化确定性自动机(min-DFA)的过程。 要求 Graphviz Networkx matplotlib 目的 更深入地了解生成NFA , DFA...
  • 从信息论的角度给出了解释,并提出多维数学模型,将冗余状态分为0维状态和1维状态,通过前者按照维度压缩,后者动态构建的方法将空间复杂度降到理论下界,并在此基础上提出多维有限自动机(MFA,multi-dimensional ...
  • 敏感词过滤算法DFA-确定有穷自动机 DFA全称为:Deterministic Finite Automaton , 即确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,115
精华内容 446
关键字:

dfa自动机