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

Question

我正在实现一个基数树/ patricia trie(无论你想要什么叫它).我想在一个严重不足的硬件上使用它在字典中进行前缀搜索.它应该或多或少地像自动完成一样工作,即显示键入的前缀匹配的单词列表.

我的实现基于这篇文章,但其中的代码不包括前缀搜索,尽管作者说:

[...]假设您要枚举所有具有公共前缀"AB"的键的节点.您可以从该根开始执行深度优先搜索,每当遇到后边时停止.

但是我不明白这是怎么回事.例如,如果我从这些单词构建基数树:

疾病
虚构的
想象力
想象 立即
模仿 立即 巨大 的

对于前缀"i"和"in",我将得到完全相同的"最佳匹配",这样我就很难通过从最佳匹配中遍历树来收集所有匹配的单词.

此外,Java中的基数树实现在RadixTreeImpl.java中具有已实现的前缀搜索.该代码显式检查所有节点(从某个节点开始)的前缀匹配 - 它实际上比较了字节.

有人能指出我在基数树上实现前缀搜索的详细描述吗？Java实现中使用的算法是唯一的方法吗？

Answer 1

想想你的trie编码.在每个节点上,您都有引导您到该节点的路径,因此在您的示例中,您从Λ(这是一个大写的Lambda,这个希腊字体很糟糕)开始,对应于空字符串的根节点.Λ每个使用的字母都有子项,因此在您的数据集中,您有一个分支,用于"i".

• Λ
• Λ→ "我"

在"i"节点,有两个子节点,一个用于"m",一个用于"n".下一个字母是"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它可以非常快速地搜索.