说来话长
小时候玩的一款红白机游戏三国志，在选君主的时候相当于有很多分支路线，最终可以到达指定的君主。
前两年有次自己研究字符串，按字符分割成上面这种结构，还写过代码实现。最近公司技术分享，噢噢原来这叫做前缀树啊！😊
前缀树
前缀树（Trie树），每一个节点存储字符串的一个字符，多个节点组合起来形成一个完整的字符串。
- 根节点不包含字符串，除了根节点，其他节点都只包含一个字符；
- 每个节点的所有子节点包含的字符都不相同；
- 从根节点到某个子节点，节点的字符连接起来形成一个字符串；
- 每个节点的子节点拥有相同的前缀。
前缀树有几个典型应用场景；
- 字符串的快速检索
- 最长公共前缀
构建过程
例如有一批词，“中国人”、“中国力量”、“共和国”、“中国”，有前缀树；
查找匹配就比较简单了，比如有一段话：“今天，中国人民站起来了！”需要校验是否包含上述词。从“今”开始，逐个与前缀树进行匹配，直到匹配成功，例如这里的“中国”
数据结构
通常树形结构，我都会用链表存储。但这里为了提高查找效率，可以换成 map 结构；
json
{
"中": {
"国": {
"力": {
"量": {
"$end$": true
},
"$end$": false
},
"人": {
"$end$": true
},
"$end$": true
}
},
"共": {
"和": {
"国": {
"$end$": true
},
"$end$": false
},
"$end$": false
}
}小试牛刀
编写一个敏感词工具类，提供是否命中敏感词的方法；
java
/**
* 敏感词工具类
*/
public class SensitiveWordService {
/**
* 前缀树 map
*/
private final Map<String, Object> map = new HashMap<>();
/**
* 结束标志
*/
private static final String END = "$END$";
/**
* 添加敏感词
*
* @param word 敏感词
*/
public void add(String word) {
// 每个关键词开始，都将前缀 map 重置为初始的 map
Map<String, Object> prefixMap = map;
for (int i = 0; i < word.toCharArray().length; i++) {
String key = String.valueOf(word.charAt(i));
Map<String, Object> currentMap = (Map<String, Object>) prefixMap.get(key);
if (Objects.isNull(currentMap)) {
currentMap = new HashMap<>();
prefixMap.put(key, currentMap);
}
boolean end = (boolean) currentMap.getOrDefault(END, false);
currentMap.put(END, end || (i == word.length() - 1));
// 然后遍历的过程依次像下设置前缀 map
prefixMap = currentMap;
}
}
private boolean remove(String word, int index, Map<String, Object> prefixMap) {
if (index >= word.length()) {
return true;
}
String key = String.valueOf(word.charAt(index));
Map<String, Object> currentMap = (Map<String, Object>) prefixMap.get(key);
if (Objects.isNull(currentMap)) {
return false;
}
boolean remove = remove(word, index + 1, currentMap);
boolean single = currentMap.size() == 1;
// 词尾需要先重置 END 标志位
if (index == word.length() - 1) {
currentMap.put(END, false);
}
// 下一个字符不能被删除，或者当前字符还有后缀字符，则当前节点不能删除
if (!remove || !single) {
return false;
}
prefixMap.remove(key);
return true;
}
/**
* 移除敏感词
*
* @param word 敏感词
* @return 是否完全移除
*/
public boolean remove(String word) {
return remove(word, 0, map);
}
private boolean hit(String string, int index, Map<String, Object> prefixMap) {
if (index >= string.length()) {
return false;
}
String key = String.valueOf(string.charAt(index));
Map<String, Object> currentMap = (Map<String, Object>) prefixMap.get(key);
if (Objects.isNull(currentMap)) {
return hit(string, index + 1, map);
}
boolean end = (boolean) currentMap.getOrDefault(END, false);
if (end) {
return true;
}
// 注意这里，优先用下个字符下个前缀 map 进行匹配查找，找不到向下移位
return hit(string, index + 1, currentMap) || hit(string, index + 1, map);
}
/**
* 是否命中敏感词
*
* @param string 待校验文本
* @return 命中结果
*/
public boolean hit(String string) {
return hit(string, 0, map);
}
public static void main(String[] args) {
List<String> list = Arrays.asList("中国", "中国人", "中国力量", "共和国");
SensitiveWordService service = new SensitiveWordService();
list.forEach(service::add);
System.out.println(service.map);
service.remove("中国");
System.out.println(service.map);
System.out.println(service.hit("中国"));
}
}我在编写过程中有两个小问题耽搁了会，一个是 remove 的逻辑有点点绕，需要递归至词尾开始逐个尝试删除；另一个是 hit 时本身就是一个前缀树的递归过程，但同时也是待匹配文本词头向词尾的递归过程。