问题标签 [trie]

也许我不够聪明，无法学习 Haskell，但我会给它最后一次机会。我一直坚持从树中删除条目的实现，像 Trie 这样的结构更具体（http://en.wikipedia.org/wiki/Trie）。

我正在寻找任何建议（不是解决方案！）如何实现这种纯功能。我对一种算法有一个想法。通过遍历等于单词每个字符的整个树“跳过”值来重新创建一棵新树，如果找不到下一个字符，则边缘条件返回原始树。但是当一个字符也属于另一个词时，就会出现问题。

数据看起来像：

通过 trie 映射，我的意思是关联数组，其中有效负载存储在trie而不是哈希表中。

当我使用哈希映射/表时，我使用的键通常是字符串。与某些基于 trie 的映射相比，哈希映射有哪些优势？我已经读过哈希映射更快 - 但在我看来，一致的哈希函数必须检查 (char) 数组的每个元素以获取最终哈希 - 遍历数组一次。在 trie 中，您同样必须只对数组进行一次迭代。

在我看来，这在编码小对象时会使用更多的内存（即使你只允许键中的小写字母字符，它是每个节点 26 个指针，并且每个键通常是多个节点），但从好的方面来说，你永远不必担心调整大小。为什么哈希图如此普遍，但我从未见过特里图？

我需要将数百万个带有公共前缀的字符串（它们不对应于文件系统路径）存储在内存中的类似结构的集合中，并查询集合以查看路径是否存在。

例如

我想尽可能有效地存储这些（它们将在内存中），考虑到所有涉及的字符串都会有许多公共前缀，Trie 是否是一个合理的候选者？

我正在寻找有关在 Java 中实现合适数据结构的建议。

嗨，我有一个项目，我需要通过尝试来实现字典......但现在我无法实现搜索方法......我的代码在这里

在这段代码中，我在 else 语句中有错误！！！！我想用其中一个孩子替换根，它的值类似于 key(temp) 的第一个字符，但我不能在“else statement”中这样做......以及为什么我无法访问该值孩子的？？

这是在采访中被问到的。

我认为可以通过构建所有有效单词的 trie 来完成答案，然后可以根据可能的有效路径提出建议，否则会被认为是不正确的。

假设如果用户键入 apfle，系统会检测到在 ap 之后可能的有效路径是 app，这将满足 apple 的要求。

还有比这更好的解决方案吗？也许是拼写检查器实现的。

想象一下下面的树：

我正在寻找一种方法来查询例如 F 是否是 A 的后代（注意：F 不需要是 A 的直接后代），在这种特殊情况下是正确的。只有有限数量的潜在父节点需要针对更大的潜在后代节点池进行测试。

在测试一个节点是否是潜在父池中某个节点的后代时，需要针对所有潜在父节点进行测试。

这是一个想出的：

• 将多路树转换为特里树，即为上述树中的每个节点分配以下前缀：

  /li>

• 然后，为每个可能的前缀大小保留一个位数组并添加要测试的父节点，即如果将 C 添加到潜在的父节点池中，请执行以下操作：

  /li>

• 当测试一个节点是否是潜在父节点的后代时，取其 trie 前缀，在第一个“前缀数组”（见上文）中查找第一个字符，如果存在，则在第二个“前缀”中查找第二个前缀字符数组”等等，即测试 F 导致：

  所以是的，F，是 C 的后代。

这个测试似乎是最坏情况 O(n)，其中 n = 最大前缀长度 = 最大树深度，所以它的最坏情况完全等于直接上树并比较节点的明显方法。但是，如果测试的节点靠近树的底部并且潜在的父节点位于顶部的某个地方，则此方法的性能要好得多。结合这两种算法将减轻两种最坏的情况。但是，内存开销是一个问题。

还有另一种方法吗？任何指针都非常感谢！

我编写了 Perl 代码来实际创建一个Trie数据结构，给定数组中的一组单词。现在我在遍历和打印单词时遇到问题。

还粘贴了创建的数据结构的 Dumper 输出。

遍历后的最后一组单词似乎不正确，因为遍历逻辑肯定遗漏了一些东西。但是 trie 的创建很好并且运行速度很快。有人可以在这里帮助我吗？

trie的顶层是哈希

1. 每个散列项都有一个键，它是一个字母，每个散列指向一个数组 ref。

2. 数组 ref 再次包含一个哈希列表，每个哈希项与 1 相同

如果您在输出中看到第一个单词。它以archtopriumwe的形式出现。

我们应该得到弧，拱，顶，中庭，敬畏

代码

输出：

我一直在尝试在 C 中实现将字符插入到 trie 数据结构中的基本功能。我一直在试图找出我做错了什么，但在最后一天左右我被难住了/卡住了。

这是我写的一些代码：

我想不通这个...

PS checkLetter，是一个布尔函数，检查字母是否已经在trie里面（通过遍历trie结构，即trie = trie->sibling）

任何帮助将不胜感激=]

干杯!

编辑：更改了我的代码，以便 insertInOrder 返回一个值，但由于 insert 是一个 void 函数并且必须保持一个 void 函数，我不知道有一种方法可以将节点进一步插入到 trie 的头部（即 head ->孩子，头->孩子->孩子等）

有谁知道用于后缀尝试的真正坚如磐石的 C++ 库？除了 Mummer 中的那个？
理想情况下，我想要：
一些并发的概念。
良好的缓存行为。
许可许可证。
支持任意字母。

I have a trie-based word detection algorithm for a custom dictionary. Note that regular expressions are too brittle with this dictionary as entries may contain spaces, periods, etc.

I've implemented the algorithm in a local C# app that reads in the dictionary from file and stores the trie in memory (it's compact, so no RAM size issues at all). Now I would like to use this algorithm in an MVC 3 app on a cloud host like AppHarbor, with the added twist that I want a web interface to enable adding/editing words.

It's fast enough that loading the dictionary from file and building the trie every time a user uploads their text would not be an issue (< 1s on my laptop). However, if I want to enable admins to edit the dictionary via the web interface, that would seem tricky since the dictionary would potentially be getting updated while a user is trying to upload text for analysis.

What is the best strategy for storing, loading, and updating the trie in an MVC 3 app?