• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

网络常用敏感词过滤方法

开发技术 开发技术 3小时前 1次浏览

 一、基础概念介绍

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

       NFA全称为:Non-Deeterministic Finite State Automata,即不确定的有穷自动机: 对一个输入符号,有两种或两种以上可能对状态,所以是不确定的。

      

二、Trie tree算法

       Trie tree,又称字典树、单词查找树,是一种树形结构,用于保存大量的字符串,是DFA算法中最常见的一种。它的优点是:利用字符串的公共前缀来节约存储空间。

       将abject、ablaze、able、abound、about、accent、accept、best、bestow、bet……生成Trie tree图,如下所示:

 网络常用敏感词过滤方法

 

  Trie tree类定义如下:

1     public class Trietree
2     {
3         public bool End;    //当前节点是否有匹配到的字符串
4         public List<string> Results;    // 匹配到的字符串集合
5         public Dictionary<char, Trietree > Nodes;    //子节点
6     }

 

三、AC自动机算法

       AC自动机是在trie tree基础上进行优化算法。即在tried tree的类上增加一个failure指针,如果当前点匹配失败,则将指针转移到failure指针指向的地方,这样就不用回溯,而可以路匹配下去了。

       例如使用上文生成的tried tree进行匹配【abestp】,

 网络常用敏感词过滤方法

       第一次,从a开始匹配,从左到右只能匹配到了ab。

       第二次,从b开始琵琶,从左到右匹配到了best,并且成功匹配了。

      

       在这个案例中,出现了算法回溯,如第一次匹配失败后,第二次还是从根节点匹配开始查找下一个节点,这就是回溯。

       AC自动机增加failure指针后,在第一次匹配失败时,就通过failure指针来到了第二次的b节点,减少回溯,从而优化性能。

 

AC自动机类定义如下:

1     public class ACTrietree
2     {
3         public bool End;    //当前节点是否有匹配到的字符串
4         public List<string> Results;    // 匹配到的字符串集合
5         public Dictionary<char, ACTrietree> Nodes;  //子节点
6         public ACTrietree Failure; // Failure指针,匹配失败后,使用此值进行下一次匹配
7         public ACTrietree Parent; //构造 Failure时 辅助用的
8     }

       AC自动机构造方法太多了,此文不再阐述。

 

四、AC自动机的几种改良

       AC自动机算法在算法理论上是无法再进行优化的,但可以在代码实现中优化

       1、Results集合,改用List<int>,做成索引集,就会减少内存使用量。

       2、Nodes字典使用的是Dictionary<>类,也是内存使用大户,并且Dictionary<>类查询采用的是hash查找,改用自定义Dictionary类使用二分查找

       3、构建AC自动机比较费时,当关键字太多时,会有明显感觉,可以使用序列化保存到文件,第二次加载文件就很快了。

       4、查询时,使用数组化查询比使用类查询快,常用的方法就是将ACTrietree结构转成5组数组,分别是basePtr、nextPtr、check、failure、resultIndex五组。

 

后记:

       敏感词过滤是一个复杂工程,学会AC自动机算法,只能说已经达到敏感词过滤的基础。

      

       不建议将Trietree转成double array trie,原因很简单,数组的长度是有最大限制的,如在C#代码中定入下面代码会报“Array dimensions exceeded supported range“

              int[] c =new int[0x7fffffff];

       将数组数量压得越少,数组的最大长度越容易达到最大限制。


程序员灯塔
转载请注明原文链接:网络常用敏感词过滤方法
喜欢 (0)