问题标签 [prefix-tree]

我有一个问题问你。我必须实现一个包含 30000 个名称的业务通讯簿。所有名称都包含名字和姓氏。我必须实现一个自动完成文本框，它不仅可以搜索输入名字，还可以搜索姓氏。在 google 上搜索我发现这个问题是使用 patricia trie 解决的，但它只做前缀搜索，所以如果我用 firstname+lastname 创建一个 trie，我如何不仅可以按名字搜索，而且可以按姓氏搜索？

我是否必须复制插入两个这样的字符串的条目？名字+姓氏和姓氏+名字

请帮我！！！

搜索必须非常有效。

谢谢。

对于我的特定应用程序，F# 的 Map 和 Set 的性能相当欠缺。似乎一个不错的前缀特里树会大大提高我的解释器的性能，尤其是在按名称查找符号方面。唯一需要注意的是，它必须对添加和查找操作非常有效（尤其是当键是字符串时），并且对于持久性是不可变的（意味着非破坏性更新）。

如果没有这样的野兽可用，OCaml 或 Haskell 的参考实现将帮助我开始使用。

非常感谢！

我想通过使用单词作为符号而不是字符来压缩文本，我真的不知道这是否是一个好主意，但我只想测试它（用于科学）。

问题是，我不能真正存储英语的所有单词，所以我收集了一个非常常见的单词列表（大约 1600 个单词），我打算像拼写检查器存储派生形式的单词一样对其进行更改。（例如：kill、kill-ing、kill-er、kill-s 取决于它是动词、形容词等）

http://en.wikipedia.org/wiki/Canonical_Huffman_code

我想知道这个特殊版本的霍夫曼编码是否适合我的需要，因为“字典”不会经常更改并且可以与解压缩工具一起分发。在创建原始霍夫曼树之前，我似乎还必须指定单词的频率，然后再将其变成规范的霍夫曼树。

如果我在这里遗漏了一点，或者这是一个好主意还是坏主意，你能纠正我吗？

我有一大组字符串，大约 10^12 左右，我需要选择一个合适的数据结构，这样，提供一个字符串，我可以检索和关联整数值，比如 O(log(n))或 O(m) 时间，其中“n”是字符串列表的长度，“m”是每个字符串的长度。

我们可以预期，我们的字符串集，每个长度为“m”并编码在一些大小为“q”的字母表上，几乎涵盖了该长度的所有可能字符串。例如，假设我们有 10^12 个长度为 m = 39 的全唯一二进制字符串。这意味着我们已经覆盖了该长度的所有可能二进制字符串集合的约 54%。

因此，我担心为避免冲突的字符串找到合适的散列函数。有什么好的我可以用吗？索引我的一组 n 个字符串需要多长时间？

还是我应该使用后缀树？我们知道 Ukkonen 的算法允许线性时间构造，我的猜测是考虑到大量相似的字符串，这将节省空间？

I am implementing a prefix tree, with a standard insertion mechanism. If we know we will be given a list of words in alphabetical order, is there any way we can change the insertion to skip a few steps? I am coding in Java, although I'm not looking for code in any particular language. I have considered adding the Nodes for each word to a queue, then hopping backwards through it until we're at a prefix of the next word, but this may be circumventing the whole point of the prefix tree!

Any thoughts on something like this? I'm finding it hard to come up with an implementation that's of any use unless the input is many many very similar words ("aaaaaaaaaab", "aaaaaaaaaac", "aaaaaaaaaad", ...) or something. But even then doing a string comparison on the prefixes is probably a similar cost to just using the prefix tree normally.

我有一个类似字符串的字符串

并将其转换为输出此字符串的 CNF，例如

（或（非 P）（或 AB））（或（非 P）（或（非 B）（非 A）））

我需要制作一个结构 TreeNode 来保持价值吗？

如何使其成为合取范式的CNF？请给出一些算法细节。从我的角度来看，也许使用递归函数更好地解决这个问题，但我仍然想不出如何使用递归。或者您有其他解决此问题的建议？

我写了以下前缀特里：

我想添加 DFS 方法以查找具有多个子节点的第一个节点（因此它会显示最长的公共前缀）。

我写了这段代码：

但它不起作用。我究竟做错了什么？

假设我有一个字符串列表和这些字符串的前缀树，我想找到一个给定键的字符串，哪个更快？二分查找还是前缀树查找？

为什么以及时间复杂度是多少？

谢谢！

我正在阅读一篇论文，他们提到他们能够使用前缀树在 O(1) 中找到单个最近邻居。我将描述一般问题，然后是经典解决方案，最后是本文中提出的解决方案：

问题：给定一个位向量列表 L（所有向量具有相同的长度）和查询位向量 q，我们想找到 q 的最近邻。距离度量是汉明距离（有多少位不同）。天真的方法是遍历列表并计算列表中每个向量与 q 之间的汉明距离，这将花费 O(N)。然而，鉴于我们将拥有数百万个非常昂贵的位向量，因此我们希望减少它。

经典解决方案：这个问题的经典解决方案是使用近似值来找到最近的邻居，从而达到 O(logN)。这样做的方法是首先按字典顺序对 L 进行排序，以便相似的位向量彼此接近。然后给定 q，我们在排序列表上应用二分搜索来获得 q 在排序列表中的位置，并在列表中获取它上面和下面的向量（因为它们是相似的排序原因）并计算它们之间的距离并选择具有最低汉明距离的那个。然而，仅仅简单地进行一次排序，我们仍然会错过许多相似的向量，因此为了尽可能多地覆盖相似的向量，我们使用了 P 个列表和 P 个混杂函数。每个混杂函数对应每个列表。然后我们将每个位向量插入到 P 中的每个列表中，然后将其位与相应的混杂函数混杂。所以我们最终得到 P 个列表，每个列表都有位向量，但位的顺序不同。我们再次按字典顺序对 P 中的每个列表进行排序。现在给定 q，我们对 P 中的每个列表应用相同的二分搜索，但这里我们之前根据我们正在访问的列表对 q 应用混杂函数。在这一步中，我们得到了与 q 最相似的向量的 P 个，因此我们最终得到了与 q 最相似的向量。这样我们就可以覆盖尽可能多的相似向量。通过忽略排序所需的时间，找到最近邻居所需的时间为 O(log n)，即对每个列表进行二分查找的时间。我们再次按字典顺序对 P 中的每个列表进行排序。现在给定 q，我们对 P 中的每个列表应用相同的二分搜索，但这里我们之前根据我们正在访问的列表对 q 应用混杂函数。在这一步中，我们得到了与 q 最相似的向量的 P 个，因此我们最终得到了与 q 最相似的向量。这样我们就可以覆盖尽可能多的相似向量。通过忽略排序所需的时间，找到最近邻居所需的时间为 O(log n)，即对每个列表进行二分查找的时间。我们再次按字典顺序对 P 中的每个列表进行排序。现在给定 q，我们对 P 中的每个列表应用相同的二分搜索，但这里我们之前根据我们正在访问的列表对 q 应用混杂函数。在这一步中，我们得到了与 q 最相似的向量的 P 个，因此我们最终得到了与 q 最相似的向量。这样我们就可以覆盖尽可能多的相似向量。通过忽略排序所需的时间，找到最近邻居所需的时间为 O(log n)，即对每个列表进行二分查找的时间。这样我们就可以覆盖尽可能多的相似向量。通过忽略排序所需的时间，找到最近邻居所需的时间为 O(log n)，即对每个列表进行二分查找的时间。这样我们就可以覆盖尽可能多的相似向量。通过忽略排序所需的时间，找到最近邻居所需的时间为 O(log n)，即对每个列表进行二分查找的时间。

建议的解决方案：论文中提出的这个解决方案（但没有任何解释）说我们可以使用前缀树在 O(1) 时间内获得最近的邻居。在论文中他们说他们使用了 P 个前缀树和 P 个混杂函数，其中每个混杂函数对应于每棵树。然后他们在将每个向量的比特与相应的混杂函数混杂之后，将比特向量插入到每棵树中。给定 q，我们将跳跃函数应用于与每棵树对应的 q，并从每棵树中检索与 q 最相似的向量。现在我们最终得到了从树中检索到的 P 位向量。在论文中，他们说从前缀树中获取与 q 最相似的向量是 O(1)。我真的不明白这一点，因为我知道搜索前缀树是 O(M) 其中 M 是位向量的长度。

这是我所指的论文（第 3.3.2 节）：实时 Web 上基于内容的人群检索

http://students.cse.tamu.edu/kykamath/papers/cikm2012/fp105-kamath.pdf

我也希望您能回答我与此相关的另一个问题：如何在前缀树中查找最相似的位向量以进行 NN 搜索？

给定一个前缀树和一个键。在树中查找密钥的成本是多少？

我在一篇论文中读到它是 O(1)。据我所知，它是 O(LogM)，其中 M 是密钥的长度。我找不到答案，为什么它是 O(1)，但有人提到，关键可能是如果我们忽略扫描密钥，那么它将是 O(1)。如果我们忽略扫描密钥，有人可以以图形方式（通过制作树并遍历）向我解释它是 O(1) 吗？