DFA算法的简单说明与案例实现以及优化思路

1.背景

项目中需要对敏感词做一个过滤，首先有几个方案可以选择：

a.直接将敏感词组织成String后，利用indexOf方法来查询。

b.传统的敏感词入库后SQL查询。

c.利用Lucene建立分词索引来查询。

d.利用DFA算法来进行。

首先，项目收集到的敏感词有几千条，使用a方案肯定不行。其次，为了方便以后的扩展性尽量减少对数据库的依赖，所以放弃b方案。然后Lucene本身作为本地索引，敏感词增加后需要触发更新索引，并且这里本着轻量原则不想引入更多的库，所以放弃c方案。于是我们选定d方案为研究目标。

2.DFA算法简介

DFA全称为：Deterministic Finite Automaton,即确定有穷自动机。其特征为：有一个有限状态集合和一些从一个状态通向另一个状态的边，每条边上标记有一个符号，其中一个状态是初态，某些状态是终态。但不同于不确定的有限自动机，DFA中不会有从同一状态出发的两条边标志有相同的符号。

简单点说就是，它是是通过event和当前的state得到下一个state，即event+state=nextstate。理解为系统中有多个节点，通过传递进入的event，来确定走哪个路由至另一个节点，而节点是有限的。

3.敏感词搜寻中的DFA算法

3.1敏感词库构造描述

以王八蛋和王八羔子两个敏感词来进行描述，首先构建敏感词库，该词库名称为SensitiveMap，这两个词的二叉树构造为：

用hash表构造为：

3.2基于敏感词库收索算法的描述

以上面例子构造出来的SensitiveMap为敏感词库进行示意，假设这里输入的关键字为：王八不好，流程图如下：

4.代码编写

4.1构造敏感词实现代码

4.2实现敏感词查询代码

4.3API预览

4.3.1 敏感词替换

String text = "我们决定紧急征调5000人前往宅区帮助灾民，并且决定为紧急事件打开绿灯";filter.replace(text);

4.3.2. 是否包含敏感词

String text = "我小时候有个朋友叫张三，现在和他几乎没联系了";filter.include(text);

4.3.3. 获取敏感词数

String text = "我小时候有个朋友叫张三，现在和他几乎没联系了";int result = filter.wordCount(text);

4.3.4. 获取敏感词列表

String text = "我小时候有个朋友叫张三，现在和他几乎没联系了";List<String> words = filter.wordList(text);

4.3.5. 增加白名单功能

- blacklist.txt- whitelist.txt

4.3.6. 增加方法重载

- replace(final String text) // distance=0&symbol=*- replace(final String text, final char symbol) // distance=0- include(final String text) // distance=0- wordCount(final String text) // distance=0- wordList(final String text)// distance=0

4.3.7. 增加在线添加敏感词方法

//此处将5000加入黑名单context.addWord(Collections.singletonList("5000"), WordType.BLACK);

4.3.8、增加在线删除敏感词方法

//此处将5000移出黑名单（若黑名单没有该词组将忽略）context.removeWord(Collections.singletonList("5000"), WordType.BLACK);//此处将紧急事件移出白名单（若白名单没有该词组将忽略）context.removeWord(Collections.singletonList("紧急事件"), WordType.WHITE);