我正在实现一个基数树/ patricia trie(无论你想要什么叫它).我想在一个严重不足的硬件上使用它在字典中进行前缀搜索.它应该或多或少地像自动完成一样工作,即显示键入的前缀匹配的单词列表.
我的实现基于这篇文章,但其中的代码不包括前缀搜索,尽管作者说:
[...]假设您要枚举所有具有公共前缀"AB"的键的节点.您可以从该根开始执行深度优先搜索,每当遇到后边时停止.
但是我不明白这是怎么回事.例如,如果我从这些单词构建基数树:
疾病
虚构的
想象力
想象 立即
模仿 立即 巨大 的
对于前缀"i"和"in",我将得到完全相同的"最佳匹配",这样我就很难通过从最佳匹配中遍历树来收集所有匹配的单词.
此外,Java中的基数树实现在RadixTreeImpl.java中具有已实现的前缀搜索.该代码显式检查所有节点(从某个节点开始)的前缀匹配 - 它实际上比较了字节.
有人能指出我在基数树上实现前缀搜索的详细描述吗？Java实现中使用的算法是唯一的方法吗？