Trie树及其优化

一时失言乱红尘 2022-09-15 06:08 237阅读 0赞

### 文章目录 ###

*  1 Trie树简介
 *  2 比较
 *   *  2.1 HashMap
     *  2.2 ElasticSearch
 *  3 实现Trie树
 *  4 使用DoubleArrayTrie降低空间复杂度

# 1 Trie树简介 #

Trie又称前缀树或字典树，有如下特性：

*  除根节点为空外，其每个节点都表示一个字符
 *  一个节点的所有子孙都有相同的前缀
 *  从根节点出发，到某一end节点，则表示一个字符串

一下是一个简单的例子：在trie树中插入多个子串\[she, he, her, this, his, is\]

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

蓝色的节点表示end节点，即从root出发到end节点表示一个子串。

当我们要查找主串sherthis，是否存在一个从首字符起**前缀相同**的子串时（如果是查找子串，则需要为trie加上fail指针，即AC自动机，这里不讲），我们便可以在trie上以O(n)的时间复杂度完成查找。

从上边的例子中，我们可以看到在前缀匹配中，trie拥有不俗查找效率外，还能够对公共前缀进行空间上的压缩。

Trie树主要可以应用在各种字符串前缀匹配的场景下，如搜索提示、词频统计等。

看完后依然不明白，可以手动实现一遍LeetCode208题。

# 2 比较 #

## 2.1 HashMap ##

HashMap可以在O(1)的时间复杂度和O(n)的时间复杂度内，完成对字符串的匹配。

但其只能使用在字符串精确匹配，而无法应对前缀匹配场景。

## 2.2 ElasticSearch ##

除了自己实现数据结构去应对业务场景外，同样可以考虑借助一些中间件帮助我们干活。

ElasticSearch作为一款分布式搜索引擎，是否能够实现高效的前缀匹配呢？

ES提供有prefix前缀查询功能，可以支持前缀匹配功能。以匹配W1前缀为例，工作流程如下：

1.  扫描词列表并查找第一个以W1开始词
2.  搜集关联的文档ID
3.  移动到下一个词
4.  如果这个词也是以W1开头，查询跳回到第二步再重复执行，直到下一词不以W1为止

但官方文档中同时也建议要小心使用该功能，避免搜索过大的词集合（换句话说，也就是输入的前缀能够匹配上的词越少，效率越高）。

> `prefix` 查询或过滤对于一些特定的匹配是有效的，但使用方式还是应当注意。当字段中词的集合很小时，可以放心使用，但是它的伸缩性并不好，会对我们的集群带来很多压力。可以使用较长的前缀来限制这种影响，减少需要访问的量。

所以可以看到ElasticSearch可以解决前缀匹配的问题，但是要考虑前缀串的特性，并且要依赖中间件。

# 3 实现Trie树 #

这里就不贴实现了，网上的代码有很多。

如果你思考过如何实现Trie树，或则尝试解决了LeetCode208题，你或许发现可以使用HashMap或则数组去存储父子节点关系。

但不幸的是，在特定的业务场景和数据量比较小的情况，它们能够正确的运行。但数据量太大的话，这两种实现恐怕就无法胜任工作了。

使用HashMap需要new大量的对象，对GC并不友好，并且hashMap自身的数据结构对内存的占用较高。

使用数组则不够灵活，因为插入的字符可不一定是26个英文字符，数组大小难以估算，并且哪怕是只有一个子节点，也需要开辟一个完整的数组。

那有没有一种在O(1)时间复杂度下，能以更小的空间复杂度实现父子节点关系的存储呢？

有，它便是双数组（DoubleArrayTrie）。

# 4 使用DoubleArrayTrie降低空间复杂度 #

简单的说，DoubleArrayTrie本质是一个确定有限状态自动机（DFA），使用两个线性数组（base数组和check数组）来表示Trie树，对Trie的结构进行了空间上的压缩，但同时不降低查询速度。

在这里不做更多DoubleArrayTrie构建和查找原理上的介绍，感兴趣这里贴几篇高质量的文章（让我写并不会写得比他们更好），足够让你理解DoubleArrayTrie的原理和实现了。

[《DoubleArrayTrie的Java实现》][DoubleArrayTrie_Java]

[《最好懂的DoubleArrayTrie构建与遍历流程》][DoubleArrayTrie]

《计算的本质：深入剖析程序和计算机》3.1节 确定性有限自动机

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmhpbmU0MDQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/be6ba968007f458ca8cd1b2f0ebb1520.png
[DoubleArrayTrie_Java]: https://www.hankcs.com/program/java/%E5%8F%8C%E6%95%B0%E7%BB%84trie%E6%A0%91doublearraytriejava%E5%AE%9E%E7%8E%B0.html
[DoubleArrayTrie]: https://www.cnblogs.com/zhangchaoyang/articles/4508266.html