你应该知道的算法1-敏感词过滤算法

=敏感词过滤在各互联网是比较常见的操作，也有很多算法来处理这个问题，个人看了些资料后觉得“字符串多模式精确匹配”（脏字/敏感词汇搜索算法）——TTMP算法是一种比较实用的方法，每个做web的人都应该有所了解

在这片文章中对这个算法有较详尽的解释了，推荐大家去看原文：http://www.cnblogs.com/sumtec/archive/2008/02/01/1061742.html

下面是我从原文中摘抄的比较重要的内容：

关于多模匹配问题，有很多已有的算法，我没有仔细的看，只看了一个可能是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算法，也还有不少可以挖掘潜力的地方，比如现在是前向检索的，以及预先计算哈希值的。如果改成后向检索，检索时计算哈希值，性能应该会更好一点。不过暂时不打算继续挖掘了，准备把他先放到实战里面应用再说。