在基数树 patricia trie中搜索前缀

在基数树/ patricia trie中搜索前缀

考虑一下您的特里编码。在每个节点上，都有通往该节点的路径，因此，在您的示例中，从与空字符串相对应的根节点Λ（这是大写的Lambda，这种希腊字体很烂）开始。Λ每个使用的字母都有孩子，因此在您的数据集中，您有一个分支“
i”。

• Λ
• Λ→“ i”

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

• Λ→“ i”→“ 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

搜索速度可能非常快。