问题标签 [radix-tree]

我想合并两个特里结构，但我能想到的最好的复杂性是

从其他 trie 获取值列表：O(n)，n 是 trie 中的节点数。从list intro target trie中插入所有值：n * O(m)，m是key的长度考虑到，最坏的情况下，key的大小是n，合并的复杂度不是O(n^2)吗？

有没有更好的方法呢？

我目前有一些从基数树数据结构执行最长前缀查找（LPM）的实现。此数据结构包含 IP 前缀（最大深度为 128 位的基数树），目前完全保存在内存中。数据是只读数据，永远不会被修改。

不幸的是，数据变大了，我不再能够在内存中维护它。我正在寻找一种可以保存在磁盘上并提供高效查找的高效数据结构。我打算在它上面使用一些缓存机制。

在我的应用程序中，我有大约 50Mb 的字符串，它们有很多共同的部分。我想通过使用 Radix Trie (Patricia Tree) 来减少内存消耗，例如。Apache 集合实现。

目标是保留对条目的引用并在需要时获取完整的字符串：

所以我希望它像下面这样存储在内存中：

当需要时，我应该能够获得完整的字符串（在 someObjectN 中）：

有2个问题：

1. 如何将字符串放入 trie 并获取TrieEntry实例？由于它实现了java.util.map，put 方法返回值：

   public V put(final K key, final V value)

2. 如何从TrieEntry实例中获取完整字符串？

在我的用例中，值（节点有效负载）是无用的，因为主要目标只是节省内存（没有任何有效负载）。

Apache 的 PatriciaTrie是否适合该用例？有什么想法吗？

我正在编写一个颤振应用程序。为此，我必须缓存一些地方并想要搜索名称。为此，我想使用基数特里树。我已经在 dart 下搜索了实现，但我没有发现任何有用的东西。

有人知道我在哪里可以找到实现吗？或者有没有人打扰过？

问候达戈伯特

我有兴趣使用基数树（或 Patricia trie）来存储strings -> values. 但是，我发现我有太多的字符串无法放入内存。

我发现Algolia 的一篇文章，介绍了他们如何通过搜索索引解决这个问题，他们谈到了我正在尝试做的事情：在构建每个分支时将基数树刷新到磁盘，并且只读回您需要的分支。

但是，他们没有提到他们是如何做到这一点的。我能想到的存储基数树的唯一方法是作为完整（序列化）对象或作为简单的键/值存储的哈希/数组。

例如，使用键/值存储

然后进行前缀扫描以提取MATCH smil*. 然而，这种方式失去了基数树节省空间的优势，而且它需要在负载时重建至少部分基数树。

我想存储多个百万长度的键（字符串）及其关联的对象。这样我必须非常频繁地插入数据结构（rbtree 或基数树），并且与插入相比必须搜索相当少的时间。任何建议将不胜感激。谢谢你。

我一直致力于将基数树（用于索引）序列化为 golang 中的文件。基数树节点存储 6 位咆哮位图（请参阅https://github.com/RoaringBitmap/roaring）。以下代码是我正在使用的代码，以及尝试将其加载回内存时得到的输出：

输出：

（我知道解码是空的，因为 gob 包不会因 EOF 错误而修改）

我注意到，当直接尝试使用字节时，只有 15 个字节存储在磁盘上（太少了）。尝试使用and的encoding/json包，我看到存储了 33 个字节，但它们加载为空（咆哮的位图消失了）：json.Marshall()json.Unmarshall()

我觉得这与我试图序列化 amap[string]interface{}而不是类似 a的事实有关map[string]int，但我仍然对 golang 相当陌生。

有关示例和我的测试，请参见https://repl.it/@danthegoodman/SelfishMoralCharactermapping#main.go 。

如何从 Patricia 中删除节点？帕特里夏我特别指的是基数二树，它的节点在树中向上指向以结束搜索。