我目前正在实现基数树/ patricia trie（无论您想称呼它如何）。我想将其用于在功能严重不足的硬件上的字典中的前缀搜索。它应该或多或少像自动完成一样工作，即显示键入的前缀匹配的单词列表。
我的实现基于本文，但是其中的代码不包括前缀搜索，尽管作者说：
[…]假设您要枚举具有公共前缀为“ AB”的键的所有节点。您可以从该根开始执行深度优先搜索，每当遇到后边缘时便停止搜索。
但是我不知道这应该如何工作。例如，如果我从这些词构建基数树：
疾病 虚构 想象 想象 模仿 立即 立即 巨大 的
我将获得与前缀“ i”和“ in”完全相同的“最佳匹配”，因此我似乎很难仅通过从最佳匹配中遍历树来收集所有匹配单词。
此外，Java中有一个基数树实现，在RadixTreeImpl.java中具有已实现的前缀搜索。该代码显式检查所有节点（从某个节点开始）是否存在前缀匹配- 它实际上比较字节。
谁能指出我对在基数树上执行前缀搜索的详细说明？Java实现中使用的算法是唯一的方法吗？
考虑一下您的特里编码。在每个节点上，都有通往该节点的路径，因此，在您的示例中，从与空字符串相对应的根节点Λ（这是大写的Lambda，这种希腊字体很烂）开始。Λ每个使用的字母都有孩子，因此在您的数据集中，您有一个分支“ i”。
在“ i”节点上，有两个孩子，一个用于“ m”，一个用于“ n”。下一个字母是“ n”，所以你接受了
并且由于数据集中唯一以“ i”，“ n”开头的单词 是 “ in”，因此“ n”中没有子代。那是一场比赛。
现在，假设数据集具有“ infindibulum”，而不是“ in”。（我要参考的SF仍作为练习。）您仍然会以相同的方式到达“ n”节点，但是如果下一个字母是“ q”，则知道单词不会出现在您的数据集中根本没有，因为没有“ q”分支。那时，您说“好，不匹配”。（也许您然后开始添加单词，也许不是，取决于应用程序。）
但是，如果下一个字母是“ f”，则可以继续。不过，您可以通过一些技巧来实现以下目的：到达代表唯一路径的节点后，就可以将 整个字符串 挂在该节点上。当到达该节点时，您知道字符串的其余部分 必须 是“ findibulum”，因此您已使用前缀来匹配整个字符串，然后将其返回。
您如何使用它？在许多非UNIX命令解释器中，例如旧的VAX DCL，您可以使用命令的任何唯一前缀。因此， ls（1） 的等效项是DIRECTORY，但是没有其他命令以DIR开头，因此您可以键入DIR，这与完成整个单词一样好。如果您不记得正确的命令，则可以只键入“ D”，然后按（我认为）ESC；DCL CLI会返回以开头的 所有 命令，D搜索速度可能非常快。
DIRECTORY
DIR
D
