敏感词过滤Aho-Corasick算法

多模式串匹配算法简介

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

字符串匹配算法有很多比如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树：

在这张图中，虚线表示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
    }
}

敏感词过滤

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

function filter(word) {
  let children = this.root.children;
  let currentNode = this.root;
  
  for(let i=0; i<word.length; i++){
    
    while(currentNode.children[word[i].charCodeAt() - 97] == null && currentNode != this.root) {
      currentNode = currentNode.failure;
    }
    
    currentNode = currentNode.children[word[i].charCodeAt() - 97];
    if (currentNode == null) {
      currentNode = this.root;
    }
    let temNode = currentNode;

    while(temNode != this.root) {
      if(temNode.word === true) {
        console.log('出现了敏感词');
      } 
      temNode = temNode.failure;
    }
  }
}

测试

let trie = new Trie();

// 生成trie树
trie.insert('he');
trie.insert('his');
trie.insert('she');
trie.insert('hers');

trie.getFailure();

// 测试数据
trie.filter('ushers')

// 该字符串出现了三个敏感词

完整代码

function TrieNode(key, parent, word) {
    this.key = key;
    this.children = [];
    this.parent = parent;
    this.failure = null;
    this.word = word
}

function Trie() {
    this.root = new TrieNode('/', null, false); // 添加根节点
    this.insert = insert; // 插入
    this.insertData = insertData;
  
    this.getFailure = getFailure;
    this.filter = filter;
}

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); 
    }
}

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
    }
}

function filter(word) {
  let children = this.root.children;
  let currentNode = this.root;
  
  for(let i=0; i<word.length; i++){
    
    while(currentNode.children[word[i].charCodeAt() - 97] == null && currentNode != this.root) {
      currentNode = currentNode.failure;
    }
    
    currentNode = currentNode.children[word[i].charCodeAt() - 97];
    if (currentNode == null) {
      currentNode = this.root;
    }
    let temNode = currentNode;

    while(temNode != this.root) {
      if(temNode.word === true) {
        console.log('出现了敏感词');
      } 
      temNode = temNode.failure;
    }
  }
}

let trie = new Trie();

// 生成trie树
trie.insert('he');
trie.insert('his');
trie.insert('she');
trie.insert('hers');

trie.getFailure();

// 测试数据
trie.filter('ushers')

参考资料

• TypeScript：Aho–Corasick算法实现敏感词过滤

• Aho-Corasick算法的Java实现与分析

• 36 | AC自动机：如何用多模式串匹配实现敏感词过滤功能？