logo标签列表

Trie如何节省空间？

javac++collectionsguavatrie
15

我对Trie数据结构是如何节省空间并以最紧凑的形式存储数据感到困惑！

如果你看下面的树。当你在任何节点存储一个字符时，你也需要存储对该字符的引用，因此对于字符串的每个字符，你需要存储它的引用。 当一个常见字符出现时，我们确实可以节省一些空间，但是在存储对该字符节点的引用时，我们失去了更多的空间。

那么难道不需要有很多结构性的开销来维护这个树本身吗？相反，如果使用TreeMap来实现字典，比如说，这将可以节省更多的空间，因为字符串将保持完整，因此不会浪费存储引用的空间，是吗？

输入图片描述

如果一个节点占用16个字节，但在超过16个字符串（Java中为8个）中被重复使用，则可以节省空间。然后问题就是你是否节省了比浪费更多的空间。假设你的示例中蓝色数字是重复计数，与简单的字符串数组相比，节省的空间确实比浪费的空间要大。然而，在这种情况下，最好存储带有重复计数的完整字符串。 - han
5个回答
16
为了在使用字典树时节省空间，可以使用压缩字典树（也称为 Patricia 字典树或基数树），其中一个节点可以表示多个字符：
在计算机科学中，基数树（也称为 Patricia 字典树或基数 Trie）是一种经过空间优化的字典树数据结构，只有一个子节点的每个节点都会与其子节点合并。结果是每个内部节点至少有两个子节点。与常规字典树（Trie）不同，边缘可以用字符序列以及单个字符标记。这使得它们对于小型集合（特别是如果字符串很长）和共享长前缀的字符串集合更加高效。
基数树的示例：

radix tree or patricia trie

请注意，Trie通常用作一组字符串的前缀匹配的高效数据结构。Trie也可以用作关联数组（类似于哈希表），其中键是字符串。

我看了一下 Patricia Trie 的实现，但它是否是像 Guava 和 Apache Commons 这样的流行库的一部分呢？根据他们的说法，我无法在 Guava/ Apache Commons 集合中找到它的实现。 - Rajat Gupta
3
@Marcos 在Guava中没有trie实现，不过已经有一个长期的问题在进行添加该功能，所以可能最终会实现。 - ColinD
@David数字表示数值吗？ - Pacerier
@DavidHu：我也在这里解决Patricia Trie问题here。目前我卡住了。如果你能帮我，那就太好了。谢谢。 - user2467545
7

如果您需要用树来表示大量单词，那么使用树可以节省空间。因为许多单词在树中共享相同的路径；您拥有的单词越多，您将节省更多的空间。

但是，如果您想节省空间，那么有一种更好的数据结构。与Trie不同，有向无环图(DAWG)通过整个结构共享公共节点来节省空间。 维基百科条目详细解释了这一点，请查看。

以下是Trie和DAWG之间的差异（以图形方式）：

enter image description here

左边的树是Trie，右边的树是DAWG。比较它们并看看DAWG如何高效地节省空间。Trie有重复的节点代表相同的字母/子单词，而DAWG对于每个字母/子单词只有一个节点。EOW代表单词结尾。
这是我不明白的地方。对于我们保存的每个字符，我们都要付出指针的代价..那难道不是更糟糕吗？ - Pacerier
@Pacerier：指针需要支付多少次？只需支付一次，您就可以使用相同字符的重复次数。 - Nawaz
单独来看，我不明白dawg如何为“两个不同分支具有相同尾部的概率是多少？”这个问题节省空间。例如，“topsman”是一个单词，但显然“tapsman”不是；因此，对于典型的问题陈述（在内存中使用英语字典），您仍然需要两个尾巴，不是吗？ - Pacerier
5

这不仅仅是内存空间的问题，而是文件或通信链路上宝贵空间的问题。通过构建 trie 算法，我们可以用左-右-右三位二进制码发送 “ten”，相比未压缩前需要 24 位二进制码，这将节省大量宝贵的磁盘空间或传输带宽。

这真的是一个巨大的优势！ - Rajat Gupta
那么，仅针对内存结构且无需传输数据，但需要一种高效且占用空间少的解决方案来获取大约10,000个名称的电话名录搜索建议，使用Trie相比TreeMap是否更为推荐？ - Rajat Gupta
@David，关于“左-右-右”；这不是trie而是patricia吗？ - Pacerier
3
你可能会推断，在每个字节都被有效分配的理想机器上保存空间。然而，实际机器分配对齐的内存块（在Java中为8字节，在某些C++中为16字节），因此可能不会节省任何空间。
Java字符串和集合添加相对较高的开销，所以百分比差异可能非常小。
除非您的结构非常大，否则使用最简单、最标准、最易于维护的集合的内存成本远远低于时间价值。例如，您的时间很容易比您尝试节省的内存价值高1000倍或更多。
例如，假设您有10000个名称，使用trie可以每个名称节省16字节。（假设可以证明这一点而不需要花费更多时间）这相当于16 KB，在今天的价格下价值0.1美分。如果您的时间每小时为30美元，编写一行经过测试的代码的成本可能为1美元。
如果你需要再思考一瞬间才能节省16 KB，这对于PC来说不太值得。（移动设备是另一回事，但同样的论点适用于我的看法）
编辑：您已经激发了我添加一个更新 http://vanillajava.blogspot.com/2011/11/ever-decreasing-cost-of-main-memory.html。
Trie 会更快，更省空间。对于 15K 条目，它可以节省你 0.2 美分的内存和 CPU。如果你看到马路对面可能会有 0.2 美分，你会过去捡吗？如果这只需要花费你大约一秒的时间，我才会这样做。考虑到 TreeMap 是一个内置、经过充分测试、文档完善且能被任何需要支持你代码的人所理解的工具，除非你使用的是许多内存受限的设备，否则它将在时间上为你节省远远超过在内存方面的成本。 - Peter Lawrey
1
如果你正在编写一个被部署到数千或数百万消费者的库，那么这0.2美分就有了多个因素，当它被部署到按使用量计费的服务器时，这0.2美分又有了另一个倍数。"性能不重要"不是解决方案，而是一种意识形态。 - Ajax
如果在一百万台机器上节省0.2美分，总共可以节省2000美元。这值得花费几天甚至一周的时间。如果只有10万台机器，你只需要几个小时或者一天的时间。如果只有1万台机器，你只需要几分钟的时间。如果只有1000台机器或更少，你可能浪费时间去担心这个问题。规模确实很重要，大多数项目没有部署到足够多的机器上，所以担心资源的小量是不明智的。 - Peter Lawrey
2
我更倾向于一种更乐观的方法，即始终选择最高效的解决方案，即使需要花费更长的时间。只要你进行基准测试并知道在什么情况下使用哪种方法以获得最佳结果，你就会始终知道瓶颈在哪里，并养成避免它们的习惯。每当我看到有人使用ArrayList.add(0, item)时，我都会留下评论，建议使用LinkedList。如果你不知道你的工具在干什么，你会犯错误，导致应用程序变得缓慢。支付服务器成本是一回事，但潜在用户的第一印象是无价的。 - Ajax
@PeterLawrey，回答正确但问题不对。 - Pacerier
@Pacerier 可能是这样，尽管我在顶级答案之后回答，但 OP 认为这是正确的答案。有时候我回答的是 OP 可能想要问的问题，而不是字面上的问题。 - Peter Lawrey
1

Guava 可能确实在每个级别存储键，但要意识到的是，实际上不需要存储键，因为节点的路径完全定义了该节点的键。每个节点实际上只需要存储一个布尔值，指示这是否是叶节点。

Tries（字典树），像任何其他结构一样，擅长存储某些类型的数据。具体来说，Tries 最擅长存储共享公共前缀的字符串。例如，考虑存储完整路径目录列表。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接