我目前正在实现一个基数树/帕特里夏特里（无论你想怎么称呼它）。我想用它在功能严重不足的硬件上的字典中进行前缀搜索。它应该或多或少像自动完成一样工作，即。 e.显示与键入的前缀匹配的单词列表。
我的实现是基于关于这篇文章，但其中的代码不包括前缀搜索，尽管作者说：
[...] 假设您想要枚举所有具有公共前缀“AB”的键的节点。您可以从该根开始执行深度优先搜索，只要遇到后边缘就停止。
但我不明白这应该如何运作。例如，如果我从这些单词构建一个基数树：
illness
假想
想像力
想象
模仿
即时
立即地
巨大
in
对于前缀“i”和“in”，我将获得完全相同的“最佳匹配”，因此对我来说，仅通过从最佳匹配遍历树来收集所有匹配的单词似乎很困难。
此外，还有一个Java中基数树的实现已实现前缀搜索RadixTreeImpl.java。该代码显式检查所有节点（从某个节点开始）是否有前缀匹配 - 它实际上比较字节。
谁能指出我在基数树上实现前缀搜索的详细描述？ Java实现中使用的算法是唯一的方法吗？
想想你的 trie 编码了什么。在每个节点，您都有通往该节点的路径，因此在您的示例中，您从对应于空字符串的根节点 Λ（这是一个大写的 Lambda，这种希腊字体有点糟糕）开始。 Λ 对于所使用的每个字母都有子代，因此在您的数据集中，您有一个分支，即“i”。
在“i”节点处，有两个子节点，一个代表“m”，一个代表“n”。下一个字母是“n”，所以你认为，
由于数据集中唯一以“i”、“n”开头的单词is“in”，没有来自“n”的孩子。那是一场比赛。
现在，假设数据集不是“in”，而是“infindibulum”。 （我引用的 SF 留作练习。）您仍然会以相同的方式到达“n”节点，但是如果您得到的下一个字母是“q”，您就知道该单词不会出现在你的数据集中，因为没有“q”分支。那时，你会说“好吧，不匹配”。 （也许你然后开始添加这个词，也许不是，这取决于应用程序。）
但如果下一个字母是“f”，您可以继续。不过，您可以用一点技巧来短路：一旦到达代表唯一路径的节点，您就可以将整个字符串离开该节点。当你到达该节点时，你知道字符串的其余部分must是“findibulum”，因此您使用了前缀来匹配整个字符串，然后返回它。
你怎么用它？在许多非 UNIX 命令解释器中，例如旧的 VAX DCL，您可以使用命令的任何唯一前缀。所以，相当于ls(1) was DIRECTORY，但没有其他命令以 DIR 开头，因此您可以输入DIR这与完成整个单词一样好。如果你记不住正确的命令，你可以只输入“D”，然后按（我认为）ESC； DCL CLI 会返回给你all以开头的命令D，它可以非常快地搜索。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
