问题标签 [trie]

因此，如果我必须在哈希表或前缀树之间进行选择，那么导致我选择其中一个的区别因素是什么。从我自己幼稚的角度来看，似乎使用 trie 有一些额外的开销，因为它没有存储为数组，但就运行时间而言（假设最长的键是最长的英文单词）它本质上可以是 O (1) (关于上限)。也许最长的英文单词是50个字符？

一旦获得索引，哈希表就会立即查找。然而，散列密钥以获取索引似乎可以轻松完成近 50 个步骤。

有人可以为我提供一个更有经验的观点吗？谢谢！

我必须实现一个自制的 Trie 并且我被困在 Iterator 部分。我似乎无法弄清楚 trie 的增量方法。

我希望有人能帮我把事情弄清楚。

这是迭代器的代码：

这是我的特里：

我有一个前缀特里。在关系数据库中表示这种结构的推荐模式是什么？我需要子字符串匹配以保持效率。

我有一个 Java 程序，它存储了大量从字符串到各种对象的映射。

现在，我的选择要么依赖散列（通过 HashMap），要么依赖二分搜索（通过 TreeMap）。我想知道在流行的高质量收藏库中是否有一个高效且标准的基于 trie 的地图实现？

我过去写过自己的，但如果可以的话，我宁愿使用一些标准的东西。

快速澄清：虽然我的问题很笼统，但在当前项目中，我正在处理大量由完全限定的类名或方法签名索引的数据。因此，有许多共享前缀。

我在大学里最喜欢的数据结构之一是Trie。如果前缀是共享的，它是一个很好的数据结构，用于保存大量字符串。查找也很好，因为无论集合中有多少字符串，它们都是在字符串的 O(|length|) 处完成的。

相比之下，平衡树的设置项目数量为 O(log N)，加上您为比较支付的任何费用。哈希表将涉及哈希计算、比较等。

因此，令我惊讶的是，大多数语言的标准库中都没有 Trie 实现。

我能想出的唯一原因是内存访问成本可能使其过于昂贵。如果进行树查找，而不是调查 O(log N) 个位置，而不是执行 O(|length|) 个不同的位置，这会带来所有后果。如果字符串很长，这最终可能会太多。

所以我想知道：我刚才描述的问题有多少？当您需要存储大量字符串或字符串时，您会怎么做？

我正在为 VB.NET 中的预测文本输入实现一个 trie - 就 trie 的使用而言，基本上是自动完成。我已经使我的 trie 成为基于通用字典类的递归数据结构。

基本上是：

单词中的每个字母（全部大写）都用作新 WordTrie 的键。叶子上的空字符表示单词的终止。要找到以前缀开头的单词，我会一直走到我的前缀，然后收集所有子单词。

我的问题基本上是关于 trie 本身的实现。我正在使用字典哈希函数来分支我的树。我可以使用一个列表并对列表进行线性搜索，或者做其他事情。这里有什么流畅的动作？这是进行分支的合理方法吗？

谢谢。

更新：

只是为了澄清，我基本上是在问字典分支方法是否明显不如其他替代方法。我使用此数据结构的应用程序仅使用大写字母，因此数组方法可能是最好的。我可能会在未来更复杂的预输入情况（更多字符）中使用相同的数据结构。在这种情况下，听起来字典是正确的方法——直到我需要使用更复杂的东西。

我有一个Trie和几个修改它的函数。

现在，为了调试和/或测试我的功能，我需要打印出尝试。

我递归地尝试过，但我无法获得第一级，而不是第二级......

有什么好方法吗？

我不知道这是否是询问算法的地方。但是让我们看看我是否得到任何答案...... :)

如果有什么不清楚的地方，我很乐意澄清事情。

我刚刚在 python 中实现了一个Trie 。然而，有一点似乎比它应该的更复杂（作为一个喜欢简单的人）。也许有人遇到过类似的问题？

我的目标是通过将子树的最大公共前缀存储在其根中来最小化节点数量。例如，如果我们有单词stackoverflow、stackbase和stackbased，那么树看起来像这样：

请注意，仍然可以认为边缘具有一个字符（子节点的第一个字符）。

Find -query 很容易实现。 插入并不难，但比我想要的要复杂一些.. :(

我的想法是一个接一个地插入键（从一个空的 trie 开始），首先搜索要插入的键 k（Find (k)），然后在本地重新排列/拆分节点查找过程停止。结果有4种情况：（设k是我们要插入的键，k'是节点的键，搜索结束的地方）

1. k 与 k' 相同
2. k 是 k' 的“正确”前缀
3. k' 是 k 的“正确”前缀
4. k 和 k' 共享一些共同的前缀，但没有出现 (1)、(2) 或 (3) 的情况。

似乎每个案例都是独一无二的，因此意味着对 Trie 的不同修改。但是：真的那么复杂吗？我错过了什么吗？有更好的方法吗？

谢谢 ：）

我正在使用 jQuery 的自动完成功能实现类似自动完成功能的“Google Suggest”标签搜索。

我需要为 jQuery 提供一个 Web 服务，根据用户输入的内容给它一个建议列表。我看到了两种实现 Web 服务的方法：

1）只需将所有标签存储在数据库中，并使用用户输入作为前缀搜索数据库。这很简单，但我担心延迟。

2) 使用进程内尝试存储所有标签并搜索匹配结果。由于一切都在进行中，我希望这会有更低的延迟。但是有几个困难： - 初始化 trie on 进程启动的好方法是什么？假设我将标签数据存储在数据库中并在我第一次启动该过程时检索它们并将它们变成一个 trie。但我不确定如何。我正在使用 Python/Django。-当用户创建新标签时，我需要将新标签插入到 trie 中。但是假设我有 5 个 Django 进程，因此有 5 次尝试，我如何告诉其他 4 次尝试他们也需要插入一个新标签？-如何确保 trie 是线程安全的，因为我的 Django 进程将被线程化（我正在使用 mod_wsgi）。或者我不必担心因为 Python 的线程安全？吉尔？- 有什么方法可以将标签的使用频率存储在 trie 中？我如何判断标签的字符串何时结束以及频率何时开始 - 例如。如果我将apple213存储到trie中，它是频率为213的“apple”还是频率为13的“apple2”？

对上述问题的任何帮助或对不同方法的任何建议将不胜感激。

在 C/C++ 中是否有任何速度和缓存高效的 trie 实现？我知道 trie 是什么，但我不想重新发明轮子，自己实现它。