一、DFA敏感词过滤其实是模式匹配问题,目前比较高效的计算模型是DFA。匹配过程主要依赖状态的转移而不是复杂的计算,从而提高了速度。DFA的基本功能是可以通过当前的state和event得到下一个state,即δ(state, event)=next_state,下列状态转换图展现了一个DFA的状态转移过程:当然,该过程还有其他表示方式,比如说矩阵表示:abSUVUUVVUQQQQ本文将使用字典树来实现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中作状态转移就可以判断出一个敏感词是否出现在输
...
继续阅读
(205)