敏感词过滤算法Aho-Corasick

作者: mah93 | 来源:发表于2019-10-10 08:58 被阅读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码作为数组下标存储节点。

function insert(data) {
    this.insertData(data, this.root);
}

function insertData(data, node){
    if (data === '') {
        return;
    }

    let children = node.children;
    let haveData = children[data[0].charCodeAt() - 97];
      
    if(haveData) {
        this.insertData(data.substring(1), haveData);
    }else{
        let isWord = data.length === 1;
        let insertNode = new TrieNode(data[0], node, isWord);
        children[data[0].charCodeAt() - 97] = insertNode;
        this.insertData(data.substring(1), insertNode); 
    }
}

添加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树：

function getFailure() {
  let currQueue = Object.values(this.root.children);
  
  while (currQueue.length > 0) {
      let nextQueue = [];

      for (let i = 0; i < currQueue.length; i++) {
        let node = currQueue[i]
        let key = node.key
        let parent = node.parent
        node.failure = this.root
        for (let k in node.children) {
          nextQueue.push(node.children[k])
        }

        if (parent) {
          let failure = parent.failure
          while (failure) {
            let children = failure.children[key.charCodeAt() - 97]
            if (children) {
              node.failure = children
              break;
            }
            failure = failure.failure
          }
        }
      }

      currQueue = nextQueue
    }
}