一、DFA

敏感词过滤其实是模式匹配问题，目前比较高效的计算模型是DFA。匹配过程主要依赖状态的转移而不是复杂的计算，从而提高了速度。

DFA的基本功能是可以通过当前的state和event得到下一个state，即δ(state, event)=next_state，下列状态转换图展现了一个DFA的状态转移过程：

当然，该过程还有其他表示方式，比如说矩阵表示：

	a	b
S	U	V
U	U	V
V	U	Q
Q	Q	Q

本文将使用字典树来实现DFA模型。

二、模式匹配

所有的敏感词其本质来说是由ascii码组成的，而待过滤文本其本质也是ascii码的集合。比如说，现有敏感词集：{ [102, 105], [98, 112] }，对于输入串：A=[101, 102, 105, 97, 98, 112, 110]，我们的任务就是把上面两个敏感词构造成一个DFA，这样输入的A就可以通过在这个DFA上的转移来实现敏感词查找的功能。

树结构实现这个DFA的基于的基本方法是数组的index和数组value之间的关系（在双数组trie中同样是基于这一基本方法）。那么102其实可以看作一个数组索引，而105是102这个索引指向的下一个数组中的一个索引，105后面没有值了，那就代表这个敏感词结束了。

通过这样一种方式，就可以构造出一颗DFA的树结构表示。接着遍历输入文本中的每一个byte，然后在DFA中作状态转移就可以判断出一个敏感词是否出现在输入文本中。

三、程序实现

该思想的基础实现可参见这段python过滤脚本： https://github.com/ricoxie/word-filter/blob/master/dfa_trie_tree_impl_1.py

上述程序已知存在问题：无法最长匹配

程序已基于java改进实现，目前支持多语言、多编码、可最长匹配。

运行结果如下：

input  :    dfskdjf fuck ffucks
outcome:    dfskdjf * f*s 

input  :    fuck xxshitxfuckx功夫网
outcome:    * xx*x*x*