一、引言
上周在公司的周会上，谈到这样一件事，对于风控行业来说，关键词匹配是一个比较重要的业务之一，而关键字匹配的效率，也是众多风控者关注的重要指标。
如何使用一种既方便又快捷的方案进行关键字的匹配呢，风控常见做法是 Trie树 ，今天我们就来看一下关键词匹配界的霸主——Trie树（前缀树）。
二、何为关键词匹配
对于风控来说，每天处理的风控信息杂七杂八，其中比较重要的一个业务方向——关键字匹配
简单来说，如果用户输入傻逼、卧槽、我要炸学校…等一系列的违规词语，我们需要去我们的关键词表中进行匹配，最终返回结果：这是一个违规词语
这样看起来可能不够人性化，我们可以对其关键词表进行 打标签 的操作，将我们关键词表，打上涉政、涉黄、涉恐等一系列的标签。
这样，我们的整套流程看起来已经非常人性化了
三、何为Trie树
字典树，顾名思义，是关于“字典”的一棵树。即：它是对于字典的一种存储方式（所以是一种数据结构而不是算法）。这个词典中的每个“单词”就是从根节点出发一直到某一个目标节点的路径，路径中每条边的字母连起来就是一个单词。
- （标橙色的节点是“目标节点“，即根节点到这个目标节点的路径上的所有字母构成了一个单词。）
从这张图我们可以看出，字典树就是一棵树，只不过，这棵树的每条边上都有一个字母，然后这棵树的一些节点被指定成了标记节点（目标节点）而已。
这就是字典树的概念。结合上面说的概念，上图所示的字典树包括的单词分别为：a、abc、bac、bbc、ca
Trie树功能如下：
- 维护字符串集合（即字典）
- 向字符串集合中插入字符串（即建树）
- 查询字符串集合中是否有某个字符串（即查询）
- 统计字符串在集合中出现的个数（即统计）
- 将字符串集合按字典序排序（即字典序排序）
- 求集合内两个字符串的LCP（Longest CommonPrefix，最长公共前缀）（即求最长公共前缀）
四、为什么不直接使用HashMap
首先，我们要明确我们的目的，为了业务去追寻相应的技术，才是最佳实现方式我们要明确一点，对于 HashMap 来说，查询效率为 O(1) 的前提是：忽略单样本的大小
对于这一点，我们来看下面代码：
String类
// 计算字符串的hashCode public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }
HashMap类
public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
我们可以看到 当我们往HashMap存放一个字符串时，他会遍历整个字符串获取其 hashCode
这样的话，如果我们不忽略样本大小的话，那么我们的时间复杂度其实是：O(K)，K为字符串的大小
如果我们当前查询该字符串出现的频率，我们从技术上使用 HashMap 和 Trie树 区别是不大的，但是在我们的业务落地时，对于关键词那么大的数据，你使用 HashMap 占据的空间岂不是造成浪费
如果我想要查询以 “abc” 为前缀出现的字符串，我们的 HashMap 是不支持的，而 trie树 就很好的支持了这一点
总体而言，对于关键词的匹配，为了避免空间的浪费和业务的多元化，使用 trie树 的效率远大于 HashMap
五、Trie树的代码实现
1、Trie的初始化
我们本文的 Trie树 代码假设所有出现的字符串均为小写字母
- pass：通过该点的字符串数量
- end：结束该点的字符串数量
- tries：子树
class Trie { int pass; int end; Trie[] tries; public Trie() { pass = 0; end = 0; tries = new Trie[26]; } }
2、Trie添加字符串
public void insert(String word) { if (word == null) { return; } char[] str = word.toCharArray(); Trie trie = this; int path = 0; for (int i = 0; i < str.length; i++) { path = str[i] - 'a'; // 看一下子树是不是已经存在，如果不存在，则进行创建 if (trie.tries[path] == null) { trie.tries[path] = new Trie(); } trie.pass++; trie = trie.tries[path]; } trie.end++; }
3、Trie查询字符串出现的频率
/** * 该字符串出现了几次 * * @param word * @return */ public int search(String word) { if (word == null) { return 0; } char[] str = word.toCharArray(); Node node = root; int path = 0; for (int i = 0; i < str.length; i++) { path = str[i] - 'a'; if (node.nodes[path] == null) { return 0; } node = node.nodes[path]; } return node.end; }
4、Trie删除字符串
- Java选手直接置为
null，GC即可回收，C++选手要手动回收
public void delete(String word) { if (search(word) == 0) { return; } char[] str = word.toCharArray(); Node node = root; int path = 0; for (int i = 0; i < str.length; i++) { path = str[i] - 'a'; if (--node.nodes[path].pass == 0) { // Java垃圾回收直接回收掉 node.nodes[path] = null; return; } node = node.nodes[path]; } node.end--; }
六、总结
关于 Trie树 的介绍到这就已经结束了，大家可以思考下 HashMap 和 Trie树 的差距，想一下哪个才是最优解，毕竟博主也有可能写错了呢（题主必不可能写错，逃）
同时，对于 Trie树 的代码也需要多写几遍，博主写这篇博客的时候，又忘记了怎么写（逃
