https://www.hoshino.asia/archives/hutool

概述

由来

在我最早入职的一家公司,主要负责内容方面的业务,对我来说大部分的工作是对内容的清洗和规整。当然,清洗过程免不了的就是按照关键词过滤,你懂的。需求如下:

后台人员添加N个关键字,然后对主站所有的内容进行清洗,含有这些关键字的所有内容都置为无效。

思路

拿到此需求,我最早的方案比较粗暴:针对关键字建立一个HashSet,然后遍历整个数据库,针对每篇文章遍历这个Set,查找是否contains关键字……好吧我承认这不是一个好方法,随着关键字的增多和数据的增多,这个过程消耗的时间成指数型增长!

于是我找到度娘,发现一个算法:DFA。

DFA介绍

DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。因为本人算法学的不好,有兴趣的可以看这篇博客: 基于DFA敏感词查询的算法简析

解释起来原理其实也不难,就是用所有关键字构造一棵树,然后用正文遍历这棵树,遍历到叶子节点即表示文章中存在这个关键字。

我们暂且忽略构建关键词树的时间,每次查找正文只需要O(n)复杂度就可以搞定。

针对DFA算法以及网上的一些实现,Hutool做了整理和改进,最终形成现在的Hutool-dfa模块。

DFA查找

使用

1. 构建关键词树

WordTree tree = new WordTree();
tree.addWord("大");
tree.addWord("大土豆");
tree.addWord("土豆");
tree.addWord("刚出锅");
tree.addWord("出锅");

2. 查找关键词

//正文
String text = "我有一颗大土豆,刚出锅的";
  1. 情况一:标准匹配,匹配到最短关键词,并跳过已经匹配的关键词

// 匹配到【大】,就不再继续匹配了,因此【大土豆】不匹配
// 匹配到【刚出锅】,就跳过这三个字了,因此【出锅】不匹配(由于【刚】首先被匹配,因此长的被匹配,最短匹配只针对第一个字相同选最短)
List<String> matchAll = tree.matchAll(text, -1, false, false);
Assert.assertEquals(matchAll.toString(), "[大, 土豆, 刚出锅]");
  1. 情况二:匹配到最短关键词,不跳过已经匹配的关键词

// 【大】被匹配,最短匹配原则【大土豆】被跳过,【土豆】继续被匹配
// 【刚出锅】被匹配,由于不跳过已经匹配的词,【出锅】被匹配
matchAll = tree.matchAll(text, -1, true, false);
Assert.assertEquals(matchAll.toString(), "[大, 土豆, 刚出锅, 出锅]");
  1. 情况三:匹配到最长关键词,跳过已经匹配的关键词

// 匹配到【大】,由于非密集匹配,因此从下一个字符开始查找,匹配到【土豆】接着被匹配
// 由于【刚出锅】被匹配,由于非密集匹配,【出锅】被跳过
matchAll = tree.matchAll(text, -1, false, true);
Assert.assertEquals(matchAll.toString(), "[大, 土豆, 刚出锅]");
  1. 情况四:匹配到最长关键词,不跳过已经匹配的关键词(最全关键词)

// 匹配到【大】,由于是最长匹配,因此【大土豆】接着被匹配,由于不跳过已经匹配的关键词,【土豆】继续被匹配
// 【刚出锅】被匹配,由于不跳过已经匹配的词,【出锅】被匹配
matchAll = tree.matchAll(text, -1, true, true);
Assert.assertEquals(matchAll.toString(), "[大, 大土豆, 土豆, 刚出锅, 出锅]");

除了matchAll方法,WordTree还提供了matchisMatch两个方法,这两个方法只会查找第一个匹配的结果,这样一旦找到第一个关键字,就会停止继续匹配,大大提高了匹配效率。

针对特殊字符

有时候,正文中的关键字常常包含特殊字符,比如:"〓关键☆字",针对这种情况,Hutool提供了StopChar类,专门针对特殊字符做跳过处理,这个过程是在match方法或matchAll方法执行的时候自动去掉特殊字符。

Ciallo~(∠・ω< )⌒☆