问题标签 [patricia-trie]

我目前正在实现一个基数树/帕特里夏树（无论你想怎么称呼它）。我想用它在一个严重不足的硬件上的字典中进行前缀搜索。它应该或多或少像自动完成一样工作，即显示输入前缀匹配的单词列表。

我的实现基于这篇文章，但其中的代码不包括前缀搜索，尽管作者说：

[...]假设您要枚举所有具有公共前缀“AB”的键的节点。您可以从该根开始执行深度优先搜索，只要遇到后边缘就停止。

但我不明白这应该如何工作。例如，如果我从这些词构建一个基数树：

疾病
想象
想象
想象
模仿
立即
立即
巨大
的

对于前缀“i”和“in”，我将得到完全相同的“最佳匹配”，因此我似乎很难通过从最佳匹配中遍历树来收集所有匹配的单词。

此外，Java 中有一个基数树实现，它在RadixTreeImpl.java中实现了前缀搜索。该代码显式检查所有节点（从某个节点开始）是否有前缀匹配 - 它实际上比较字节。

谁能指出我在基数树上实现前缀搜索的详细描述？Java实现中使用的算法是唯一的方法吗？

我正在实施 Patricia 尝试进行 IP 前缀查找，我可以让代码为完整的键匹配工作，但遇到前缀搜索问题，当键是其他键的前缀时，例如：

在上述情况下，任何人都可以帮助我使用前缀搜索算法我应该将它们视为单独长度的键（即/24 和 16）吗？

我目前正在尝试为 dna 序列数据搜索系统实现 Index Fabric：

索引结构算法

我可以实现普通的 patricia trie，但我仍然不明白如何添加图层。我也尝试了谷歌，但也找不到关于向 patricia trie 添加层的足够信息。在上面提到的论文中，他们直接使用了分层特里树，这对我来说似乎是巫术（开个玩笑，最后一部分）。有没有人有实现 Index Fabric 架构的经验，如果有，你们能和我分享一下你的经验吗？

提前
致谢

我正在尝试使用 , 和 方法实现 Patricia Trie addWord()，isWord()并将isPrefix()其作为一种存储大型单词字典以便快速检索（包括前缀搜索）的方法。我已经阅读了这些概念，但它们只是没有阐明实现。我想知道（在 Java 或 Python 代码中）如何实现 Trie，尤其是节点（或者我应该递归地实现它）。我看到一个人用一组 26 个子节点设置为 null/None 来实现它。是否有更好的策略（例如将字母视为位）以及您将如何实施？

四处寻找尝试的 python 实现，以便我能理解它们是什么以及它们是如何工作的，我遇到了 Justin Peel 的patricia trie，发现它非常有启发性：对于像我这样新的人来说，它很简单，可以使用它并且从中学习。

但是，有些事情我认为我不明白：

因此使用贾斯汀的类 patricia() ：

我得到一个看起来像这样的字典：

addWord() 和 isWord() 按预期工作，但 isPrefix() 显示以下令我困惑的行为：

好，正如预期的那样；进而

也很好，但是：

此外：

这里有什么我不明白的？

我正在考虑编写一个 Android 应用程序，该应用程序具有大约 2000 个经度和纬度的数据库，这些数据库实际上是硬编码的。

我假设一旦安装了我的应用程序，我可以将这些信息放入 SQLite 数据库，但是在下载应用程序时我应该如何分发这些信息？

我想到的一个选择是某种 Patricia Trie 以最小化数据的大小（这些点将位于多个集群中，而不是均匀分布），但我不确定这样的集合是否会在有要存储的两个关联数字，可能还有一些其他信息，例如地名。

有没有人有任何想法、意见或建议？

富有的

最近我一直在研究 Patricia 的尝试，并使用了一个非常好的C++ 实现，它可以用作 STL 排序关联容器。Patricia 尝试与普通二叉树不同，因为叶节点具有指向内部节点的反向指针。尽管如此，如果您只通过叶节点反向指针访问内部节点，则可以通过按字母顺序遍历 Patricia trie。

这让我想到了一个问题：是否可以使用 Patricia trie实现 STLlower_bound和函数？upper_bound我正在使用的实现确实实现了这些功能，但它们没有按预期工作。

例如：

当我希望它输出 HCDA 时，这会输出 BLQ。（std::set例如，这里肯定会输出 HCDA。）

我给制作这个库的开发人员发了电子邮件，但从未得到回复。无论如何，我觉得我对 Patricia 如何尝试工作有很好的理解，而且我无法弄清楚像 lower_bound 这样的东西是如何可能的。问题在于，lower_bound 似乎依赖于按字典顺序比较两个字符串的能力。由于树中不存在“GG”，我们需要找出哪个元素 >= 到 GG。但是 Radix/Patricia 尝试不使用字典比较来从一个节点移动到另一个节点；而是每个节点存储一个位索引，用于对搜索键执行位比较。位比较的结果告诉您是向左还是向右移动。这使得在树中找到特定前缀变得容易。但是如果树中不存在前缀，

我正在使用的 C++ 实现似乎没有正确实现 lower_bound 的事实证实了我的怀疑，即它可能是不可能的。尽管如此，您可以按字母顺序遍历树的事实让我认为可能有一种方法可以做到这一点。

有没有人有这方面的经验，或者知道是否可以使用 Patricia Trie 实现 lower_bound 功能？

I. 刚刚实现了一种按位 trie（基于 nedtries），但是我的代码做了很多内存分配（对于每个节点）。与我的实现相反，nedtries 声称是快速的，除此之外，因为它们的内存分配数量很少（如果有的话）。作者声称他的实现是“就地”的，但在这种情况下它的真正含义是什么？nedtries 是如何实现如此少量的动态内存分配的呢？

Ps：我知道资源是可用的，但是代码很难理解，我不知道它是如何工作的

我有大约 10,000 个单词用作大约 500,000 个文档的一组反向索引。两者都是标准化的，因此索引是整数（单词 id）到一组整数（包含单词的文档的 id）的映射。

我的原型使用 Python 的集合作为明显的数据类型。

当我搜索文档时，我会找到 N 个搜索词的列表及其对应的 N 个集合。我想返回这 N 个集合的交集中的文档集。

Python 的“相交”方法是作为成对归约实现的。我认为我可以通过并行搜索排序集做得更好，只要库提供了一种快速获取i之后的下一个条目的方法。

我一直在寻找类似的东西一段时间。几年前，我编写了PyJudy，但我不再维护它，而且我知道需要做多少工作才能让它再次适应它的阶段。我宁愿使用别人的经过良好测试的代码，我想要一个支持快速序列化/反序列化的代码。

我找不到任何 Python 绑定，或者至少找不到任何 Python 绑定。有avltree 可以满足我的要求，但由于即使是成对的集合合并也比我想要的要长，我怀疑我想在 C/C++ 中完成所有操作。

你知道任何作为 Python 的 C/C++ 扩展编写的 radix/patricia/​​critbit 树库吗？

如果做不到这一点，我应该包装的最合适的库是什么？Judy Array网站已经 6年没有更新了，2007 年 5 月发布了 1.0.5。（虽然它确实构建得很干净，所以它可能只是工作。）

（编辑：为了澄清我从 API 中寻找的内容，我想要类似的东西：

我正在寻找实现 GET_NEXT() 以返回在给定条目之后发生的下一个条目的东西。这对应于Judy1N和其他 Judy 数组的类似条目。

该算法动态地适应数据应该优先支持低命中的集合。对于我使用的数据类型，性能提高了 5-10%。））

我已经部分实现了 Patricia Trie，它仍然不完整，因为它缺少用于从 Trie 中删除节点的删除/删除功能，我发现这篇描述结构的文章，它带有 C++ 中的实现，有一个删除/delete 函数，但我无法弄清楚实现背后的想法是什么。

如何从 Trie 中删除节点并使 Trie 处于正确状态？