问题标签 [trie]

假设构建了字典单词的一般 Trie，那么在遍历期间检查 4 种拼写错误的最佳方法是什么 - 替换、删除、转置和插入？

一种方法是找出给定单词 n 个编辑距离内的所有单词，然后在 Trie 中检查它们。这不是一个坏选择，但这里更好的直觉似乎是使用动态编程（或递归等效）方法来确定在遍历期间修改单词后的最佳子尝试。

欢迎任何想法！

PS，会欣赏实际的输入，而不仅仅是答案中的链接。

除了好玩之外，我今天无缘无故地实现了一个Trie。目前它支持 add() 和 search()，remove() 也应该实现，但我认为这是相当直接的。

它功能齐全，但是用数据填充 Trie 对我来说有点太多了。我将此列表用作数据源：http ://www.isc.ro/lists/twl06.zip （在 SO 的其他地方找到）。加载大约需要 11 秒。我最初的实现花了大约 15 秒，所以我已经给它一个很好的性能提升，但我仍然不满意 :)

我的问题是：还有什么可以给我（大幅）性能提升？我不受这种设计的约束，彻底检修是可以接受的。

我研究过 Tries 和 Suffix Trees 并想实现相同的。请分享一些链接，我可以从中了解结构和实施的基本思想。

任何好的例子，如果包括在内，将是一个加号。

C中的实现。

好的，尝试已经有一段时间了。一个典型的实现应该给你 O(m) 的查找、插入和删除操作，与数据集的大小 n 无关，其中 m 是消息长度。然而，在最坏的情况下，同样的实现每个输入字节占用 256 个字。

其他数据结构，特别是散列，为您提供预期的 O(m) 查找、插入和删除，有些实现甚至提供恒定时间查找。然而，在最坏的情况下，例程要么不停止，要么花费 O(nm) 时间。

问题是，是否有一种数据结构可以提供 O(m) 查找、插入和删除时间，同时保持与散列或搜索树相当的内存占用？

说我只对时间和空间上的最坏情况行为感兴趣可能是合适的。

我正在寻找在一些免费许可下发布的 ANSI C HAT-trie 实现。我还没有找到一个。您能否指出一些独立的实现或使用 HAT 的程序尝试至少稍微了解如何以正确的方式实现它，好吗？

关于 HAT-trie 的原始论文可以在这里找到： http ://crpit.com/confpapers/CRPITV62Askitis.pdf

PS：如果自写上述论文以来，更快的缓存意识数据结构非常适合字符串，请指出我的论文或示例源代码。

我正在尝试编写一个与字典中是否存在字符串相匹配的 C++ 函数。它可以是部分字符串或完整字符串。所以我把每一行都读成了一个特里

有人可以帮我解决这个问题。我添加了用于阅读字典中单词的代码。

我得到了trie背后的概念。但是在实现方面我有点困惑。

我能想到的最明显的构造Trie类型的方法是Trie维护一个 internal Dictionary<char, Trie>。事实上，我已经以这种方式编写了一个，并且它有效，但是......这似乎有点矫枉过正。我的印象是 trie 应该是轻量级的，并且每个节点Dictionary<char, Trie>都有一个单独的节点对我来说似乎不是很轻量级。

有没有更合适的方法来实现我所缺少的这种结构？

更新：好的！根据 Jon 和 leppie 的非常有用的意见，这是我迄今为止提出的：

(1) 我有Trie类型，它有一个私有_nodes成员 type Trie.INodeCollection。

(2)Trie.INodeCollection接口有以下成员：

(3) 该接口共有三种实现：

(4) 当 aTrie被第一次构造时，它的_nodes成员是null。根据上述步骤，第一次调用Add创建一个SingleNode，随后调用从那里开始。Add

这有意义吗？从某种意义上说，这感觉像是一种改进，它在一定程度上减少了 a 的“体积” （节点在拥有足够数量的子节点之前Trie不再是成熟的对象）。Dictionary<char, Trie>然而，它也变得更加复杂。是不是太纠结了？我是否采取了一条复杂的路线来实现本应直截了当的事情？

这听起来像一个简单的问题，但我不知道如何搜索它的答案。

我在 C# 中有一个 trie 实现，它将存储字典文件中的大约 80K 单词。加载所有这些单词需要相当长的时间（超过 5 分钟）。我想知道，“持久化”这些数据的最佳方式是什么，这样我每次启动应用程序时都不必重新加载所有单词？

谢谢。

最近我一直在研究 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 功能？

是否有任何库或文档/链接可以提供更多关于在 java 中实现 Trie 数据结构的信息？

任何帮助都会很棒！

谢谢。