Trie 数据结构：被忽视的宝石

从我们作为程序员的第一天开始，我们就都在处理数据结构：数组、链表、树、集合、堆栈和队列是我们的日常伙伴，经验丰富的程序员知道何时以及为何使用它们。 在本文中，我们将看到一个经常被忽视的数据结构trie是如何在具有特定功能的应用程序领域（如文字游戏）中真正发挥作用的。

文字游戏作为特里的例子

首先，让我们考虑一个简单的单词拼图：在 4x4 字母板上找到所有有效单词，水平、垂直或对角连接相邻的字母。 例如，在下面的板上，我们看到字母“W”、“A”、“I”和“T”连接起来形成单词“WAIT”。

寻找所有有效词的简单解决方案是从左上角开始探索棋盘，然后将深度优先移动到更长的序列，再次从第一行的第二个字母开始，依此类推。 在 4x4 棋盘中，允许垂直、水平和对角线移动，有 12029640 个序列，长度从 1 到 16 个字符不等。

现在，我们的目标是找到实现这个有效词检查器的最佳数据结构，即我们的词汇表。 需要记住的几点：

• 从逻辑的角度来看，我们只需要每个单词的一个副本，即我们的词汇表是一个集合。
• 对于任何给定的单词，我们需要回答以下问题：
  • 当前字符序列是否包含有效单词？
  • 有没有以这个序列开头的更长的单词？ 如果没有，我们可以放弃我们的深度优先探索，因为更深入不会产生任何有效的单词。

为了说明第二点，请考虑以下棋盘：探索后续动作没有意义，因为字典中没有以“ASF”开头的单词。

我们希望我们的数据结构能够尽快回答这些问题。 ~O(1) 访问时间（用于检查序列）将是理想的！

我们可以像这样定义 Vocabulary 接口（参见此处获取 GitHub 存储库）：

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Trie 数据结构与替代方案

实现contains()方法需要一个支持数据结构，它可以让您有效地查找元素，而isPrefix()方法需要我们找到“下一个更大的元素”，即我们需要以某种方式保持词汇表的排序。

我们可以很容易地从候选列表中排除基于散列的集合：虽然这样的结构可以让我们对contains()进行恒定时间检查，但它在isPrefix()上的表现会很差，在最坏的情况下需要我们扫描整个放。

出于完全相反的原因，我们也可以排除排序的链表，因为它们需要至少扫描列表直到大于或等于搜索词或前缀的第一个元素。

两个有效的选项是使用排序的数组支持列表或二叉树。
在排序后的数组支持列表上，我们可以使用二进制搜索来查找当前序列（如果存在）或下一个更大的元素，成本为O(log2(n)) ，其中n是字典中的单词数。

我们可以使用标准的java.util.ArrayList和java.util.Collections.binarySeach实现一个数组支持的词汇表，它总是保持这样的顺序：

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

如果我们决定使用二叉树，实现可能会更短、更优雅（同样，这里是代码的链接）：

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

在这两种情况下，我们可以预期每种访问方法（ contains()和isPrefix() ）的O(log n)性能。 至于空间要求，数组支持的实现和树支持的实现都需要O(n+M)其中 n 是字典中的单词数，M 是字典的字节大小，即长度的总和字典中的字符串。

Trie 应用程序：何时以及为何使用 Trie

对数性能和线性内存还不错。 但是我们的应用程序领域还有一些特征可以使我们获得更好的性能：

• 我们可以放心地假设所有单词都是小写的。
• 我们只接受 az 字母——无标点符号、连字符、重音符号等。
• 该词典包含许多屈折形式：复数、共轭动词、复合词（例如，house –> housekeeper）。 因此，许多词共享同一个词干。
• 单词的长度是有限的。 例如，如果我们在 4x4 板上工作，所有超过 16 个字符的单词都可以被丢弃。

这就是 trie（发音为“try”）的用武之地。但是 trie 到底是什么？ 尝试是被忽视的数据结构，在书本中可以找到，但在标准库中很少见。

对于动机，让我们首先考虑计算机科学的典型代表：二叉树。 现在，当我们分析二叉树的性能并说操作x是O(log(n))时，我们一直在谈论 log base 2。但是如果我们使用三叉树而不是二叉树呢？每个节点都有三个孩子（或者，三个的扇出）。 然后，我们将讨论以 3 为基数的日志。（这是一种性能改进，尽管只是一个常数因素。）本质上，我们的树会变得更宽但更短，并且我们可以执行更少的查找，因为我们不需要下降太多很深。

更进一步，如果我们有一棵树的扇出等于我们数据类型的可能值的数量呢？

这就是 trie 背后的动机。 正如您可能已经猜到的那样，trie 确实是一棵树，可以说是一棵 trie 树！

但是，与用于排序字符串的大多数二叉树相反，那些将整个单词存储在其节点中的二叉树，trie 的每个节点都包含一个字符（甚至不是那个，我们很快就会看到）和最大扇出等于字母表的长度。 在我们的例子中，字母的长度是 26； 因此，trie 的节点的最大扇出为 26。而且，虽然平衡二叉树的深度为log2(n) ，但 trie 的最大深度等于单词的最大长度！ （同样，更宽但更短。）

在一个 trie 中，具有相同词干（前缀）的单词共享对应于词干的内存区域。

为了可视化差异，让我们考虑一个由五个单词组成的小字典。 假设希腊字母表示指针，注意在 trie 中，红色字符表示持有有效单词的节点。

Java Trie 实现

正如我们所知，在树中，指向子元素的指针通常使用左右变量来实现，因为最大扇出固定为两个。

在索引 26 个字母的字母表的 trie 中，每个节点有 26 个可能的子节点，因此有 26 个可能的指针。 因此，每个节点都有一个包含 26 个（指向）子树的数组，其中每个值可以为空（如果没有这样的子节点）或另一个节点。

那么，我们如何在 trie 中查找一个单词呢？ 这是给定String s的方法，它将识别对应于单词最后一个字母的节点（如果它存在于树中）：

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

LOWERCASE.getIndex(s.charAt(i))方法只返回字母表中第 i 个字符的位置。 在返回的节点上，一个布尔属性node表示该节点对应于一个单词的最后一个字母，即上例中标记为红色的字母。 由于每个节点都有一个子节点数量的计数器，如果这个计数器是正数，那么字典中有更长的单词以当前字符串为前缀。 注意：节点实际上并不需要保留对它对应的字符的引用，因为它隐含在它在 trie 中的位置中。

分析性能

使 trie 结构在这些情况下真正表现良好的原因是查找单词或前缀的成本是固定的，并且仅取决于单词中的字符数，而不取决于词汇表的大小。

在我们的特定领域中，由于我们有最多 16 个字符的字符串，因此需要 16 个步骤才能找到词汇表中的单词，而任何否定答案，即单词或前缀不在 trie 中，都可以获得最多16个步骤！ 考虑到我们之前在计算基于数组的排序列表和隐藏在字符串比较中的树的运行时间复杂度时忽略了字符串的长度，我们也可以在这里忽略它并安全地声明查找已完成在O(1)时间内。

考虑到空间要求（并记住我们已经用M表示字典的字节大小），如果没有两个字符串共享前缀，则在最坏的情况下，trie 可能有M个节点。 但是由于我们观察到字典中存在高度冗余，因此需要进行大量压缩。 示例代码中使用的英文字典为 935,017 字节，需要 250,264 个节点，压缩率约为 73%。

然而，尽管如此，即使是压缩的 trie 通常也需要比树或数组更多的内存。 这是因为，对于每个节点，至少需要 26 x sizeof(pointer)字节，加上对象和其他属性的一些开销。 在 64 位机器上，每个节点需要超过 200 个字节，而字符串字符需要一个字节，如果我们考虑 UTF 字符串，则需要两个字节。

尝试和性能测试

那么，性能呢？ 词汇实现在两种不同的情况下进行了测试：检查 20,000,000 个随机字符串并在从同一单词列表随机生成的 15,000 个板上查找所有单词。

分析了四种数据结构：一个数组支持的排序列表、一个二叉树、上面描述的 trie，以及一个使用与字符本身的字母索引相对应的字节数组的 trie（一个较小且易于实现的性能优化）。 以下是结果，以毫秒为单位：

解决棋盘的平均移动数为 2,188。 对于每一步，都会进行一次单词查找和前缀查找，即为了检查所有棋盘，执行了超过 32M 单词查找和 32M 前缀查找。 注意：这些可以一步完成，为了在说明中清晰起见，我将它们分开。 一步将它们压实可以将解决板的时间减少近一半，并且可能会更倾向于尝试。

如上所示，即使在使用字符串时，使用 trie 的单词查找性能也更好，使用字母索引时甚至更快，后者的执行速度是标准二叉树的两倍多。 解决板的差异更加明显，快速 trie-alphabet-index 解决方案的速度是列表和树的四倍以上。

包起来

trie 是一种非常专业的数据结构，它比树和列表需要更多的内存。 但是，当应用特定的域特征时，例如字符串第一部分中有限的字母和高冗余，它可以非常有效地解决性能优化问题。

参考

可以在 Robert Sedgewick 的著作“算法，第 4 版”的第 5 章中找到对尝试和字母表的广泛解释。 普林斯顿大学的配套网站有实现 Alphabet 和 TrieST 的代码，比我的例子更广泛。

也可以在 Wikipedia 上找到各种语言的 trie 和实现的描述，您也可以查看这个波士顿大学 trie 资源。