问题标签 [prefix-tree]

我正在编写一个算法，它将首先采用各种端点的配置文件及其相关方法，如下所示：

X这里代表一个通配符，所以任何字符串都可以匹配。该算法会将其作为输入并构建一棵树，其中每个节点代表/'s 之间的一个标记。每个叶子都是一个有效的端点。

然后当用户传入类似guest/abc/friends它会从根开始遍历树的东西时，然后查找guest连接到根的节点，如果存在则转到节点guest，如果guest这里来宾将有一个wildcard节点，那么如果abc不匹配任何ofguest的节点，但存在一个wildcard节点，它将转到wildcard. 然后它会查看wildcard它是否有一个friends节点，如果有就去那里。然后如果friends是叶节点，它将返回相应的方法。

这个算法有意义吗？我想知道查找的运行时间是什么。我认为这将是 O(n) 其中 n 是传入的参数中的令牌数。

这是我将根据上面的输入构建的图表的图像。每个菱形代表一个端点方法。

谢谢你的帮助！

我正在尝试在网站上实现支持自动完成的数据结构。我已经设法实现了 Trie 的迭代版本。它支持在 Trie 中添加和搜索的两种主要方法。但是现在我需要添加一个方法来返回所有以以下前缀开头的单词。有人可以帮我弄这个吗。

我想合并两个特里结构，但我能想到的最好的复杂性是

从其他 trie 获取值列表：O(n)，n 是 trie 中的节点数。从list intro target trie中插入所有值：n * O(m)，m是key的长度考虑到，最坏的情况下，key的大小是n，合并的复杂度不是O(n^2)吗？

有没有更好的方法呢？

背景：我正在研究用户代理字符串（Yuaaa）的分析器，作为此分析的一部分，我想对应该报告的设备品牌进行有根据的猜测。我有一个实现需要重写以提高效率。

因为我不想拥有所有设备的完整列表，所以我想根据模型的前缀进行检测。

所以我有一个带有前缀和相关品牌的数据集：

• "GT-" --> "三星"
• "LLD-" --> "华为"

然后我想做一个 .get("GT-1234124") 应该导致“三星”，因为那是“最长的匹配前缀”。

我查看了 Trie 结构，但这似乎是针对相反的情况。我的理解是，您从一组值开始，您可以有效地获取以提供的前缀开头的所有值。

如果我要从头开始实现它，我会使用类似于 Trie 的树，但会以不同的方式绕过它。我正在寻找的是一种尽可能快地完成我需要的数据结构。

您为此用例推荐什么数据结构？

我可以使用现有的（经过验证的）实现吗？

有没有一种方法可以计算给定字母字典的无前缀编码及其频率。类似于 Huffman-Coding 但动态计算 - 优化函数看起来如何？

仅仅为了字典的 i 位置而构建树的问题是，频率最低的字母可能会改变，因此整个树的结构也会改变。

给定一个字符串字典D和一个输入字符串S。我试图从D中找到某个字符串p ，它是S的前缀。

对于无序字典，最快的方法似乎是为D构建一个 trie并与S的初始字符一起遍历该 trie 。由于D中的字符串是无序的，因此这里最自然的搜索算法将是找到最长前缀p的算法。

但是，我需要为D中的字符串保留一个特殊的输入顺序。例如，对于D = [ bar, foo, foobar] 和S = foobariously，上述搜索将产生p = foobar，因为它是最长的前缀。但相反，我想得到p = foo，因为foo在输入列表中较早出现。

这种前缀搜索最快的算法是什么？我认为基本方法仍然涉及 trie，但我不知道如何将原始排序集成到其中。

nginx 中如何实现前缀字符串位置处理？

• http://nginx.org/r/location

具体来说，广泛报道http://nginx.org/r/server_name匹配是通过哈希表完成的——http: //nginx.org/docs/http/server_names.html——但没有类似的级别location指令的实施细节。

所以我有一个具有多个节点的前缀树对象。每个节点都由一个字符组成，无论它是最终节点，还是存储在对象指针数组中的子节点（最多 26 个值）。我需要打印在给定节点下找到的单词。

下面的例子。

如果在带有字符“a”的节点上调用该函数，它应该打印 ab 并采取行动。我计划通过添加到一个字符串直到到达一个标记为 final 的节点然后删除该字母来做到这一点。我想实现一个递归函数，但是在将一个节点设置为该节点的子节点时，我遇到了分段错误。

获取子函数：

节点对象：

我正在以形式编写脚本

随着标签数量的增加，我每行都会做太多的检查。我可以尝试将常见标签排序更高，但我认为它不能解决根本问题。我不是软件工程师。有没有可以改善这种情况的编程概念/方法？

我有一个路径列表，我想只保留不是任何其他项目前缀的项目。

例如，在以下列表中：

我只想保留：

我不喜欢“发明轮子”并实现前缀树，而是使用已经这样做的 python 包。

谢谢！