srcmini本文概述
从成为程序员的一开始, 我们就开始处理数据结构：数组, 链接列表, 树, 集合, 堆栈和队列是我们的日常伴侣, 并且经验丰富的程序员知道何时以及为什么使用它们。在本文中, 我们将了解经常被忽略的数据结构trie在具有特定功能(例如文字游戏)的应用程序领域中如何真正发挥作用。
文字游戏作为例子
首先, 让我们考虑一个简单的单词拼图：在4×4的字母板上找到所有有效的单词, 水平, 垂直或对角线连接相邻的字母。例如, 在下面的面板中, 我们看到字母” W”, ” A”, ” I”和” T”连接在一起形成单词” WAIT”。
查找所有有效词的幼稚解决方案是从左上角开始探索木板, 然后将深度优先的序列移至更长的序列, 再从第一行的第二个字母开始, 依次类推。在4×4电路板上, 允许垂直, 水平和对角线移动, 共有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是字典的字节大小, 即L的长度之和。字典中的字符串。
Trie应用程序：何时和为什么使用Tries
对数性能和线性记忆也不错。但是我们的应用程序域还有其他一些特征可以使我们获得更好的性能：
- 我们可以安全地假设所有单词都是小写。
- 我们仅接受a-z字母-不允许标点符号, 连字符, 重音符号等。
- 字典包含许多变体形式：复数形式, 共轭动词, 复合词(例如, house –> housekeeper)。因此, 许多单词共享同一词干。
- 单词的长度是有限的。例如, 如果我们在4×4板上工作, 则所有长度超过16个字符的单词都将被丢弃。
这就是trie(发音为” try”)出现的地方。但是trie到底是什么呢？尝试是被忽略的数据结构, 可以在书籍中找到, 但很少在标准库中找到。
为了获得动力, 让我们首先考虑计算机科学的后代：二叉树。现在, 当我们分析二叉树的性能并说操作x为O(log(n))时, 我们一直在谈论对数为2。但是, 如果我们使用三叉树代替二叉树, 那该怎么办？每个节点有3个子节点(或3个子节点)。然后, 我们将讨论基于3的对数。(这是性能的提高, 尽管只是一个恒定的因素。)从本质上讲, 我们的树将变宽但变短, 并且我们可以执行更少的查找, 因为我们不需要完全下降很深。
更进一步, 如果我们有一棵扇出的树等于数据类型的可能值的数量怎么办？
这是尝试的动机。正如你可能已经猜到的那样, Trie树确实是一棵树, 可以这么说！
但是, 与大多数用于对字符串进行排序的二叉树相反, 那些将整个单词存储在其节点中的二叉树与之相反, 一个Trie树的每个节点都拥有一个字符(甚至不会, 我们很快会看到)。最大扇出量等于字母的长度。在我们的例子中, 字母的长度是26；因此, Trie树的节点的最大扇出度为26。并且, 尽管平衡二叉树的深度为log2(n), 但Trie树的最大深度等于一个单词的最大长度！ (再次, 宽但短。)
在Trie里, 具有相同词干(前缀)的单词共享与词干对应的存储区域。
为了显示差异, 让我们考虑一个由五个词组成的小词典。假定希腊字母表示指针, 并注意在trie中, 红色字符表示持有有效单词的节点。
Java Trie实现
众所周知, 在树中, 指向子元素的指针通常使用left和right变量实现, 因为最大扇出固定为2。
在索引由26个字母组成的字母表的Trie中, 每个节点具有26个可能的子代, 因此有26个可能的指针。因此, 每个节点都具有26个(指向)子树的数组, 其中每个值可以为null(如果没有这样的子级)或另一个节点。
那么, 我们如何在Trie查询一个单词呢？如果给定String, 则以下方法将识别与单词的最后一个字母相对应的节点(如果它存在于树中)：
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个字符在字母表中的位置。在返回的节点上, 布尔属性节点指示该节点对应于单词的最后一个字母, 即在上一个示例中以红色标记的字母。由于每个节点都保留有一个子代数计数器, 因此如果该计数器为正数, 则字典中将有更长的单词, 这些单词具有当前字符串作为前缀。注意：该节点实际上不需要保留对其所对应字符的引用, 因为该节点隐含在其在Trie中的位置。
分析效果
在这些情况下, 使trie结构真正发挥出色的原因在于, 查找单词或前缀的成本是固定的, 并且仅取决于单词中字符的数量, 而不取决于词汇量。
在我们的特定领域中, 由于我们的字符串最多包含16个字符, 因此找到词汇表中的单词仅需16个步骤, 而任何否定答案(即单词或前缀不在trie中)都可以获取最多也要16个步骤！考虑到我们之前在计算数组支持的排序列表和树的运行时间复杂度时都忽略了字符串的长度(隐藏在字符串比较中), 我们也可以在此处忽略它, 并安全地指出查找已完成在O(1)时间内。
考虑到空间要求(并记住我们用M表示了字典的字节大小), 如果没有两个字符串共享前缀, 则在最坏的情况下, Trie树可能有M个节点。但是, 由于我们已经观察到字典中存在很高的冗余度, 因此需要进行大量压缩。示例代码中使用的英语词典为935, 017字节, 需要250, 264个节点, 压缩率约为73％。
但是, 尽管如此, 即使压缩的Trie树通常也比树或数组需要更多的内存。这是因为, 对于每个节点, 至少需要26 x sizeof(pointer)字节, 再加上对象和其他属性的一些开销。在64位计算机上, 每个节点需要200多个字节, 而字符串字符则需要一个字节, 如果考虑使用UTF字符串, 则需要两个字节。
相关：Java开发人员最常犯的10个错误：Java初学者的教程
尝试和性能测试
那么, 性能呢？在两种不同的情况下测试了词汇的实现方式：检查20, 000, 000个随机字符串, 并在从同一单词列表中随机生成的15, 000个木板中找到所有单词。
分析了四个数据结构：一个数组支持的排序列表, 一个二叉树, 上述的trie, 以及一个使用字节数组的trie, 这些字节数组对应于字符本身的字母索引(较小且易于实现的性能优化)。这是结果, 以毫秒为单位：
解决董事会所采取的平均动作数量为2, 188。对于每一步, 都执行单词查找和前缀查找, 即, 为了检查所有板, 执行了超过32M的单词查找和32M的前缀查找。注意：这些操作可以一步完成, 为了说明清楚, 我将它们分开。一步压缩它们可以将解决电路板的时间减少近一半, 并且可能会更喜欢Trie。
从上面可以看出, 即使在使用字符串时, 单词查找在trie上的性能也更好, 而在使用字母索引时, 单词的查找甚至更快, 后者的索引速度是标准二叉树的两倍以上。解决木板问题的区别更加明显, 快速的Trie-字母索引解决方案的速度是列表和树的四倍以上。
总结
Trie树是一种非常专业的数据结构, 它需要比树和列表更多的内存。但是, 当应用特定的域特征时, 例如有限的字母和字符串的第一部分中的高冗余度, 它在解决性能优化方面非常有效。
参考文献
罗伯特·塞奇威克(Robert Sedgewick)的书”算法, 第4版”的第5章提供了有关尝试和字母的详尽解释。普林斯顿大学的同伴网站具有用于实现Alphabet和TrieST的代码, 该代码比我的示例更广泛。
关于trie的描述和各种语言的实现也可以在Wikipedia上找到, 你也可以查看波士顿大学的trie资源。
相关：大海捞针：一个漂亮的大规模文本搜索算法教程
评论前必须登录！
注册