问题标签 [trie]

我正在尝试在内存容量非常有限的手机上构建Trie 。

我认为最好将整个结构存储在磁盘上，并且只在必要时加载，因为我可以容忍一些磁盘读取。但是，经过几次尝试，这似乎是一件非常复杂的事情。

有哪些方法可以将 Trie 存储在磁盘上（即仅部分加载）并保持快速查找属性？
这甚至是一个好主意吗？

patricia trie 是众所周知的推荐数据结构，用于存储 IPv4 分配/分配和执行查找。

IPv6 地址也是如此吗？只是更深/更高的尝试来容纳额外的 96 位？trie 仍然是 patricia，还是不同的 radix trie？

嗨，我在 C 中实现了一个 trie ...但我在 insert_trie 函数中遇到了一个错误。

我无法弄清楚为什么根节点没有得到更新。请帮我解决一下这个。

由于 insert_trie 函数中的行 nodepointer = nodepointer->list 导致分段错误...为什么 ????

PS：这不是作业。但我正在尝试实施它。我只是找不到错误。

我最近听说了 nedtries 并决定尝试实现它们，但我对它们的搜索操作的复杂性感到困扰；我无法忍受他们为什么要这么快。

据我了解，他们的搜索操作的预期复杂度应该是 O(m/2)，其中 m 是密钥的大小（以位为单位）。如果将其与传统二叉树中搜索操作的复杂性进行比较，您会得到：log2(n) >= m/2

让我们的密钥长度为 32 位：log2(n) >= 16 <=> n >= 65536

所以 nedtries 应该比从 65536 个项目开始的二叉树更快。然而，作者声称它们总是比二叉树快，所以要么我对它们复杂性的假设是错误的，要么在搜索的每一步执行的计算在 nedtrie 中要快得多。

那么，它呢？

我们正在构建一个电话簿（联系人）应用程序，我刚刚在网上搜索了一下，发现了一个有用的数据结构可用于电话簿应用程序，即 TRIE。

您能否指导/建议链接，以便我们可以使用 Trie 数据结构实现电话簿应用程序。

我是 Java 数据结构和算法的新手，请将此视为我帮助我的请求。

我无法继续讨论是否真的可以使用 TRIE 数据结构来实现它？

我目前正在为 iOS 制作一个文字游戏，加载时会读取大约 30000 个单词的文本文件并将它们加载到前缀树中，以便在游戏过程中快速搜索。这很好用，但是加载和树构建过程会明显增加应用程序的启动时间几秒钟。目前我正在 iPhone 4 上进行测试，但我想在 3GS 早期型号上它会慢很多。

有没有办法在编译时而不是在应用程序打开时创建这个树？或者，不太理想的是，是否可以使用另一个程序预烘焙数据并将该文件添加到项目中，而不是在运行时进行？我该怎么做呢？

文献中有很多信息说搜索 trie 的时间是 O(N)，其中 N 是模式的长度。

但是，构建树也需要一些时间。对我来说，假设有 X 个单词，总共有 Y 个字符。

那么 O(Y) 就是时间（因为我们必须插入每个字符）。这个评估是否正确（我通常不正确）

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

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

我远程记得尝试不存储每个节点的全部数据，只存储父节点的后缀。

树确实存储了整个数据，但仅根据前缀进行组织。

因此尝试变得更小，例如可以很好地压缩字典。

这真的是唯一的区别吗？

从实际应用程序中，我记得尝试在范围查询中更快。甚至还有特殊的 solr/lucene trie 字段来加速范围查询。但怎么会这样呢？

尝试和树的实际区别是什么以及优缺点是什么？

我想通过制作一个非常通用的前缀树来学习新的 Scala 集合框架。不仅键和值必须是参数，而且每个节点中使用的映射的类型也必须是参数。所以我尝试了这个：

但这不会编译：

这让我很困惑。我可以从文档中看到 MapLike 有一个返回“This”的空。因此，由于 children 是 M[K,PrefixMap[M,K,V]] 类型，children.empty 也应该是该类型。

出了什么问题，可以修复吗？