前缀树根节点为空，其他节点只包含一个字符。
从根节点到某节点，连起来的每个路径，就是当前节点的字符串。
例如：敏感词构成一个前缀树
3个指针：1指针指向根节点，2指针一直往前走，3指针往返
前缀树的数据结构，util包下的SensitiveFilter.java。
主要有两个成员变量，关键词结束标志和子节点，在节点的数据结构中建立hashmap用于存储结构。
private class TrieNode {
// 关键词结束标志
private boolean isKeywordEnd = false;
// 子节点(key是下级字符，value是下级节点)
private Map subNodes = new HashMap<>(16);
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);
}
}
2、根据敏感词初始化前缀树
读取敏感词文件中的所有敏感词，构造敏感词构成的前缀树。每读取到一个敏感词，就加到前缀树中。
其中将一个敏感词加入到前缀树的操作：先新建一个子节点，然后再通过本节点hashmap的put操作，将子节点添加到本节点的map中。例如，添加abc就需要新建a节点，根节点put（a，a节点），新建b节点…，新建c节点…；添加完abc敏感词后，再添加abd时，只需要一直循环到b节点后，新建c节点，map对应关系即可。
@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() {
long start = System.currentTimeMillis();
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());
e.printStackTrace();
}
LOGGER.info("构建前缀树时间：" + String.valueOf(System.currentTimeMillis() - start) + "ms");
}
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);
}
}
}
private boolean isSymbol(char c) {
// 0x2E80 到 0x9FFF为东亚文字
return !CharUtils.isAsciiAlphanumeric(c) && (c < 0x2E80 || c > 0x9FFF);
}
}
3、过滤敏感词
过滤某个字符串的敏感词，如果有，则转化为***。这里新建一个字符串，不是敏感词的，直接append，是敏感词的，append（）。
指针1为根节点，指针2一直往前走，指针3往返，新建一个字符串。
如果遇到符号，符号再begin位置，则指针2、3都加一，否则指针3加一。
begin不动，position不断增加。
如果遇到了完整的敏感词（即标志位为真），将position-begin替换为*，添加到新字符串，然后begin = position+1。
如果没有敏感词，将该字符添加到新字符串中，begin = position + 1。
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()) {
if (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++;
}
}
// position遍历越界仍未匹配到敏感词
else {
sb.append(text.charAt(begin));
position = ++begin;
tempNode = rootNode;
}
}
return sb.toString();
}
4、难点
遇到敏感词为fabcd和abc，要检测的字符串最后一段为fabc
原来以指针3position作为循环判断条件，此时指针2为f，循环之后指针3为c，c不是fabcd的敏感词标志位节点，所以直接跳出了，没有检测f之后的字符作为begin的情况。
所以要以指针2begin作为循环条件。
