我目前正在实现一个基数树/帕特里夏树（无论你想怎么称呼它）。我想用它在一个严重不足的硬件上的字典中进行前缀搜索。它应该或多或少像自动完成一样工作，即显示输入前缀匹配的单词列表。
我的实现基于这篇文章，但其中的代码不包括前缀搜索，尽管作者说：
[...]假设您要枚举所有具有公共前缀“AB”的键的节点。您可以从该根开始执行深度优先搜索，只要遇到后边缘就停止。
但我不明白这应该如何工作。例如，如果我从这些词构建一个基数树：
疾病
想象
想象
想象
模仿
立即
立即
巨大
的
对于前缀“i”和“in”，我将得到完全相同的“最佳匹配”，因此我似乎很难通过从最佳匹配中遍历树来收集所有匹配的单词。
此外，Java 中有一个基数树实现，它在RadixTreeImpl.java中实现了前缀搜索。该代码显式检查所有节点（从某个节点开始）是否有前缀匹配 - 它实际上比较字节。
谁能指出我在基数树上实现前缀搜索的详细描述？Java实现中使用的算法是唯一的方法吗？
想想你的 trie 编码了什么。在每个节点上，您都有通往该节点的路径，因此在您的示例中，您从 Λ（这是一个大写的 Lambda，这种希腊字体很烂）与空字符串对应的根节点开始。Λ 对使用的每个字母都有子级，因此在您的数据集中，您有一个分支，用于“i”。
在“i”节点，有两个孩子，一个用于“m”，一个用于“n”。下一个字母是“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它可以非常快速地搜索这些命令。
事实证明，标准 c++ lib 的 GNU 扩展包括一个 Patricia trie 实现。它位于基于策略的数据结构扩展下。请参阅http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html
另一种算法：保持简单愚蠢！
只需对您的关键字进行排序列表即可。当您有前缀时，二进制搜索以查找该前缀在列表中的位置。所有可能的完成都将从该索引开始，随时可以访问。
该算法将只需要 Patricia trie 的 5% 的代码，并且易于维护、理解和更新。几乎可以肯定，这个简单的列表搜索也会更有效。
唯一的缺点是，如果您有大量具有相似前缀的长关键字，则 trie 可以节省一些存储空间，因为它不需要为每个条目保留完整的前缀。在实践中，如果你的单词少于几百万，这不会节省，因为树的指针开销将占主导地位。这种节省更多地用于搜索具有数百万个字符的 DNA 字符串数据库等应用程序，而不是文本关键字。