首页天道酬勤如何设计高效的组织结构,设计一个高效的算法

如何设计高效的组织结构,设计一个高效的算法

张世龙 05-06 08:35 126次浏览

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)

后续文章将详细讲解怎么高效构建“前缀指针 ”,如何快速遍历母串,以及工程上如何实现的问题。

centos查看所有用户,查看当前用户命令