Python中的Trie（前缀树）

Question

我不知道这是否是询问算法的地方。但是让我们看看我是否有任何答案… :)

如果有任何不清楚的地方，我很乐于澄清。

我刚刚在python中实现了Trie。但是，似乎有些事情比应该做的要复杂（作为一个热爱简单的人）。也许有人遇到过类似的问题？

我的目标是通过在子根目录的根中存储最大的公共前缀来最大程度地减少节点数。例如，如果我们有单词 stackoverflow ，
stackbase 和 stackbased ，则树将如下所示：

              [s]tack
[o]verflow ______/ \_______ [b]ase
                                  \___ [d]

注意，仍然可以想到具有一个字符的边缘（子节点的第一个）。

Find -query很容易实现。 插入 并不难，但是比我想要的要复杂。

我的想法是，先搜索要插入的密钥k（ 查找
（k）），然后再在其中重新放置/拆分节点，然后再从空的树中插入密钥。查找过程停止。共有4种情况：（让k为我们要插入的键，而k’为搜索结束的节点的键）

1. k等于k’
2. k是k’的“适当”前缀
3. k’是k的“适当”前缀
4. k和k’共享一些公共前缀，但情况（1），（2）或（3）均不发生。

似乎每种情况都是唯一的，因此暗示对Trie的不同修改。但是：真的那么复杂吗？我想念什么吗？有没有更好的方法？

谢谢 ：）

Answer 1

乍一看，听起来您已经实现了Patricia
Trie
。在某些文献中，这种方法也称为路径压缩。该纸张的副本应位于ACM付费专区的后面，其中应包括插入算法。

您可能还需要查看另一种压缩方法：级别压缩。路径压缩的思想是用具有“跳过”计数的单个超级节点替换单个子节点的字符串。级别压缩的思想是用具有“度”数的超级节点替换完整或接近完整的子树，“度”数表示节点解码的密钥的位数。还有一种第三种方法，称为宽度压缩，但是恐怕我的记忆力不佳，我无法通过快速谷歌搜索找到它的描述。

级别压缩可以大大缩短平均路径，但是插入和删除算法变得非常复杂，因为它们需要像处理动态数组一样管理Trie节点。对于正确的数据集，级别压缩的树可能 很快
。据我所知，它们是存储IP路由表的第二快的方法，最快的是某种哈希算法。