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();
}
最终,一个敏感词过滤器就写好了。
当然了,这里只是最简单的过滤器,实际业务中要考虑很多情况,不过都是在此基础之上做改动。
最后,欢迎关注公众号「码农小奎」,分享编程经历和经验,一直在路上