问题标签 [prefix-tree]

我得到了一组（没有重复）具有任意长度和数字的二进制字符串，并且需要找出是否有任何字符串是其他字符串的前缀。对于小集合和长度小的字符串，这很容易，只需通过读取每个字符串来构建二叉树，每当我找到前缀匹配时，我就完成了。但是对于很多长度很长的字符串，这种方法效率不高. 只是想知道什么是正确的数据结构和算法。霍夫曼树？尝试（基数树）？还是什么？谢谢。

我试图在 dict_free() 函数中释放内存，但它不起作用，我不知道为什么。我错过了什么吗？想不通，怎么回事。

编辑：如果我在 dict_free() 中调用 free()，我希望看到 free'd 指针指向 NULL，但这并没有发生。

这是我的代码：

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

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

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

但这不会编译：

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

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

好的，这有点棘手。

我有一堆代码采用表达式树，例如：

((a + b)/(c + d) + sqrt(e))

以前缀形式存储在向量中（我使用的是 C++，但我只需要算法）：

+(/(+(a,b),+(c,d)),sqrt(e))//括号只是为了帮助您阅读它。每个运算符和终端都是向量中的一个元素。

现在有另一种表示表达式树的方法，称为 ORF 形式

（论文第三页：http: //arxiv.org/ftp/cs/papers/0102/0102027.pdf）

在这种形式中，您可以将树表示为从左到右、从上到下阅读树。

((a + b)/(c + d) + sqrt(e))现在变成：

+/sqrt++eabcd

我一直未能做的是创建一个可以转换的算法：

+/sqrt++eabcd//ORF 成：
+(/(+(a,b),+(c,d)),sqrt(e))//前缀

到目前为止，我所拥有的只是一些代码来获取不同级别的树的广度：

提前感谢您的帮助！这让我很头疼。哦，这对性能至关重要:(

我已经实现了一个基本的前缀树或“trie”。特里树由这样的节点组成：

假设我在我的 trie 中添加了以下词：“Apple”、“Ark”和“Cat”。现在，当我查找诸如“Ap”和“Ca”之类的前缀时，我的 trie 的“bool containsPrefix(string prefix)”方法将正确返回 true。

现在我正在实现方法“bool containsWholeWord(string word)”，它将为“Cat”和“Ark”返回true，但为“App”返回false（在上面的示例中）。

trie 中的节点具有某种“endOfWord”标志是否很常见？ 这将有助于确定要查找的字符串是否实际上是输入到 trie 中的整个单词，而不仅仅是前缀。

干杯!

我有一些序列，因为这些

在 C++ 中有一些有效的实现前缀树或 fp-tree 或类似的吗？

我需要删除除根之外的前缀树的所有子级。我不问任何代码。我只需要一种方法来遍历和删除树的所有子节点。

关于来自维基百科的特里：

【对比HashTable】尝试支持有序迭代

我不确定这里首先是什么意思。它与排序迭代相同吗？
此外，这应该是该数据结构的固有特征吗？
我的意思是，如果将 aHashSet用于 a 中每个节点的子节点，Trie我们可以O(1)尝试找到要分支的子节点，或者使用 aLinkedList可以节省节点上的空间。
也许我错了，但从我的角度来看，支持ordered迭代的唯一方法是保持每个节点的所有键数组甚至未使用。
这种方法不好吗？
最后一点：
如果ordered这里与插入顺序（而不是排序）有关，因为我们将每个单词（使用字符作为键）插入到相应的节点，我们将如何得到它，但我看不出这如何为我们提供有关插入顺序的信息？
有人能帮我把这些事情弄清楚吗？
谢谢你。

做一个具体的例子：

• 你有一个美国每个名字的列表。
• 您想在 GUI 中自动建议完成。

显而易见的事情是使用基数树来获取给定前缀的名称列表。但是，这没有考虑频率信息。因此，我想要最常见的 5 个名称，而不是仅将前 5 个结果作为第一个词汇结果：

例如对于前缀dan

有没有我错过的特里树算法？当然，理想的实现（如果存在的话）在我看来是在 python 中。

更新：总体上对 Paddy3113 的建议感到满意，尽管我会说当我向它提供 2.6GB 文件时它完全爆炸了，这是我正在减少的文件之一。查看详细信息，输出提供了一些见解：

我们在赏金方面还有几天的时间，所以我仍在寻找杀手级解决方案。因为这不仅与减少有关，还与事物的查找有关。