trie - 搜索丢失字母的算法

Question

因此，我必须搜索缺少一些字母的单词（在填字游戏中使用），并且还必须维护剩余空格的可能单词列表。

现在我的问题是，如果是最快的搜索算法，我已经用谷歌搜索了那个突发特里。但是，如果我在 trie 中编写代码，那么我转向burst-trie 会有多难。？？

如果您没有得到任何东西，请耐心等待您可以发表评论以澄清任何一点。

Answer 1

首先是免责声明，我还没有写过burst-trie。但是，阅读您的问题后，我发现最初的论文提出了 Burst Tries，Burst Tries: A Fast, Ecient Data Structure for String Keys，听起来很直接。我已经编写了几个 trie 数据库和许多辅助函数。

从我读到的内容听起来你是按照标准方法编写 trie 并简单地将 bst 选项添加到你的结构并将其用于最后一个 char 序列。然后在您的 trie 类中添加一个“burst”函数，并在您的设置中，将 bst“burst”到新级别的 trie 结构中，并继续使用 bst 后缀树。

所以，我认为你的问题的答案是肯定的，很容易将你的 trie 转换为突发 trie。

Answer 2

只要你有正确的抽象层，将一个 trie 变成一个 Burst trie 实际上非常简单。有一个突发 trie 论文的Scala 实现（混合了 GWT 的 trie 实现中的一些想法），它在空间方面非常有效（并且在处理 trie 时空间限制是最明显的）。

如果您想构建自己的，请查看该实现以获取指导。它有点通用，因此可以以不同的方式使用；但如果您在 JVM 上并且不介意引入 scala 库，它应该适用于您的用例。