Python中的Trie(前缀树)

Question

我不知道这是否是询问算法的地方.但是,让我们看看我是否得到任何答案...... :)

如果有什么不清楚我很乐意澄清事情.

我刚刚在python中实现了一个Trie.然而,有一点似乎比它应该更复杂(作为一个喜欢简单的人).也许有人遇到过类似的问题？

我的目标是通过在其根中存储子trie的最大公共前缀来最小化节点数.例如,如果我们有stackoverflow,stackbase和stackbased这两个词,那么树看起来像这样:

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

注意,人们仍然可以想到边缘具有一个字符(子节点的第一个).

查找 -query很容易实现. 插入并不难,但比我想要的更复杂.. :(

我的想法是一个接一个地插入密钥(从一个空的trie开始),首先搜索要插入的密钥k(Find(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路由表的第二快方法,最快的是某种哈希特里.