字符串多模式精确匹配（脏字/敏感词汇搜索算法）——TTMP算法之

【 tulaoshi.com - Web开发 】

　　什么是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这种情况。