问题标签 [prefix-tree]

这个问题解释了我要解决的问题： Finding the single nearest neighbor using a Prefix tree in O(1)?

我的问题是关于该问题页面中提出的解决方案部分。在那一节中提到，我们通过从节点开始遍历树来从每个前缀树中找到最近的邻居。查找前缀树中是否存在键很简单，但得到最相似的键我根本不明白。如何做到这一点？

我希望有人可以向我解释这一点，如果不是以图形方式（这是首选），那么至少有一些细节。

编辑：

这是论文的代码。它是用 python 编写的，不幸的是我以前从未使用过 python。如果有人熟悉 python 并且可以查找代码以查看他们如何使用前缀树找到最近的邻居。https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/nearest_neighbor_lsh.py

https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/classes.py

我写了一个简单的函数来确定 str1 是否是 str2 的前缀。这是一个非常简单的函数，看起来像这样（在 JS 中）：

如您所见，它遍历前缀字符串的整个长度以判断它是否是候选字符串的前缀。这意味着它的复杂度是 O(N)，这还不错，但是当我有一个庞大的数据集要考虑循环以确定哪些字符串具有前缀字符串作为前缀的一部分时，这就会成为一个问题。这使得复杂度倍数为 O(M*N)，其中 M 是给定数据集中的字符串总数。不好。

我在 Internet 上进行了一些探索，以确定最佳答案是 Patricia/​​Radix trie。字符串存储为前缀的位置。即使那样，当我尝试插入/查找字符串时，如果我使用上述前缀测量功能，字符串匹配也会有相当大的开销。

假设我有一个前缀字符串“rom”和一组候选词

var dataset =["random","rapid","romance","romania","rome","rose"];

在 radix trie 中会这样：

这意味着，对于每个节点，我将使用前缀匹配函数来确定哪个节点的值与索引处的前缀字符串匹配。不知何故，这个解决方案似乎仍然很艰巨，对我来说不太合适。有没有更好的东西或者我可以改进核心前缀匹配功能？

假设给定我们的无前缀二进制码有 11 个长度为 4 的码字和 2 个长度为 2 的码字。我们被要求为它提供一个示例，但是当码长为4 我们只能使用 1 和 0（二进制代码）。

我有一个前缀树来存储大量的单词。现在，如果我想找到所有带有公共前缀“a”的单词，我首先检索包含 a 的第一个节点，然后在第一个节点的子节点中以深度优先方式彻底搜索。虽然这个想法看起来很天真和简单，但如果具有公共前缀的单词的可能数量非常高（> 20K），它实际上是非常缓慢的。有没有其他方法可以有效地检索所有以公共前缀开头的单词？还是我应该采用其他数据结构？提前谢谢你。

EDIT1 基本上我通过访问每个节点并逐步添加字符来创建一个完整的单词。所有单词稍后都存储在向量容器中。是的，我有递归实现。

编辑2

编辑 3 已解决！！！我的实现实际上存在问题。我在递归调用中传递了这个巨大的向量字符串容器，这实际上是问题所在。谢谢大家的好意建议。

我需要为最长的两个模式前缀/后缀匹配编写算法，其时间复杂度为 O(n+m1+m2)，其中 n 是字符串的长度，m1，m2 分别是模式 1 和模式 2 的长度。

示例：如果 String 是“OBANTAO”，Pattern1 是“BANANA”，Patten2 是“SIESTA”，那么答案是 String 的子字符串“BANTA”，由 BANANA 的前缀 BAN 和 SIESTA 的后缀 TA 组成。

来自 Google 的结果是：“Rabin-karp 字符串搜索算法”、“Knuth-morris-pratt 算法”和“Boyer-moore 字符串搜索算法”。

我能够理解上述所有 3 种算法，但问题是，它们都是基于“单一模式前缀/后缀匹配”的。我无法将它们扩展为两个模式前缀/后缀匹配。

一个示例算法或搜索它的链接将对我开发程序有很大帮助。

我正在尝试编写一个函数来将文本文件中的单词输入到前缀树中，但它一直给我分段错误

经过一些测试，我很确定问题出在附加功能上。

如果有人详细解释原因以及在哪种情况下一种比另一种更有利，那将有很大帮助。提前致谢 ！！

假设我们有一个来自英语词典的 AZ 中所有词典单词的列表。

我要对这些单词列表执行三个案例：

1）找出所有“以”开头的特定片段的单词

2）找出所有“包含”片段作为子字符串的单词

3）找出所有“以”结尾的特定片段的单词

在互联网上进行了一些搜索练习后，我发现 1）可以通过 trie/compressed trie 完成，3）可以通过后缀树完成。

我不确定如何实现 2)。另外有没有更好的场景可以处理所有这三种情况？因为维护前缀和后缀树可能是一项内存密集型任务。

请让我知道其他需要注意的地方。

提前致谢。

PS：我将使用 C++ 来实现这一点

编辑 1：暂时我在此处的巨大帮助下构建了一个后缀树。

C语言中的单字后缀树生成

在这里，我需要为整个英语词典单词构建一个后缀树。那么我应该创建一个

a）每个单词的单独后缀树或

b) 为所有单词创建一个通用后缀树。

我不确定如何在 a) 情况下进行子字符串匹配时跟踪每个单词的单个树

任何指针？

我从 Code Review 中找到了这个 trie 实现，它运行良好，我已经以某种方式对其进行了更改以适应我的程序的需求，现在我想操纵这个find()函数，以便我可以将结果放在一个数组中。谢谢。这是课程代码：

我有一个 trie（也称为前缀树）。给定一个前缀，我想得到一个以前缀开头的十个单词的列表。

这个问题的独特之处在于我只想要10 个以给定前缀开头的单词——而不是全部。鉴于此，可以进行优化。

我知道下面的代码可以正常工作。trie 中的每个节点都有一个children属性和一个this_is_the_end_of_a_word属性。例如，当您插入“hi”时，trie 如下所示：

.

问题：给定一个前缀，我想得到一个以该前缀开头的十个单词的列表。

我解决这个问题的方法是：沿着前缀树向下，跟随 的字符，prefix直到到达与 . 的最后一个字符相对应的节点prefix。现在您应该在该节点上执行 DFS，跟踪this_is_the_end_of_a_word === true列表中的节点。但是当列表的长度等于 10 时，您应该停止搜索，并返回列表。

我认为我的方法是合理的，但我在实现它时遇到了麻烦——特别是因为我正在尝试使用递归 DFS，所以我不确定如何在递归调用之间传递“全局”列表。我知道我应该使用闭包，但我是 javascript 新手，我不确定如何去做。我已经尝试过的一个例子如下。

我的 Trie 类（我知道这段代码有效，这只是为了让您了解我是如何组织我的数据结构的。）

我的第一种方法（有很多错误）

}

第二种方法：我还发现了一个我正在查看的 python 示例：http: //v1v3kn.tumblr.com/post/18238156967/roll-your-own-autocomplete-solution-using-tries 我尝试将他的示例翻译成 JavaScript，但仍然有问题all_suffixes。