关键词匹配——HashMap已死，Trie树称王

逃离我推掉我的手 2023-10-02 15:15 2阅读 0赞

> 你好，我是小黄，一名独角兽企业的Java开发工程师。  
> 感谢茫茫人海中我们能够相遇，  
> 俗话说：当你的才华和能力，不足以支撑你的梦想的时候，请静下心来学习，  
> 希望优秀的你可以和我一起学习，一起努力，实现属于自己的梦想。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

#### 文章目录 ####

*  一、引言
 *  二、何为关键词匹配
 *  三、何为Trie树
 *  四、为什么不直接使用HashMap
 *  五、Trie树的代码实现
 *   *  1、Trie的初始化
     *  2、Trie添加字符串
     *  3、Trie查询字符串出现的频率
     *  4、Trie删除字符串
 *  六、总结

## 一、引言 ##

上周在公司的周会上，谈到这样一件事，对于风控行业来说，关键词匹配是一个比较重要的业务之一，而关键字匹配的效率，也是众多风控者关注的重要指标。

如何使用一种既方便又快捷的方案进行关键字的匹配呢，风控常见做法是 **Trie树** ，今天我们就来看一下关键词匹配界的霸主——**Trie树（前缀树）**。

## 二、何为关键词匹配 ##

对于风控来说，每天处理的风控信息杂七杂八，其中比较重要的一个业务方向——**关键字匹配**

![在这里插入图片描述][477d59830e9d45fe8af73d9ce5ee75f1.png]

简单来说，如果用户输入傻逼、卧槽、我要炸学校…等一系列的违规词语，我们需要去我们的关键词表中进行匹配，最终返回结果：**这是一个违规词语**

这样看起来可能不够人性化，我们可以对其关键词表进行 **打标签** 的操作，将我们关键词表，打上涉政、涉黄、涉恐等一系列的标签。

这样，我们的整套流程看起来已经非常人性化了

## 三、何为Trie树 ##

字典树，顾名思义，是关于“字典”的一棵树。即：它是对于字典的一种存储方式（所以是一种数据结构而不是算法）。这个词典中的每个“单词”就是从根节点出发一直到某一个目标节点的路径，路径中每条边的字母连起来就是一个单词。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_11_color_FFFFFF_t_70_g_se_x_16]

*  （标橙色的节点是“目标节点“，即根节点到这个目标节点的路径上的所有字母构成了一个单词。）

从这张图我们可以看出，字典树就是一棵树，只不过，这棵树的每条边上都有一个字母，然后这棵树的一些节点被指定成了标记节点（目标节点）而已。

这就是字典树的概念。结合上面说的概念，上图所示的字典树包括的单词分别为：`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树的代码实现 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_11_color_FFFFFF_t_70_g_se_x_16 1]

### 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树` 的代码也需要多写几遍，博主写这篇博客的时候，又忘记了怎么写（逃

*  题目一：[208. 实现 Trie (前缀树)【基础题】][208. _ Trie]
 *  题目二：[211. 添加与搜索单词 - 数据结构设计【需要一些DFS知识】][211. _ - _DFS]

对源代码有兴趣的小伙伴，可以关注 `爱敲代码的小黄` 公众号，回复：**算法源码** 即可获得算法源码

本期的内容就到这里，下期 **一定一定一定** 会讲述 **最小生成树（Prim、Kruskal）** 算法。

我是一名独角兽企业的Java开发工程师，希望可以点个关注呀，有问题可以留言或者私信加我微信：**hls1793929520**，我们下期再见！

![在这里插入图片描述][f56dab9358d59e78cdf7352e966dc172.png]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/f34ae532a7d34322a9819b3bfeaf7a82.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[477d59830e9d45fe8af73d9ce5ee75f1.png]: https://img-blog.csdnimg.cn/477d59830e9d45fe8af73d9ce5ee75f1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_11_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/c791e5e1c0554748891528767a7fc99a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_11,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_11_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/8cdf552df7cb46159c21e1363d69e76b.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_11,color_FFFFFF,t_70,g_se,x_16
[208. _ Trie]: https://leetcode-cn.com/problems/implement-trie-prefix-tree/
[211. _ - _DFS]: https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/
[f56dab9358d59e78cdf7352e966dc172.png]: https://img-blog.csdnimg.cn/img_convert/f56dab9358d59e78cdf7352e966dc172.png