如何设计高效的组织结构,设计一个高效的算法
IM项目需要对从上面转发的邮件进行必要的过滤。 如果总是对着某人输入f**k,就不太文明了。
一个常见而简单的方法是设置一组敏感单词,当消息中显示这些单词时,系统会进行必要的处理。 怎么实现这个功能?
一、能够实现敏感单词过滤功能的方法有很多
方法有很多,但很容易罗列了一些。
1、敏感单词直接整理成String后,用索引of方法查询。
2、传统敏感词签入后,SQL查询。
3、利用Lucene编制分词索引进行查询。
4、利用DFA算法进行。
显然,方法1和方法2很少能满足IM系统有效处理消息的需要而放弃。
方法3 )采用Lucene建立本地分词索引,将消息内容分词后,在索引库中检索。 这个方法很复杂,分词效率也不高,所以放弃。
许多敏感词过滤系统采用方法4、DFA算法。
二. DFA介绍
什么是DFA? 我需要在这里简要介绍这个概念。
1、DFA的定义
DFA翻译成中文是“确认有贫困机器人”
定义:有穷机器人(DFA )的m为5组。 m=) k、、f、s、z )其中
K是贫穷的集会,其各要素被称为一种状态
是贫穷的字母,每个元素都称为输入符号,因此也称为输入符号字母
f是变换函数,可以是KK上的映射,且也可以是部分函数。 也就是说,这意味着如f(ki,a )=kj,) kiK,kjK ),当前状态为ki,输入端为a的情况下,变换为下一状态kj,将kj称为ki的下一状态
S K是唯一的初始状态
ZK是终端状态的集合,终端状态又称可接受状态或退出状态。
2、DFA示例
3、DFA状态图显示
假设DFA M中包含m个状态、n个输入字符,则该状态图中包含m个节点,每个节点最多射出n个弧,整个图中包含唯一的初始状态点和几个终端状态点。 初始状态节点被赋予双重箭头“=”,末端状态节点用双重圆表示,如果f(ki,a )=kj,则从状态节点ki到状态节点kj画出标记为a的弧。
4、DFA接受
对于*中的任何符号串t,如果存在从初始状态到某个最终状态的道路,并且该道路上的所有弧线标记相连的字符串等于t,则t被接受为DFA M;如果m的初始状态同时是最终状态,则空字符被识别(接受)为m
也就是说,如果t *,f(s,t )=P,其中s是m的开始状态,PZ,z是终端状态集合。
说是DFA M接受(认识到) t。
如果知道DFA的介绍,就可以这样理解敏感的单词过滤系统。 用需要过滤的敏感单词构建DFA (确认有贫困机器人),遍历需要过滤的文本,判断文本中是否有DFA被接受)字符串即可。
如果读不懂DFA,看下一节也没关系。
三.在三叉树中构建DFA
Trie树,即词典树,也称为单词检索树或关键树,是树结构,是哈希树的变种。 典型的APP应用程序用于统计和排序大量字符串,因此不仅是字符串,在搜索引擎系统中还经常用于统计文本的词数。 其优点是,最大限度地减少了不必要的字符串比较,查询效率高于哈希表。
假设有b、abc、abd、bcd、abcd、efg、hii这7个单词,我们构建的树如下图所示
如上图所示,对于各节点,从根到他的过程是一个单词,如果这个节点用红色标记,表示该单词存在,否则就不存在。
过滤敏感单词是指从第一个单词开始,然后在Trie树中为每个单词搜索需要过滤的文本。 走到树的尽头,就能找到敏感的语言!
四.防止倒退
1、上溯的场景
请看“葵花籽二手车交易量全国领先”过滤对象文本(以下简称母串),来看下图模拟的几个敏感词语。 让我们来看看搜索过程。
)第一个字符“瓜”位于树的一层节点上(一层节点有“二”、“瓜”、“西”三个字符)。 接着(用中间的子树)在后面找“子”字,在树枝的后续节点; 继续找“二”,继续找“手”,继续找“车”,找不到“车”字,找失败。
)2) )这里不能从“二”字开始找。 有必要追溯到“子”字。 万一,有一个从“子”字开始的敏感词语呢。 )第二个字符的“子代”不在三叉树的一楼节点上。 找失败了。
(3)第三个“二”字在三树的一楼节点上……
)4)后续文字可以用这种方法逐字逐句地向后查找。
虽然能解开这个搜索方法,但是效率不高(注意步骤2 ),虽然读了后面的文字,但是没有命中,所以检索返回,效率降低。 其实,我们在第一步中比较过“二手货”这个词。 如果能利用步骤1中的比较结果,我直观地觉得可以加快和“二手车”这个敏感的词的匹配。
2、前缀指针
上一个场景类似于字符串搜索的KMP算法。 KMP算法可以防止在字符串搜索过程中指针后退。 那么,t
rie树的结构有没有办法也避免这种情况发生呢?答案是肯定的。参考KMP算法(百度一下你就知道了) 的最长相同前后缀的方法,来避免回溯。
这里首先需要理解“前缀”、“后缀”的思想。如果不了解这两个概念,推荐一篇KMP算法讲得特别清楚的博文http://www.cnblogs.com/c-cloud/p/3224788.html(一定要读)。
为了避免回溯,参考KMP的next数组,在Trie图中定义“前缀指针 ”
“前缀指针 ”定义:从根节点到节点P可以得到一个字符串S,节点P的前缀指针定义为 指向树中出现过的S的最长后缀(不能等于S)
后续文章将详细讲解怎么高效构建“前缀指针 ”,如何快速遍历母串,以及工程上如何实现的问题。