Trie 树(字典树)

Trie 树，即字典树，又称单词查找树或键树，是一种树形结构。

典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

Trie 的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有 3 个基本性质：

  • 根节点不包含字符，除根节点外每一个节点都只包含一个字符
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
  • 每个节点的所有子节点包含的字符都不相同

1. 10 个频繁出现的词

问题

一个文本文件，大约有一万行，每行一个词，要求统计出其中出现次数最频繁的 10 个词，请给出思路和时间复杂度的分析。

分析

用 Trie 树统计每个词出现的次数，时间复杂度是 O(n*l)（l 表示单词的平均长度），然后是找出出现最频繁的前 10 个词。

2. 寻找热门查询

问题

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为 1-255 字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是 1 千万，但是如果去除重复和，不超过 3 百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的 10 个查询串，要求使用的内存不能超过 1G。

分析

3 百万字符占用的最大内存为 300 0000 * 255 B = 0.75 GB。

利用 Trie 树，观察关键字域存该查询串出现的次数，若没有出现则为 0。最后用 10 个元素的最小堆来对出现频率进行排序。