c++ - 在基数树/patricia trie 中进行前缀搜索

Question

我目前正在实现一个基数树/patricia trie(随便你怎么调用它)。我想用它在一个功能严重不足的硬件上的字典中进行前缀搜索。它应该或多或少像自动完成一样工作，我。 e.显示输入的前缀匹配的单词列表。

我的实现基于on this article ，但其中的代码不包括前缀搜索，尽管作者说:

[...] Say you want to enumerate all the nodes that have keys with a common prefix "AB". You can perform a depth first search starting at that root, stopping whenever you encounter back edges.

但我不明白它应该如何工作。例如，如果我从这些词构建一个基数树:

illness
imaginary
imagination
imagine
imitation
immediate
immediately
immense
in

对于前缀“i”和“in”，我将获得完全相同的“最佳匹配”，因此我似乎很难通过从最佳匹配开始遍历树来收集所有匹配的词。

此外，还有一个 radix tree implementation in Java在 RadixTreeImpl.java 中实现了前缀搜索.该代码显式检查所有节点(从某个节点开始)的前缀匹配 - 它实际上比较字节。

任何人都可以指出有关在基数树上实现前缀搜索的详细说明吗？ Java 实现中使用的算法是唯一的方法吗？

Answer 1

想想您的 trie 编码的内容。在每个节点，您都有通往该节点的路径，因此在您的示例中，您从 Λ(这是一个大写的 Lambda，这种希腊字体有点糟糕)开始，根节点对应于一个空字符串。 Λ 为使用的每个字母都有子代，因此在您的数据集中，您有一个分支，用于“i”。

• Λ
• Λ→"i"

在“i”节点，有两个子节点，一个用于“m”，一个用于“n”。下一个字母是“n”，所以你接受它，

• Λ→"i"→"n"

并且由于在您的数据集中唯一以“i”、“n”开头的词是“in”，因此没有来自“n”的子项。这是一场比赛。

现在，假设数据集没有“in”，而是“infindibulum”。 (我引用的 SF 留作练习。)您仍然会以相同的方式到达“n”节点，但是如果您得到的下一个字母是“q”，您就知道这个词没有出现在你的数据集中，因为没有“q”分支。那时，你说“好吧，不匹配”。 (也许你然后开始添加这个词，也许不，这取决于应用程序。)

但是如果下一个字母是“f”，你可以继续前进。不过，您可以使用一些技巧将其短路:一旦您到达代表唯一路径的节点，您可以将整个字符串卡在该节点上。当您到达该节点时，您知道字符串的其余部分必须 是“findibulum”，因此您使用前缀来匹配整个字符串并返回它。

你如何使用它？在许多非 UNIX 命令解释器中，例如旧的 VAX DCL，您可以使用命令的任何唯一前缀。因此，ls(1) 的等价物是 DIRECTORY，但没有其他命令以 DIR 开头，因此您可以键入 DIR，这就像就像做整个词一样好。如果您不记得正确的命令，您可以只输入“D”，然后按(我认为)ESC； DCL CLI 会向您返回所有 以D 开头的命令，它可以非常快速地搜索这些命令。