字符串多模式精确匹配(脏字/敏感词汇搜索算法)——TTMP算法 之B模式概述

字符串多模式精确匹配(脏字/敏感词汇搜索算法)——TTMP算法 之B模式概述

前面一片文章,已经提到了TTMP算法的核心概念,就是“终止符”触发检索。其实这个概念也不是我创造出来的,如果看过编译理论,应该会很熟悉,其实我是偷师其中的归纳法。那么何谓之B模式呢?
TTMP -B指的是,在触发对关键字的检索时,从后面往前面检索。比如说:
脏字表:
wxyz
yz
待检文本:
wxyza
当我们遇到了结束符z的时候,我们会回过头来查看刚才到底都遇到了什么文字。由于我们之前的扫描已经得到了两个“起始符”的相关信息,因此我们只要按发现起始符的逆序找 yz和wxyz。于是,最终我们命中的关键字是yz,而不是最先遇到的wxyz。
我们先说B模式的好处:
1、找到的一定是最短的匹配
2、在分析正常文本的时候,效率可能相对会更高
为什么是最短匹配很简单,就不说了。重点说一下为什么效率可能会相对更高呢?这里有两个原因:
1、如果我们的脏字表存在以某一个有n个短模式X作为结尾的其他模式,例如AX、BX,由于算法的特殊关系,是不可能进行AX、BX扫描的。这样的话,我们可以少算若干个字符的运算量。
2、对于正常文本,以及正常的脏字表,有如下特性:
a)文本中出现脏字条目命中的概率是非常低的,也就是说,大多数遇到起始符的情况,到最后都不见得能遇到结束符。于是在扫描到起始符就开始计算哈希值,很可能是得不偿失的(大多时候预先的计算是白做的),因此我们很可能选择在触发检索之后,再重新回过头来计算哈希值。同样是在触发检索之后,再重新计算哈希值的情况下,B模式比F模式所需要额外损失的性能就会更小。
b)脏字表中的词条通常都是小字符串占多数,而且通常比较有可能会有交集的情况,比如说ABC和C。在此情况下,如果从后往前搜索,实际上ABC这个条目是永远也不会被命中的。换句话说,B模式会自动达到使得脏字表最小化的实际效果,而不需要进行一个取交集的运算过程,包括初始化的时候和进行扫描的时候,都不会有额外的性能损失(不预先计算哈希值的情况),或者至少性能损失较小(预先计算哈希值的情况)。当然了,这样会占用一些额外的不必要的空间,不过一般来说脏字表要超过1万个条目都很难,1万个条目撑死了也就占用100k。
回头来说B模式的坏处:
1、要做最大匹配,意味着要付出比F模式更高昂的额外计算成本。不过有可能即使加上这个额外成本,与会比F模式要高效。
2、由于是逆顺序检索,如果我们选择遇到起始符就预先计算哈希值,就很有可能做了一些不必要的运算,即使是在命中的情况下。考虑:
脏字表:
ABC
C
待建文本:
ABC
则在遇到A的时候,就会开始计算哈希值,直到C字符。但是可以看到,对AB进行哈希值计算,很有可能就是不必要的。
关于这个缺点,其实只是“眼看着还有白费的运算无法消除”而已,实际上相对F模式可能还是更快的。
综上所述,如果你的任务只是检索某篇文本是否有命中,B模式更适合你。如果你是要做替换,也可以考虑F模式。由于我所选用的是F模式,并没有实际实施,因此我无法给出任何代码,大家只能够抽象的看一下。同时有的地方因为没有经过实际检验的缘故,有可能会有谬误的地方,请大家原谅。

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