字符串多模式精确匹配(脏字/敏感词汇搜索算法)——TTMP算法 之理论如此

字符串多模式精确匹配(脏字/敏感词汇搜索算法)——TTMP算法 之理论如此

什么是TTMP算法?不好意思,我发布这篇文章之前,估摸是没有其他地方能找着该算法的,因为那是俺生造的。

TTMP是啥意思呢?是Terminator Triggered Multi-Pattern 的意思,也就是结束符触发多模式算法。

-_-! 有点难理解,没关系,看完了也许就理解了。

不过这个自造的算法有点复杂,为了保证大家能够顺利阅读,请大家配合做一个测试:

拿出你的手表,或者其他计时器,看看你能用多块的时间阅读完下面这篇文章。

判断标准如下:

如果你的时间少于15秒,就可以不用读我的文章了,完全有能力造一个更强的算法;

如果你的时间少于30秒,我们可以沟通交流一下;

如果你的时间少于45秒,你可以仔细阅读一下,说不定可能也许有点启发作用;

如果你的时间少于60秒,你一定能够在这里挖到宝矿;

如果你不属于上述情况,我建议您啊,还是不要费力气阅读了,有点面为其难了。

Do you raelly know Engilsh?

At laest in Egnlish, wehn pepole raed, tehy

usaully wlil not noitce taht the charcatres bewteen

the frist ltteer and the lsat leettr are not in a

corrcet oredr. In fcat, hmuan brian does recongize

wrods by seeknig the fsirt ltteer and the lsat leettr,

and tehn fnidnig whcih charatcers are insdie of tehm.

See! All the wrods hree wtih mroe tahn 3 leettrs are

all wirtten in a worng way! Do you niotice taht?

嘿嘿!其实刚才那段能力测试的话是瞎扯的,主要是让大家快速阅读,而不是认真阅读。有意思吧?

这个不是我瞎扯出来的,是一个著名大学的研究结果(好像是剑桥),原文我没工夫找,瞎造一段对付一下。不知道你读上述文字的时候是什么感受,反正我自己觉得比较震撼,也比较有意思。

确实,如果按照自动机理论,一个字一个字的去认真阅读,那么也还是很有可能能够理顺语法结构,搞清楚一句话的含义的(理论上如此吧,实际上还没有任何一个机器能做到真人般的感知能力)。但是如果每个字都认真读,并查找语法表,一来速度会慢,二来需要海量的空间去做这个事情。而人脑比较聪明,经过若干年的锻炼之后,已经自动的学会了放弃细节,比如读"cerroct"这个词的时候,找到前面是c开头,后面是t结尾,中间有eoc各一个,r两个,一查表就知道肯定是“正确”这个词而不管他正确与否——哦,不好意思,我又写错了,应该是correct!

嗯?这个跟我们这次的主题——字符串多模式精确匹配,有什么关系呢?

有啊!当然有啦。不过在我告诉大家这个关系之前,我们先来分析一下,字符串多模式精确匹配的效率问题是什么?写之前我先给大家说一下,我下面的说明也许不会很严谨,因为有时候太严谨了,就不好理解了。例如什么令X=Y……反正我最近为了这个事情找的一些资料,尽是这个,看着也觉得头晕。

所谓字符串多模式精确匹配是啥意思呢?字符串不多说了,实际上能用于搜索字符串的,也能搜索其他东西。多模式嘛:比如

string s="xxx";

string t="xx";

s.IndexOf(t);

这个是在一个字符串s中,找出另外一个字符串t所在的位置(或者说是否存在),这种叫做单模式,只有一个要被寻找的字符串t——唯一的一个搜索模式;如果说是

string s="xxx";

string[] t= new string[]{"x1", "x2", "x3"…};

s.Scan(t);

这种呢,就叫做多模式匹配了。因为我要在s里面找出一组t中任意一个所在的位置,或者说是看看我们的文章里面是否有脏字表里面的敏感词汇。

关于多模匹配问题,有很多已有的算法,我没有仔细的看,只看了一个可能是WM的算法,实际上可能还有什么grep/agrep等算法。不过需要提醒大家的是,还有不少的算法是讨论模糊匹配的,比如说容许其中有一个字不正确,那些算法就不是我这个主题要讨论的内容了。我要讨论的是精确搜索,即要找“地瓜”就找“地瓜”,不要“地鼠”。

多模式精确匹配很难吗?不难,很简单:我们只需要循环一下,先找s.IndexOf(t1),再找s.IndexOf(t2)……但是如果你果然这么做,效率就会很低了,因为你会需要扫描文本很多很多遍。可以想象,我们的目标是只要扫描整个文章一遍就能够找出这个文章里面都有哪些敏感词汇。不过,很明显该目标并不容易达成,但至少我们可以尽量接近“只扫描一次”这个目标。在进一步分析之前,建议先看另外一篇文章:

(重发).NET脏字过滤算法

这篇文章的算法(比如叫做XDMP算法)其扫描速度已经是比较快的了,并且其思路也比较好理解,我们在这个文章的基础上进行讨论会比较有意义。首先我们先整理一下这个算法的思路:

1、首先扫描文章里面的每一个字符,只有当某一个字符是脏字表中任意一个脏词的第一个字符(称为“起始符”),我们才试图看看接下来是否是脏字(触发检索)。

2、但是我们也不是毫无头绪的就开始循环脏字表的每一个词条:

2.1、我们往后检索一个字符,先看一下这个字符是否是脏字表里面的任意一个字符,如果不是,就表明不可能是脏字表中的任何一个条目,就可以退出了。

2.2、如果是,我们就取从第一个被检出字符到目前扫描到的字符之间的字符串,求哈希值,看看能否从哈希表中检出一个脏词。

如果检出了,那就大功告成,否则继续检索后面一个字符(重复2.1、2.2),直至找不到,或者超出脏字表条目最大的长度。

2.3、如果都找不到,或者超长,那么接下来就回到刚才的那个“起始符”后一个字符继续扫描(重复1、2),直至整个文章结束。

我这里先引入了三个重要概念:

1、扫描,指扫描文章,看看是否有需要和脏字表开始进行对比的情况;

2、检索,指已经发现可能存在情况了,在将文本和脏字表进行对比的过程;

3、起始符,指脏字表中条目中的第一个字符。

如果我们只要扫描,不需要检索就可以完成任务,那一定是最快的,不过目前我比较孤陋寡闻,没有找到这样的算法。

又或者,如果我们扫描一遍,而检索全中,那也很不错,很不幸,还是没见过。

很明显,扫描不应该多于1遍,否则肯定效率不可能高。那么检索就是算法的关键了!拆开来,提高检索质量有下列几个方式:

1、尽可能不触发检索;

2、如果确实需要触发检索了,那么每次触发检索的时候,要尽可能减少检索所需要遍历的字符数量;

3、每次对比脏字表的时候,减少运算量。

回过头分析上面的XDMP算法,是:

1、一次扫描;(很好,没啥好说的)

2、只要发现“起始符”就触发检索;

3、检索的时候,需要遍历的字符数是 1+2+3+…+n,这里的n是被命中的脏词的长度,或者最接近的长度;

4、每次检索,需要重复计算HashCode,不要忘了,计算HashCode,也是需要扫描字符串的,也就是又要遍历1+2+3+..+n个字符。

于是,我就有了一下问题:

1、难道每次遇到“起始符”了,就一定要触发检索吗?哎呀妈呀,这个也要检索(因为脏字表里面可能有MB)?!

2、难道每次触发检索,都非得要检索长度为1的,长度为2的,长度为3的……直到检索成功,或者出现非脏字表字符的时候吗?

3、难道每次检索,我们都需要把特定长度的待检文本截取出来吗?

4、难道每次检索,都需要从头开始计算哈希值吗?不能利用同一次触发检索后,上一次检索的哈希值,来减少本次计算的不必要运算量吗?

这四个问题,基本上是我想要解决的问题。其中前两个是一类问题,后两个是另一类问题。首先我们检查第一类问题:

好,我们回顾一下最开始的那篇英文,我们是否有点什么启发?对!我们触发检索的条件太简单了!

如果一个单词我们都没有看完呢,为什么要开始想这个事一个什么词呢?

另外,我们触发检索之后,也作了很多不必要的检索,因为当我们遇到"cao"这个字符的时候,很可能脏字表里面只有"caoT妈","caoN妈"这两种情况。如果有文章里面是"操作",脏字表里面正好又有"作LOVE",上述XDMP算法还是会乖乖的搜索两个字符的情况,而实际上又是没有必要的。

那么我们如何减少这些不必要的运算呢?首先,我们改一下,不要每次遇到“起始符”就触发检索。我们扫描到起始符怎么办?记录下来他的位置等信息,然后继续扫描下去。当我们遇到了“结束符”,也就是脏字表每一个词条中,最后一个字符中的任意一个时,我们才考虑是否要开始触发扫描。而扫描的时候呢,也不一定非得要脏字长度为1、2、3……的情况。因为之前记录了各种起始位置,我们可能只需要扫描1、3两种情况,或者5这种情况。

接下来是第二类问题:

上述算法里面,为了加快检索某串字符是否在脏字表里面,使用了哈希表。为了能够查表,所以就必须把这个哈希值给截取出来。可是这就引发了两个性能损耗点:

1、每一次截取,都要重新计算哈细值;

2、每一次都需要截取出一个字符串。

要避免这个问题,首先我们需要了解哈希表大致是怎么工作的:

哈希表实际上是根据当前的字符串内容,得出一个概率相对比较平均的散列值(这样哈希效表才不会容易出现冲突,即内容不同数值却一样),然后找出表中哈希值相等的第一个结果,然后对内容进行比较,如果相同就是找到了。否则就找下一个,直到没有相等哈希值的条目为止。

于是,我们可以这么来解决上述问题:

1、首先,我们造一个哈希值的计算方法,使得我们可以利用上一次的计算结果,接着计算下一个结果。

比如说,我们可以一个字节一个字节的进行异或(好处是方向性不敏感),或者也可以规定从字符串后方往前开始计算。

为什么规定从尾部进行计算?因为TTMP是结束符触发扫描的,比如说有文本:

ABCDE

如果E是结束符,那么就会检索ABCDE、BCDE、CDE、DE、E(还要看是否扫描到这些起始符)。如果我们是从后方往前计算,那就可以利用E的哈希值以及字符D,就可以计算DE的哈希值,而不需要再次对E字符进行计算了。

2、其次,我们可以构造这样的哈希表:

Dictionary<int, List<string>> hash;

其key就是我们刚才算出来的哈希值,根据算出来的哈希值,我们就可以得到一个该哈希值下的脏字列表,然后我们一个个的和待检文本进行字符对字符的比较。这里看起来很奇怪,为什么有了哈希值,还不能够通过哈希值直接找到对应的字符呢?

不要忘了,哈希值本来就是会冲突的,我现在只不过把冲突的情况单独取出来自行处理,这样实际上的检索次数并没有增加(放在哈希表里面,也必须一个个的进行字符对字符的比较,才能够确定Key值是否完全相等,而不是Key的哈希值相等但Key值不等)。而好处是,我们不需要非得取出一个字符串,好让哈希表去获取这个字符串的哈希值(需要从头遍历每一个字符)。

通过以上的措施,我们就可以让每一次对n长度待检文本触发检索,只需要最多遍历n个字符,就可以得到最多n次遍历的所有哈希值了,而原XDMP算法则需要遍历Sum(n)个字符。

当然了,上述这几个措施,其效果并不会非常明显,原因有三个:

1、通常我们的文本都是很正常的文本,顶多偶尔有点敏感词汇,因此并不会经常挑战前面说到的性能损耗点;

2、通常我们的脏字表数量不会极其巨大,起始符和结束符也应该集中在有限的那些字符里面,因此绝大多数时候首字符表,以及结束符表就已经能够极大地提高性能了;

3、即使我们真的需要触发检索了,我们的脏字通常长度会比较短,或者大多数会比较短,因此上面的改进所带来的性能提升会比较有限。比如说两个字符的情况下,原算法计算哈希值需要遍历3个字符,而TTMP则只需要遍历2个字符……汗

而如果是5个字符,原算法需要遍历15个字符,而TTMP则只需要遍历5个字符,开始有差距感了。

可惜的是,5个字符的敏感词毕竟还是比较少的,而一篇文章正好中这个5字敏感词的地方也是很少的。

目前我这个TTMP算法还没有优化,已经能够做到和XDMP算法消耗时间比为1:1.5-2.5,算是很不错了。当然了XingD后来又做了一个新的算法,测试速度很快,可是当时我测的时候还不稳定,有漏检的情况,因此暂时不做评论了。

至于我的TTMP算法,也还有不少可以挖掘潜力的地方,比如现在是前向检索的,以及预先计算哈希值的。如果改成后向检索,检索时计算哈希值,性能应该会更好一点。不过暂时不打算继续挖掘了,准备把他先放到实战里面应用再说。

呃,其实本文开头说的还是没错的,本文还是有点难度,而本人描述能力也不是特别好,不知道各位看官有没有看懂了?

源码?嘿嘿,私货,先收藏一段时间再说。当然了,如果你有一段源码,能够合法制造让制造者合法拥有的人民币真币,能够用VS2005编译通过,部署过程只需要点一下鼠标,运行过程无需看管,并且你愿意和我交换的话,我会考虑一下的……真实的情况是,我现在还要继续让算法更稳定,不能放出一个问题多多的代码出来吧?

私下说一下,这个程序比XDMS算法复杂不少,如果将来放出来,并且各位想要整明白的话,还需要自己花点心思。

哦,顺预先给某人回复一下:

KMP算法是单模匹配算法,BM据说也是单模式的算法。

WM算法是多模匹配的,我找了一个据说是WM的算法看了看:

http://blog.chinaunix.net/u/21158/showart_228430.html

不知道你说的是不是这个。

我发现思路其实和KMP/BM类似,主要是通过“跳跃”技术来提升性能的。但是该文里面也提到了这么一段话:

假设其中一个模式非常的短,长度仅为2,那我们移动的距离就不可能超过2,所以短模式会使算法的效率降低。

可问题就在于,一般脏字表的长度都是1到2个的居多,因此绝大多数跳跃的作用并不强。即使是5个字符,再TTMP里面,也很可能因为超出长度没有遇到“结束符”而不会触发扫描。而WM需要有一个Shift表,为了节省空间还需要压缩,这就意味着需要对每一个扫描单元进行一个压缩计算。综上所述,TTMP和WM进行搜索脏字任务的PK,谁胜谁负还不一定呢。顺便说一下,即使是WM,也不是一次扫描的,因为如果不跳跃的话,就会要多扫描一下某些字符。

TTMP效率描述:

Ot = Ot(文本长度) + Ot[ 起始符与结束符在出现在扫描窗口中的次数*Avg(同一个结束符中哈希值相等的词条数目) ]

=Ot(N) + Ot[f*Avg(h)]

Om = Om(字符类型表) + Om(结束符表) + Om{ 词条总数*[哈希表内部变量消耗内存+列表消耗内存数量+Avg(词条长度) ] }

=256K + 256K + Om{n * [12+12+Avg(k) ] }

=512K + Om[n*(c+k)]

^_^ 唐僧回来了……

分类: 其他

标签: 算法, 脏字, 敏感词, TTMP, 匹配, 搜索, WM, 关键字, 多模精确匹配, 多模匹配, 字符串

绿色通道:好文要顶关注我收藏该文与我联系

Sumtec

关注 – 4

粉丝 – 111

荣誉:推荐博客

+加关注

0

0

(请您对文章做出评价)

« 博主前一篇:原来,07年我把自己给和谐了

» 博主后一篇:字符串多模式精确匹配(脏字/敏感词汇搜索算法) 之算法前传

posted on 2008-02-01 18:31 Sumtec 阅读(10461) 评论(19) 编辑 收藏

评论

2102140

#1楼 2008-02-01 18:58 xingd

我现在fastcheck已经扩展到了一个byte,因此8个长度内的脏字,除非所有位上都通过了fastcheck,就不需要substring和gethashcode的调用了。像"操作"这样的词已经不需要hash判断了。

我的算法还有改进的余地,加入结束符的话,可以减少一些substring和gethashcode的代价。不过我想到了一种更快的方法,再加一个byte[Char.MaxValue],记录以某字符开头的脏字可能的长度,8个bit分别用来记2~9长度的脏字是否存在。同时加入一个新的BitArray记录结束符。这样新消耗了72k内存,但是效率又提升了很多,等下我测一下。

乐趣就在效率的不断改进中,呵呵。

 回复 引用 查看 

#2楼 2008-02-01 19:25 问道[未注册用户]

“`–引用————————————————–

xingd: 我现在fastcheck已经扩展到了一个byte,因此8个长度内的脏字,除非所有位上都通过了fastcheck,就不需要substring和gethashcode的调用了。像"操作"这样的词已经不需要hash判断了。

我的算法还有改进的余地,加入结束符的话,可以减少一些substring和gethashcode的代价。不过我想到了一种更快的方法,再加一个byte[Char.MaxValue],记录以某字符开头的脏字可能的长度,8个bit分别用来记2~9长度的脏字是否存在。同时加入一个新的BitArray记录结束符。这样新消耗了72k内存,但是效率又提升了很多,等下我测一下。

乐趣就在效率的不断改进中,呵呵。

——————————————————–

不错 不错 竟医求竟

 回复 引用 

#3楼 2008-02-01 19:25 怪怪

呵呵, 你俩有意思 🙂

 回复 引用 查看 

#4楼 2008-02-01 19:58 周银辉

算法很好,LZ很强大

 回复 引用 查看 

#5楼 2008-02-01 20:50 xingd

http://www.cnblogs.com/xingd/archive/2008/02/01/1061800.html

我发了新版的啦

 回复 引用 查看 

#6楼 2008-02-02 11:55 Anders Liu

好强!顶!

看了开头那个测试,我还以为是模糊匹配的呢。

 回复 引用 查看 

#7楼 2008-02-02 15:11 留恋星空

学习

 回复 引用 查看 

#8楼 2008-02-02 16:11 灵感之源

真巧,昨天开始做脏字过滤。。。

 回复 引用 查看 

#9楼 2008-02-03 01:20 A1[未注册用户]

呵呵,大概我就是某人吧。;)

没错KMP、BM都是单模匹配,但是有改进后适用于多模匹配的BM算法变种。之前我在xingd的文章中回复提到的更高效的新算法,基本都是基于BM算法,或者借鉴BM算法的跳跃思想。

而且WM算法也是采用了BM算法的跳跃思想。我看过新算法,其报告中通常会拿WM作比较,这些新算法基本上都是在最短模式长度越长、模式数量越多的情况下才显现出优势,所以我就建议xingd参考WM算法,对之加以改进。毕竟.net环境、中文环境尤其特殊的地方,那些算法基本上被测文本都是原始的byte array。如果只是去实现一个自己的WM是非常无趣的事情,如果是要研究一个自己用,那自然是要超过现有算法的好,否则岂如同“没有高潮的XX”,那简直是YY呢。不过我想我们这帮人大多只是好玩而已,借此活动活动大脑。

你给的那个chinaunix上的文章,我没看过,也没做过脏字过滤。我是在05年的时候因为公司一个项目迫于无奈才发动人力去找多模匹配方面的资料。那个项目其中有个需求大致是这样:能对一篇文章中的“柯林顿”一词提供“克林顿”的修正建议,这很像拼写检查,但也有很大的区别。比如有时我们标准书写是个法文,里面包含ě这样的带音调字符,但是可能在一个英文网页上它只是e而已。诸如此类,我们不知道究竟有哪些稀奇古怪的译法,对“甘乃迪”也能提供“肯尼迪”的参考是不指望了,但至少可以根据拼音相似性来提供建议。可是我们自有的词条至少也有18万之多,当时没有现成的解决方案,只好在网络上搜刮一番,才知道原来有这些(也不知道N年前在学校时有没有看过,反正是没印象)。

嗯,我念叨的也不短,该把话题转到你的文章了。

你对于算法性能要点分析已经非常清晰了。如果我没记错,你的算法和WM似乎很像,只是你没有采用压缩码。

但是我不懂你在如此明白的情况下怎么又会搞出这么个玩意:

Dictionary<int, List<string>> hash;

把模式放到List<string>中?虽然实际场景中List中的元素数量一般会很少,但我还是觉得很奇怪,哪怕只是换成hash也要更好一些吧?

其实计算压缩码和计算散列一样都可以只计算一次,只是.net中默认的string散列计算方式在长串方面会比计算压缩码更快。但我们还得考虑在必须进行一个完整(也许去掉了前缀或者后缀)的模式单元(脏字词条)与疑似子串比较时如何更快地确定到底是哪个或哪些模式,这就涉及到模式是如何分布的,也就是如何散列的,默认的散列计算发生碰撞几率是很不明确的,但如果适用压缩码加上特定的掩码是有可能明确降低碰撞几率的,况且压缩码与被测子串是一一对应的,所以还可以直接用于匹配计算(只是简单的为运算,而不是串比较或者计算hash),在模式较短情况下速度应该是能更高的。但这都是理论预测,实际状况很难说。

PS:一天不来,你们两个就这个问题发了三篇文章,特别是你,前世今生的,实在兴致好啊。过年了,本来应该是休息,却觉得更累,洗洗刷刷,买这买那,孩子又生病,烦哪!我可能真的老了,本来就懒,没你们这么激情。

 回复 引用 

#10楼 2008-02-03 09:45 蛙蛙池塘

速马熊,我转到我们论坛去了哦,前阵子研究过一下,谢谢。

手工pingback一下

http://www.xxeq.com/bbs/viewthread.php?tid=533&extra=page%3D1

 回复 引用 查看 

#11楼 2008-03-30 00:32 蛙蛙池塘

还是没看懂

 回复 引用 查看 

#12楼 2008-03-30 22:49 蛙蛙池塘

又看了一遍,还是有些地方不懂

 回复 引用 查看 

#13楼 2008-04-10 12:20 鸿都[未注册用户]

看了楼主的文章,收获很大,并且用JAVA语言实现你说的那XDMP算法,所以真心的谢谢你还用XDMP算法的作者!不过,现在看了你发表的改进算法后,自己也也很想再按照你说的思想加以对XDMP改进,希望能得到你的指导,十分感谢!另外,我想问一下,能不能给我推荐几个用于监视算法的CPU、内存使用率的工具或方法以便对各种算法进行比较,谢谢!

 回复 引用 

#14楼 2008-04-15 00:03 smt[未注册用户]

XDMP和TTMP不是一个思路,如果你要用TTMP就需要做一个比较彻底的改变。XDMP的重点在于检查某个字符是否字典中的第一个字的集合,如果是,就开始扫描。TTMP的重点是,发现某个字是字典中的第一个字的时候,记录其位置(以及字符等其他信息),而当发现某个字是字典中的最后一个字符的时候,就和现有的开始记录比较,看看头尾字符、以及之间的长度是否在字典中有符合的项,如果有再做扫描。具体的我这里就不说了。

 回复 引用 

#15楼 2008-11-23 22:58 Jeffrey Zhao

那段话我真的在15秒左右就读完了呢

 回复 引用 查看 

#16楼 2008-12-25 13:10 半克拉鹅卵石

mark

 回复 引用 查看 

#17楼 2009-07-17 09:23 xiangxiang

给楼主发消息了,还没收到回音

 回复 引用 查看 

#18楼 2011-05-16 15:41 41426277

不知道你的算法和我的比较那个更有效率?

http://www.cnblogs.com/mmpc/articles/2047474.html

 回复 引用 查看 

#19楼 2011-05-20 16:15 41426277

感谢你的回复,本人修改了部份索引,从9秒多提高到1秒多。

可以到这下载已改的程序测试。

http://www.cnblogs.com/mmpc/articles/2047474.html

 回复 引用 查看 

刷新评论列表刷新页面返回顶部

此条目发表在未分类分类目录,贴了标签。将固定链接加入收藏夹。