前缀树过滤敏感词
1.思想
三个指针，一个指向前缀树，两个在字符串上。其中在字符串上的指针代表着某个和敏感词匹配的字符串首部和尾部。
2.代码实现（使用环境SpringBoot）
1.定义敏感词
resources目录下新建一个sensitive-words.txt文件
2.定义前缀树
util包下的SensitiveFilter类中定义了内部类TrieNode类。
@Component
public class SensitiveFilter {
private static final Logger logger = LoggerFactory.getLogger(SensitiveFilter.class);
// 替换符
private static final String REPLACEMENT = "***";
// 根节点
private TrieNode rootNode = new TrieNode();
@PostConstruct
public void init() {
try (
InputStream is = this.getClass().getClassLoader().getResourceAsStream("sensitive-words.txt");
BufferedReader reader = new BufferedReader(new InputStreamReader(is));
) {
String keyword;
while ((keyword = reader.readLine()) != null) {
// 添加到前缀树
this.addKeyword(keyword);
}
} catch (IOException e) {
logger.error("加载敏感词文件失败: " + e.getMessage());
}
}
}3.根据敏感词初始化前缀树
在SensitiveFilter类中添加如下代码
// 将一个敏感词添加到前缀树中
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);
}
}
}4.过滤敏感词方法并测试
版本1：以指针3到达尾部为结束。已知敏感词有 fabcd 和 abc, 要核验的字符串的最后一段为 fabc时，abc不能完成过滤。（测试用例中屏蔽的love和iloveyou，显然ilove中的love没有屏蔽）
public String filter1(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);
// 跳过符号
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;
// 重新指向根节点
tempNode = rootNode;
} else if (tempNode.isKeywordEnd()) {
// 发现敏感词,将begin~position字符串替换掉
sb.append(REPLACEMENT);
// 进入下一个位置
begin = ++position;
// 重新指向根节点
tempNode = rootNode;
} else {
// 检查下一个字符
position++;
}
}
// 将最后一批字符计入结果
sb.append(text.substring(begin));
return sb.toString();
}
// 判断是否为符号
private boolean isSymbol(Character c) {
// 0x2E80~0x9FFF 是东亚文字范围
return !CharUtils.isAsciiAlphanumeric(c) && (c < 0x2E80 || c > 0x9FFF);
}
版本2：在指针3的基础上进行修改，修改了最后的边界条件。但出现了新的问题，那就是入已知敏感词fabcd和abc，检验的字符串为☆f☆a☆b☆c☆，无法屏蔽abc。
结果：
//版本2代码
public String filter(String text) {
//若是空字符串 返回空
if (StringUtils.isBlank(text)) {
return null;
}
// 根节点
// 每次在目标字符串中找到一个敏感词，完成替换之后，都要再次从根节点遍历树开始一次新的过滤
TrieNode tempNode = rootNode;
// begin指针作用是目标字符串每次过滤的开头
int begin = 0;
// position指针的作用是指向待过滤的字符
// 若position指向的字符是敏感词的结尾，那么text.subString(begin,position+1)就是一个敏感词
int position = 0;
//过滤后的结果
StringBuilder result = new StringBuilder();
//开始遍历 position移动到目标字符串尾部是 循环结束
while (position < text.length()) {
// 最开始时begin指向0 是第一次过滤的开始
// position也是0
char c = text.charAt(position);
//忽略用户故意输入的符号 例如嫖※娼 忽略※后 前后字符其实也是敏感词
if (isSymbol(c)) {
//判断当前节点是否为根节点
//若是根节点 则代表目标字符串第一次过滤或者目标字符串中已经被遍历了一部分
//因为每次过滤掉一个敏感词时，都要将tempNode重新置为根节点,以重新去前缀树中继续过滤目标字符串剩下的部分
//因此若是根节点，代表依次新的过滤刚开始，可以直接将该特殊符号字符放入到结果字符串中
if (tempNode == rootNode) {
//将用户输入的符号添加到result中
result.append(c);
//此时将单词begin指针向后移动一位，以开始新的一个单词过滤
begin++;
}
// if(position==text.length()-1){
// begin++;
// position=begin;
// continue;
// }
//若当前节点不是根节点，那说明符号字符后的字符还需要继续过滤
//所以单词开头位begin不变化，position向后移动一位继续过滤
position++;
continue;
}
//判断当前节点的子节点是否有目标字符c
tempNode = tempNode.getSubNode(c);
//如果没有 代表当前beigin-position之间的字符串不是敏感词
// 但begin+1-position却不一定不是敏感词
if (tempNode == null) {
//所以只将begin指向的字符放入过滤结果
result.append(text.charAt(begin));
//position和begin都指向begin+1
position = ++begin;
//再次过滤
tempNode = rootNode;
} else if (tempNode.isKeywordEnd()) {
//如果找到了子节点且子节点是敏感词的结尾
//则当前begin-position间的字符串是敏感词 将敏感词替换掉
result.append(REPLACEMENT);
//begin移动到敏感词的下一位
begin = ++position;
//再次过滤
tempNode = rootNode;
//&& begin < position - 1
} else if (position + 1 == text.length()) {
//特殊情况
//虽然position指向的字符在树中存在，但不是敏感词结尾，并且position到了目标字符串末尾（这个重要）
//因此begin-position之间的字符串不是敏感词 但begin+1-position之间的不一定不是敏感词
//所以只将begin指向的字符放入过滤结果
result.append(text.charAt(begin));
//position和begin都指向begin+1
position = ++begin;
//再次过滤
tempNode = rootNode;
} else {
//position指向的字符在树中存在，但不是敏感词结尾，并且position没有到目标字符串末尾
position++;
}
}
return begin < text.length() ? result.append(text.substring(begin)).toString() : result.toString();
}版本3：刚刚在版本2中有一段注释掉的代码，就是讨论的这种情况。当到达最后一位时，认为没有匹配上敏感词，因此将当前遍历的字符添加到了最终的结果集，而改进就是：当遍历到最后，仍是符号时，进行二指针的下一个字符去比较，并更新三指针和二指针指向同一位置。即下面的代码取消注释即可
// if(position==text.length()-1){
// begin++;
// position=begin;
// continue;
// }版本4：使用二指针比较。在修改完版本1出现的问题后，同样需要加上版本3上加上的代码，否则碰见☆f☆a☆b☆c☆这样的，会直接由于三指针++而越界抛出异常。造成这个现象的原因是，遍历到最后的c后面的符号时，认为应该跳过符号，从而跳过后越界。因此加上版本3中的代码就会不会越界，还会屏蔽版本2中的问题，或者是像版本2中的那样，考虑尾部的边界问题。（版本2解决了版本1的问题，但出现☆f☆a☆b☆c☆不能屏蔽）（版本2加上3中那部分代码就完美了）（版本4不加版本3中标出的代码也可以解决版本1的问题，但出现☆f☆a☆b☆c☆会直接报错）（因此最优解就是版本4和版本3）
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 (begin < text.length()) {
char c = text.charAt(position);
//跳过符号
if(isSymbol(c)){
//若指针1处于根节点，将此符号计入结果，让指针2向下走一步
if(tempNode==rootNode){
sb.append(c);
begin++;
}
//如果最后一位仍然是符号，那就比较下一个，不能直接加，否则会越界
if(position==text.length()-1){
begin++;
position=begin;
continue;
}
//无论符号在开头或者中间指针3都向下走一步
position++;
continue;
}
// 检查下级节点
tempNode = tempNode.getSubNode(c);
if (tempNode == null) {
// 以begin开头的字符串不是敏感词
sb.append(text.charAt(begin));
// 进入下一个位置
position = ++begin;
// 重新指向根节点
tempNode = rootNode;
} else if (tempNode.isKeywordEnd()) {
// 发现敏感词,将begin~position字符串替换掉
sb.append(REPLACEMENT);
// 进入下一个位置
begin = ++position;
// 重新指向根节点
tempNode = rootNode;
} else {
// 检查下一个字符
if (position < text.length() - 1) {
position++;
}
}
}
return sb.toString();
}
京公网安备 11010502036488号