敏感词过滤算法Aho-Corasick

待我称王封你为后i 2021-07-04 20:58 527阅读 0赞

## 多模式串匹配算法简介 ##

敏感词过滤最基本的原理就是字符串匹配算法，也就是通过维护一个敏感词的字典，当用户输入一段文字内容后，通过字符串匹配算法，来查找用户输入的这段文字，是否包含敏感词。

字符串匹配算法有很多比如**BF算法、RK算法、BM算法、KMP算法**还有**Trie树**。前面四种算法都是单模式串匹配算法，只有**Trie树**是多模式串匹配算法。

我们可以针对每个敏感词，通过单模式匹配算法与用户输入的文字内容进行匹配。但是这样做的话，每个需要匹配的敏感词都需要扫描一遍用户输入的内容。如果敏感词有很多，并且用户输入的内容很长，这种处理的方法就显得比较低效。

与单模式匹配算法相比，多模式串匹配算法在敏感词过滤这个问题上处理就很高效了，它只需要扫描一遍主串，就能在主串中一次性查找多个模式串是否存在。

## Aho-Corasick算法 ##

`Aho-Corasick`算法一般称作AC自动机，AC自动机实际上就是在`Trie`树之上，加了类似`KMP`的`next`数组，只不过此处的`next`数组是构建在`trie`树上罢了。

AC自动机有三个核心函数，分别是：

*  `success`状态，成功转移到下一个节点（即Trie树）
 *  `failure`状态，在该节点匹配失败，则跳转到一个特定的节点，从根节点到这个特定的节点的路径恰好是失败前文本的一部分。
 *  `output`状态，匹配到了敏感词

根据以上AC算法的特点，改进`Trie`节点的属性如下：

function TrieNode(key, parent, word) { 
        this.key = key;
        this.children = [];    
        this.parent = parent;   // 该节点的父节点，用于构建failure表
        this.failure = null;    // 失效之后指向的节点
        this.word = word        // 该节点是否为某一个敏感词的尾字符 
    }

## 构建Trie树 ##

和普通的`trie`构建是一样的，逐个插入节点。假设敏感词以及待过滤的字符串，均是小写的英文字母。以英文字母的`ASCII`码作为数组下标存储节点。

## 添加`Failure`失效节点 ##

下图是以`['HER', 'HEQ', 'SHR']`构建的`trie`树：

![ac-failure.png][]

在这张图中，虚线表示failure后的指向，上面我们也说到`failure`状态的作用，就是在失配的时候告诉程序往哪里走，为什么要这么做，从这张表我们可以很清楚的看到，当我们匹配`SHER`时，程序会走右边的分支，当走到S > H > E时，会出现失配，怎么办？可能有小伙伴会想到回滚到`ROOT`从`H`开始重新匹配，但这样回溯是有成本的，我们既然走了`H`节点，为什么要回溯呢？

这个时候`failure`就发挥作用了，我们看到右分支的H有一条虚线指向了左分支的`H`，我们也知道这就是`failure`的指向，通过这个指向，我们很轻松的将当前状态移交过去。程序继续匹配`E > R`，加上移交过来的`H`，我们可以轻松的匹配到`HER`。

**问：假设有一个节点为`currNode`，它的子节点是`childNode`，那么子节点`childNode`的`failure`指向怎么求？**

解：首先，我们需要找到`childNode`父节点`currNode`的`failure`指向，假设这个指向是`Q`的话，我们就要看看`Q`的孩子（`children`属性）中有没有与`childNode`字符相同（`key`相同）的节点，如果有的话，这个节点就是`childNode`的`failure`指向。如果没有，我们就需要沿着`currNode -> failure -> failure`重复上述过程，如果一直没找到，就将其指向`root`。

由此可知，一个节点的失效指针一定在该节点的上层。需要注意的是，我们在构建`Trie`树时，并不知道`failure`指向到哪里的，所以`failure`指向需要在`Trie`树构建完成后插入。

首先将`trie`树第二层节点的失效指针指向`root`，之后逐层为每一个节点添加失效指针，即采用广度优先遍历`Trie`树：

## 敏感词过滤 ##

对于`Trie`树上的一些准备工作已经做完了，下面就是要对待匹配的字符串进行过滤。从头遍历当遇到`output`表中的节点时，就是出现了敏感词。在匹配失败的时候顺着失效节点继续匹配过程：

## 测试 ##

let trie = new Trie();
    
    // 生成trie树
    trie.insert('he');
    trie.insert('his');
    trie.insert('she');
    trie.insert('hers');
    
    trie.getFailure();
    
    // 测试数据
    trie.filter('ushers')
    
    // 该字符串出现了三个敏感词

## 完整代码 ##

[ac-failure.png]: /images/20210704/f988a78815fd45ee8a2cbe9d53c6d42e.png