青海省教育厅门户网站官网,本地wordpress站点上传,wordpress 主题 支付宝,衡水企业做网站文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
1 敏感词过滤场景
在很多支持用户发表内容的网站#xff0c;都有敏感词过滤替换的功能。例如将一些淫秽、反动内容过滤掉#xff0c;或者替换为****。在一些社交类…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
1 敏感词过滤场景
在很多支持用户发表内容的网站都有敏感词过滤替换的功能。例如将一些淫秽、反动内容过滤掉或者替换为****。在一些社交类网站为了避免做广告之嫌会把手机号替换为*****。当然有些人为了躲避被替换会写一三七一零六捌这样的手机号。这是后话了。这篇文章我们先学习如何替换字符串类的敏感词。我们可以维护一个敏感词词典当用户输入评论之后通过字符串匹配算法查找是否包含敏感词。如果有需要找到起始位置和长度替换为***。 前面讲的几种字符串匹配算法BF、RK、BM、KMP、Trie树都可以实现但是效率不够高。我们使用多模式串匹配算法来提高效率。
2 基于单模式串和Trie树实现敏感词过滤
BF、RK、BM、KMP都是单模式串匹配算法是在一个模式串和一个主串之间进行匹配。多模式串匹配是多个模式串和一个主串进行匹配。为了解决敏感词过滤问题用单模式串匹配来做的话每次匹配一个模式串和主串匹配多次也可以实现只是这样多次扫描主串效率会低。
多模式串匹配算法扫描一次主串实现匹配这样的效率就很高了。我们可以对敏感词做预处理构建一棵Trie树。用户输入内容后把用户输入的内容作为主串从第一个字符C开始匹配。当匹配 到Trie树的叶子节点或者中途有不匹配的字符的时候我们将主串的开始位置偏移一位也就是C字符的下一位重新在Trie树中匹配。
基于Trie树的这种匹配方式很像单模式匹配的BF算法。我们知道KMP对BF算法的改进就是引入了next数组。当匹配失败的时候主串位置不动模式串位置移动。基于这种思路我们优化Trie树查找的效率这就是AC自动机算法。
3 AC自动机算法
AC自动机算法是一种经典的多模式串匹配算法全称是 Aho-Corasick 算法。ACTrie树next数组。这里的next数组是基于树的。
构建AC自动机包含两个操作1 构建Trie树2 在Trie树上构建失效指针。
AC自动机每个节点的结构如下。
public class AcNode {public char data; public AcNode[] children new AcNode[26]; // 字符集只包含 a~z 这 26 个字符public boolean isEndingChar false; // 结尾字符为 truepublic int length -1; // 当 isEndingChartrue 时记录模式串长度public AcNode fail; // 失败指针public AcNode(char data) {this.data data;}
}
关于Trie树的构建看上一篇文章。这里重点描述构建失效指针。
3.1 构建失效指针
假设这里有 4 个模式串分别是 cbcbcdabcd主串是 abcd。
我们沿着Trie树走到p节点下图中的紫色节点那p的失效指针就是指从根节点到p节点形成的字符串abc跟所有模式串前缀匹配的最长可匹配后缀子串就是箭头指向的bc子串。 这里解释一下最长可匹配后缀子串。abc的后缀子串有c、bc。我们拿它们与其他模式串的前缀子串去匹配。如果某个后缀子串和其他模式串的某个前缀子串可匹配就成为可匹配后缀子串。
从可匹配后缀子串中找到最长的那个就是最长可匹配后缀子串。我们将p节点的失效指针指向那个最长可匹配后缀子串对应的前缀子串的最后一个位置。就是上图中箭头所指位置。
计算每个节点的失效指针看似复杂是不是可以类似KMP利用已经求得的、深度更小的节点的失效指针来推到呢。如果这样的话我们可以逐层解决这就是树的层次遍历的过程。
根节点的失效指针指向自己。如果已知节点p的失效指针指向q如何推到p的子节点pc的失效指针指向什么位置。
如果q有一个子节点的字符等于pc节点的字符那么pc的失效指针指向该节点。 如果q的所有子节点的字符都不等于pc节点的字符那么qq.失效指针。再继续判断。
代码如下。
public void buildFailurePointer() {QueueAcNode queue new LinkedList();root.fail null;queue.add(root);while (!queue.isEmpty()) {AcNode p queue.remove();for (int i 0; i 26; i) {AcNode pc p.children[i];if (pc null) continue;if (p root) {pc.fail root;} else {AcNode q p.fail;while (q ! null) {AcNode qc q.children[pc.data - a];if (qc ! null) {pc.fail qc;break;}q q.fail;}if (q null) {pc.fail root;}}queue.add(pc);}}}最终,通过按层级计算每个节点的失效指针最后构建完成的AC自动机如下图。
3.2 在AC自动机上匹配主串
如何在AC自动机上匹配主串呢例如主串是a从i0开始AC自动机从proot开始。
如果p指向的子节点x的字符串等于a[i]则把px。这个时候我们判断一下以目前匹配的字符串来说有哪些是匹配到的字符串这也是失效指针的含义。实现方式就是检测p.失效指针是否是一个模式串的结尾。如果是可以得到匹配的字符串的长度和结尾位置。继续检测p.失效指针.失效指针。结合代码看最好理解。处理完成i。
如果p指向的子节点的字符串都不等于a[i]。则pp.失效指针。
public void match(char[] text) { // text 是主串int n text.length;AcNode p root;for (int i 0; i n; i) {int idx text[i] - a;while (p.children[idx] null p ! root) {p p.fail; // 失败指针发挥作用的地方}p p.children[idx];if (p null) p root; // 如果没有匹配的从 root 开始重新匹配AcNode tmp p;//字符串已经匹配了一部分了模式串中就到tmp节点。那就判断tmp是不是个字符串如果是那就是匹配到了。如果tmp不是个字符串那已经匹配的这部分如果在下一位发生不匹配的时候指针应该回退到tmp.fail。那继续看tmp.fail是不是个字符串。//如果是那就是说已经匹配的部分包含某个字符串。while (tmp ! root) { // 打印出可以匹配的模式串if (tmp.isEndingChar true) {int pos i-tmp.length1;System.out.println( 匹配起始下标 pos ; 长度 tmp.length);}tmp tmp.fail;}}}3.3 AC自动机的时间复杂度
Trie 树构建的时间复杂度是 O(m*len)其中 len 表示敏感词的平均长度m 表示敏感词的个数。
构建失效指针的时间复杂度。这里给一个不太精确的上界。假设 Trie 树中总的节点个数是 k每个节点构建失效指针的时候你可以看下代码最耗时的环节是 while 循环中的 qq-fail每运行一次这个语句q 指向节点的深度都会减少 1而树的高度最高也不会超过 len所以每个节点构建失败指针的时间复杂度是 O(len)。整个失败指针的构建过程就是 O(k*len)。
在AC自动机上查询的时间复杂度。与构建失效指针的分析类似。最外层for循环的长度是主串的长度。循环内部耗时的操作是两个while循环每个while循环的次数最多是len。所以时间复杂度不超过O(n*len)。一般来讲敏感词的长度不会很长近似O(n)近似主串的长度。
从时间复杂度来讲AC自动机和Trie树的查找性能是一样的。实际上因为失效指针大部分指向root节点所以绝大多数情况下AC自动机做匹配的效率要远远高于给出的估算。只有在极端情况下才会退化为何Trie树一样的效率。
