Python中的Trie（前缀树）

Question

我不知道这是不是问问算法的地方。但让我们看看，如果我得到任何答案... :)

如果有什么不清楚我很高兴澄清事情。

我刚刚在python中实现了一个Trie。然而，有一点似乎比它应该更复杂（就像一个热爱简单的人）。也许有人有类似的问题？

我的目标是通过在其根中存储子树的最大公共前缀来最小化节点数。例如，如果我们有话计算器，stackbase和stackbased，则树会是这个样子：

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

注意，仍然可以认为有一个字符边缘（在第一个孩子节点）。

查找 - 查询很容易实现。 插入并不难，但有些较复杂的比我想.. :(

我的想法是插入后，其他的按键一个（从空开始特里），通过为将要优先搜索（k）（查找（k）），然后在查找过程停止的地方对节点进行本地重新排列/分割，结果为4种情况：设k是我们想要插入的密钥和k '是节点，在此处搜索结束）的关键

1. k是相同的k'
2. k是一个“适当的”前缀k'
3. k'是k的“适当”前缀k和k'共享一些共同的前缀，但情况（1），（2）或3）发生。

似乎每个案例都是独一无二的，因此意味着Trie的不同修改。但是：这真的很复杂吗？我错过了什么吗？有更好的方法吗？

谢谢:)

Answer 1

一眼就可以看出您已经实施了Patricia Trie。这种方法在一些文献中也被称为路径压缩。应该有不属于ACM付费墙的文件副本，其中包含插入算法。

还有另一种压缩方法，你可能想看看：级别压缩。路径压缩背后的想法是用具有“跳过”计数的单个超级节点替换单个子节点的字符串。级别压缩背后的想法是用超级节点替换完整或接近完整的子树，其中“度”数表示节点解码密钥的数目。还有一种称为宽度压缩的第三种方法，但是我担心我的记忆会使我失败，而且我无法用Google进行快速搜索。

级别压缩可以显着缩短平均路径，但插入和移除算法变得非常复杂，因为它们需要像动态数组一样管理trie节点。对于正确的数据集，级别压缩树可以是快速。从我记忆中来看，它们是存储IP路由表的第二快速方法，最快的是某种散列函数。

Answer 2

我没有看到你的方法有什么问题。如果您正在寻找一个高峰解决方案，可能在前三种情况下案例4采取的措施实际上是可行的，IE会找到k和k'的常见前缀，然后重新构建节点。如果碰巧密钥是相互关联的前缀，那么结果中的trie仍然是正确的，只有实现做了比实际更多的工作。但是再一次，没有任何代码看它很难说这是否适用于你的情况。

Answer 3

有点切线，但如果你超级担心你的Trie中的节点数量，你可能会考虑加入你的单词后缀。我会看看DAWG（定向非循环词图）的想法：http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

这些缺点是它们不是很动态，创建它们可能很困难。但是，如果你的字典是静态的，它们可以超级紧凑。

Answer 4

我对您的实施有疑问。您决定将字符串拆分为前缀树的粒度级别是多少？您可以将堆栈分割为s，t，a，c，k或st，ta，ac，ck和其他许多ngrams。大多数前缀树实现都考虑到该语言的字母表，基于这个字母表，您可以进行拆分。

如果你正在构建一个前缀树实施蟒那么你的字母会之类的东西闪避，：如果，否则...等

选择正确的字母，使构建高效的前缀树的巨大差异。至于你的答案，你可以在CPAN上查找使用trie的最长公共子字符串计算的PERL包。你可能会有一些运气，因为他们的大部分实现都非常强大。

Answer 5

看看：朱迪数组和python界面在http://www.dalkescientific.com/Python/PyJudy.html