【前缀树】写一个敏感词过滤器

1.什么是敏感词过滤

这其实是一个很常见的功能,随处可见以至于你可能都没关注过,基本上在有评论的地方都会有它的身影。

举例来说,你打游戏和别人对喷的时候,是不是一些脏话发不出去哈哈,这些词汇会用***代替。

再比如,一些话题和视频下评论*词、色情低俗等等都是需要过滤的。

那这种过滤是怎么实现的呢?

那就不得不聊一聊一种数据结构了,那就是前缀树。

2.前缀树

前缀树是树的一种扩展类型,其实结构本身还是挺简单的,难点在于对这个结构制定的算法。

它的结构是按照敏感词来构建的,假设abc,be,bf这三个词是敏感词,

则前缀树的结构图如下:
【前缀树】写一个敏感词过滤器

根结点为空,每个子结点存放敏感词的字母,而从根结点出发到叶子结点这条路径表示为一个敏感词。

这样看来,给定一个字符串,如果其中有一部分能和一条路径匹配,则匹配的那部分就是敏感词,可以把该部分字符串替换为**。

比如给定字符串xwyabckk,其中有字符串abc和前缀树的一条路径匹配,可以把匹配的部分替换为***,那么过滤后的字符串为xwy***kk。

可是,假如abc和ab都是敏感词呢?那ab这个词是不会走到叶子结点的,就不被认为是敏感词了。

怎么改进呢?很简单,每个结点加一个标识位,也就是一个布尔值。

标识位为true表示到这个结点为敏感词,为false则表示从根结点到这个结点的路径表示的词不是敏感词。

这个标识位在图里用五角星表示了:

【前缀树】写一个敏感词过滤器

3.如何用代码实现前缀树和过滤算法

核心思想是用三个指针来实现过滤。

指针root指向前缀树的根结点,指针begin指向文本的起始位置,指针position指向过滤文本的最后位置。

图示如下:

【前缀树】写一个敏感词过滤器

在进行过滤算法前,首先需要创建这颗前缀树。

先创建前缀树的数据结构,这里拿java实现,其他语言大同小异。

// 前缀树结构
private class TrieNode {
  // 关键词结束标识
  private boolean isKeywordEnd = false;

  // 子节点(key是下级字符,value是下级节点)
  private Map<Character, TrieNode> subNodes = new HashMap<>();

  public boolean isKeywordEnd() {
    return isKeywordEnd;
  }

  public void setKeywordEnd(boolean keywordEnd) {
    isKeywordEnd = keywordEnd;
  }

  // 添加子节点
  public void addSubNode(Character c, TrieNode node) {
    subNodes.put(c, node);
  }

  // 获取子节点
  public TrieNode getSubNode(Character c) {
    return subNodes.get(c);
  }

有了前缀树的数据结构,接下来就要构建这颗树了,在此之前,你要先明确过滤的词有哪些,可以放到一个文本文件中读取。

然后根据敏感词构建前缀树。这里便写一个差入敏感词构建前缀树的方法:

// 将敏感词添加到前缀树
private void addKeyword(String keyword) {
  TrieNode tempNode = rootNode;
  for (int i = 0; i < keyword.length(); i++) {
    char c = keyword.charAt(i);
    TrieNode subNode = tempNode.getSubNode(c);
    if(subNode == null) {
      // 初始化子节点
      subNode = new TrieNode();
      tempNode.addSubNode(c, subNode);
    }
    // 指针指向子节点,进入下一轮循环
    tempNode = subNode;
    // 设置结束标识
    if(i == keyword.length() - 1) {
      tempNode.setKeywordEnd(true);
    }
  }
}

这棵树构建完毕,接下来就是写如何过滤的算法了,这里写一个函数。

这个函数负责过滤,参数为输入的需要过滤的字符串,输出为过滤好的字符串。

/**
	* 过滤敏感词
  * @param text 待过滤文本
  * @return 过滤后的文本
  */
public String filter(String text) {
  if(StringUtils.isBlank(text)) {
    return null;
  }
  // 指针1:指向树的节点
  TrieNode tempNode = rootNode;
  // 指针2:指向敏感词的开始索引
  int begin = 0;
  // 指针3:指向敏感词的结尾索引
  int position = 0;
  // 存放结果
  StringBuilder sb = new StringBuilder();

  while (position < text.length()) {
    char c = text.charAt(position);
    // 跳过符号 isSymbol判断该字符是否为符号
    // 这里是为了防止用户在敏感词中间输入符号 例如【傻、逼】,中间有符号也可以过滤
    if(isSymbol(c)) {
      // 若指针1处于根节点,将词符号计入结果,指针2向下走一步
      if(tempNode == rootNode) {
        sb.append(c);
        begin++;
      }
      // 无论符号在开头或中间,指针3都向下走一步
      position++;
      continue;
    }
    // 检查下级节点
    tempNode = tempNode.getSubNode(c);
    if(tempNode == null) {
      // 以begin开头的字符串不是敏感词
      sb.append(text.charAt(begin));
      // 进入下一个位置
      position = ++begin;
      // 指针1重新指向根节点
      tempNode = rootNode;
    } else if(tempNode.isKeywordEnd()) {
      // 发现敏感词begin-position,将其替换
      sb.append(REPLACEMENT);
      // 进入下一位置
      begin = ++position;
      // 指针1重新指向根节点
      tempNode = rootNode;
    } else {
      // 继续检查下一个字符
      position++;
    }
  }
  // 将最后一批字符计入结果
  sb.append(text.substring(begin));
  return sb.toString();
}

最终,一个敏感词过滤器就写好了。

当然了,这里只是最简单的过滤器,实际业务中要考虑很多情况,不过都是在此基础之上做改动。


最后,欢迎关注公众号「码农小奎」,分享编程经历和经验,一直在路上
【前缀树】写一个敏感词过滤器

上一篇:C----双向链表


下一篇:LeetCode刷题(16)【简单】移除链表元素&&回文链表&&删除链表中的结点