Trie节省空间,但如何？
Raj*_*pta 13 c++ java collections trie guava
我很困惑Trie实现如何以最紧凑的形式节省空间并存储数据!
如果你看下面的树.在任何节点上存储字符时,还需要存储对该字符的引用,因此对于存储其引用所需的字符串的每个字符.好的,我们在公共角色到达时节省了一些空间,但是在存储对该角色节点的引用时我们失去了更多的空间.
那么维护这棵树本身是不是有很多结构开销呢？相反,如果使用TreeMap代替这个,让我们说实现一个字典,这可以节省更多的空间,因为字符串将被保存在一个片段中因此没有浪费存储引用的空间,不是吗？
Dav*_* Hu 14
为了在使用trie时节省空间,可以使用压缩的trie(也称为patricia trie或radix tree),其中一个节点可以表示多个字符:
在计算机科学中,基数树(也称为patricia trie或radix trie)是一种空间优化的trie数据结构,其中每个只有一个子节点的节点与其子节点合并.结果是每个内部节点至少有两个子节点.与常规尝试不同,边缘可以用字符序列和单个字符标记.这使得它们对于小集合(特别是如果字符串很长)和共享长前缀的字符串集更有效.
基数树的示例:
注意,trie通常用作在一组字符串上进行前缀匹配的有效数据结构.trie也可以用作关联数组(如哈希表),其中键是字符串.
- @Marcos在Guava中没有trie实现,虽然有一个长期存在的问题需要添加一个,所以最终可能会发生. (3认同)
当您有很多单词要由树表示时,节省空间.因为许多单词在树中共享相同的路径; 你的话越多,你就会节省更多的空间.
但是如果你想节省空间,有一个更好的数据结构.Trie不像有向非循环字图(DAWG)那样节省空间,因为它在整个结构中共享公共节点,而trie不共享节点.在维基条目解释了这么多的细节,让我们看看它.
以下是Trie和DAWG之间的差异(图形):
存储在Trie(左)和DAWG(右)中的字符串"tap","tap","top"和"tops",EOW代表词尾.
左侧的树是Trie,右侧的树是DAWG.比较它们,看看DAWG如何有效地节省空间.Trie具有表示相同字母/子字的重复节点,而DAWG对于每个字母/子字只有一个节点.
它不是关于内存中的廉价空间,而是关于文件或通信链路中的宝贵空间.使用构建该trie的算法,我们可以以三位,左右右方式发送"十".相比24位"十"将占用未压缩,这大大节省了宝贵的磁盘空间或传输带宽.
您可能会推断，在每个字节都得到有效分配的理想机器上，它可以节省空间。然而，真实的机器分配对齐的内存块（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
- 我更喜欢一种更乐观的方法，即始终选择性能最佳的解决方案，即使需要更长的时间。只要您进行基准测试并知道在什么情况下使用什么方法才能获得最佳结果，您总是会知道瓶颈在哪里，并习惯性地避免它们。每次我看到有人使用 ArrayList.add(0, item) 时，我都会留下评论来查看 LinkedList。如果你不知道你的工具在幕后做什么，你就会犯错误，导致应用程序运行缓慢。支付服务器费用是一回事，但潜在用户的第一印象是无价的。 (2认同)