现在的位置: 首页 > 编程·网络 > 正文
字符串多模式精确匹配(脏字/敏感词汇搜索算法) 之算法前传
2014年04月11日 编程·网络 ⁄ 共 2605字 字符串多模式精确匹配(脏字/敏感词汇搜索算法) 之算法前传已关闭评论 ⁄ 被围观 2,564 views+

前面一篇稍微说了一下我自造的TTMP算法思路,貌似很好很强大——估计不是最强的,不过至少我自己觉得比较满意了,至少算是达到可用级别了。那么还有啥好写的呢?好久没有写这种类型的技术文章了,满脑子的想法:
1、除了算法本身,还有什么是效率损耗点?
2、TTMP算法本身也只是讲了一个大概,远没有详细到论文级别,抽空可以给大家详细讲一下。
3、其实上次说到的TTMP算法,还有至少2种实现方式,分别是前向检索和后向检索两种模式,他们都有什么区别呢?

嗯,今天的主题就是第一个:我们先抛开算法本身,看看还有什么会影响我们的性能的。

当我们进行敏感词过滤得时候,必然涉及3个要件:
1、脏字表
2、待检文本
3、检索过程

首先说脏字表的问题。通常来说,这个脏字表不是我们发明的,我们没事情搞这个图啥啊?不是自找麻烦么。这个问题通常是有人要求你这么这么干,于是你不得不那么那么干。所以,通常会有人给你一个脏字表。可是通常给你的人不是一个人,又或者说给你的文件格式乱七八糟。那么于是乎就有一个条目重复的问题!对于这个问题,可能有人是自己整理出一个没有重复的表。而我却觉得这个整理通常很费工夫,还不如让程序给整整。这样做有两个好处:
1、我们不必担心人家给你的文本就是有重复的。
2、当又有新的脏字表文本时,直接粘到原来的文本结尾即可,可以节省整理的人工成本。

于是,我们启动脏字过滤的过程时,首先第一个需要做的,就是排除重复。当然了,这个排重的过程也是一个性能损耗点,然而通常这个过程耗时相对来说还算可以接受,而且做一次这种操作,可以检索起码几百上千的文章,平均下来几乎可以认为没有任何的成本。这个过程很简单只要用下面的几句代码就可以完成了(用HashSet也一样的):

注意:上面的代码是假设你的算法能够忽略待检文本的大小写问题的。
有人就这么问我:为啥我用了一个很好的算法,最后效果还是有点不理想呢?我想这是一个可能的原因。通常我们所说的算法,都是讨论一些核心的问题。而类似这种问题,通常不会在WM/grep等算法的论文里面讨论。因为无论我们使用哪一种算法,这一个排重的步骤都是一样的,你可以认为是必须的,或者是不必要的。但是如果你真的希望提高效率,这也是一个值得你关注的地方。或者说,你得考虑一下当开始做最核心的事情之前,你是否已经将准备工作做得充分了。

从这个方向引申开来,还有一个可以优化的地方,就是是否考虑把脏字表转换成最小集合?比如这么说,当XYZ和Y都是原始脏字表条目的时候,你是否打算去掉XYZ呢?这个取决于你的任务。如果你的任务是,看看某篇文章是否有敏感词汇,如果有,就转人工检查。这个时候只要有最小集合就足够了,不需要最大匹配。但是如果你的任务是,只要是脏字,都需要用星星覆盖,不但不应该转换为最小集,反而应该增强你的算法(即使是牺牲性能)。记得有本书就说过,不要无的放矢。首先要知道目标在那里,才好射到靶上,射到靶上了,我们再来讨论如何给射准。通常我们看一段代码他是否能瞄准其目的,也可以判断出开发者在某些方面的水平如何。而我的任务目标是前者,于是乎就不需要作这个缩小最小集的工作了。顺便提醒一下,如果是后一种任务,普通算法是会有缺陷的,例如:
脏字表:
XYZ
X
待检文本:
WXYZA
被屏蔽之后会变成:
W*YZA
而不是我们所期望的:
W***A
这样的结果有可能是不理想的,因为这样可能还是有一些不雅的内容会被读出来。
这个时候即使检索出X,也不能够退出循环,需要继续检索更长的文本。这个过程也许是可以优化的,但无论如何都是要比原来多消耗一定的性能的。

当然了,如果说要做到极致,我可以用这么一段程序把原始脏字表给整理一下,缩小成最小集,然后生成修正后的脏字表文件供核心算法使用。而我目前并没有选择这么做,一个是觉得开发这么一个程序花的时间不见的能节省可观的时间。另一个问题是,有可能未来任务会转换为后者时,这个时候就不应该用最小集,原来做的这个工作可能就白费了。

下一个性能损耗点是在读取待检文本的时候,这个在什么位置呢?如果看过操作系统设计的相关书籍,我们应该知道,当我们进行磁盘操作的时候,CPU会是空闲的。我们的待检文本,不是储存于数据库中,就是储存于一个个单独的文件里面。无论是哪一种情况,我们都可能存在CPU等IO的情况。除此之外,通常一台服务器上面可能会有不止一个CPU,一个CPU也可能有不止一个内核。因此为了提高整体的检索性能,使用多个线程也是另一个必要的手段。关于这个话题,相信网上也会有很多的文章会讨论到,至少是类似的问题,这里就不再熬述了。如果你打算通过多线程进一步提高效率,我可以提醒大家的一点是,不可把性能压榨到极致,否则可能会影响到普通用户的使用。另一个需要注意的问题是,无论你是否打算用多线程,都要注意同一个时刻应该只允许有唯一一个进程在处理。如果是多个进程同时在做这样的检查,就很有可能都在检同一篇文章,这样无谓的性能损失是,无论算法再快也挽救不了的。可行的方法有很多,比如说把这个东西做成一个服务,永远就只有一个进程在做,同时内部有一个同步锁,不允许重入。又或者有一个数据库级别的锁,锁上了就不让其他人通过页面去启动这样一个检索过程。

有没有必要弄个分布式呢?一般来说,我们不是做搜索引擎,自有数据量还是比较有限的。能有一台服务器单独作这么一个工作,我估计就已经很了不起了。通过上面的多线程来压榨服务器性能,通常已经足够了。分布式处理可能会让你面临不小的技术难点,开发调试过程也比较麻烦。我建议这个作为最后的手段,在这之前还不如考虑配置一台有更多更快速CPU的服务器,或者考虑简单的空间换时间手段。其实我个人觉得,很难想象用户上传文字的速度,会超过一台服务器的处理速度。如果到了这样的一种程度,估计首先需要分布式处理的不是这个脏字过滤程序了,而是你的站点象用户提供服务的程序了。

上面说的这些,你说是算法吧,严格说来也不是,不过确实也是一段代码,也是一种解决问题的思路,这就是我标题里面“算法前传”的意思了。剩下来的,就是检索过程了。这一个前传就到此为止,希望能给大家另外一个提高效率的思路,同时也为达到你的算法的最高效率做好必要的准备。下一篇会先拆解一下TTMP-F和TTMP-B两种模式的概念、优缺点以及实施概略,详细地代码实战,还要酝酿一下。



本文链接:字符串多模式精确匹配(脏字/敏感词汇搜索算法) 之算法前传

转载声明:本站文章若无特别说明,皆为原创,转载请注明来源:海鹏的博客,谢谢!^^


抱歉!评论已关闭.

无觅相关文章插件,快速提升流量