Python中的Trie（前缀树）
我不知道这里是不是问算法的地方。不过我还是试试能不能得到一些答案... :)
如果有什么不清楚的地方，我很乐意进一步解释。
我刚刚在Python中实现了一个Trie（字典树）。不过，有一点似乎比我想象的要复杂（因为我喜欢简单）。也许有人遇到过类似的问题？
我的目标是通过把子字典树中最大的公共前缀存储在它的根节点上，来尽量减少节点的数量。例如，如果我们有stackoverflow、stackbase和stackbased这几个词，那么树的结构大概是这样的：
[s]tack
[o]verflow ______/ \_______ [b]ase
\___ [d]
注意，边缘可以看作是一个字符（也就是子节点的第一个字符）。
查找操作实现起来很简单。插入操作虽然不难，但比我想要的要复杂一些.. :(
我的想法是一个一个地插入这些键（从一个空的字典树开始），首先查找要插入的键k（查找(k)），然后在查找停止的地方局部调整/拆分节点。结果发现有四种情况： （设k是我们想插入的键，k'是查找结束时的节点键）
- k和k'完全相同
- k是k'的“真”前缀
- k'是k的“真”前缀
- k和k'有一些公共前缀，但不属于情况（1）、（2）或（3）。
似乎每种情况都是独特的，因此需要对Trie进行不同的修改。但是：这真的那么复杂吗？我是不是漏掉了什么？有没有更好的方法？
谢谢 :)
5 个回答
我有个关于你实现的疑问。你是如何决定把字符串拆分成多小的部分来构建前缀树的？比如说，你可以把“stack”拆分成s、t、a、c、k，或者拆分成st、ta、ac、ck，还有很多其他的组合。大多数前缀树的实现会考虑到语言的字母表，根据这个字母表来进行拆分。
如果你要为Python构建一个前缀树，那么你的字母表可能会包括像def、:、if、else等等。
选择合适的字母表在构建高效的前缀树时非常重要。至于你的问题，你可以在CPAN上寻找PERL的包，这些包使用前缀树来计算最长公共子串。你可能会有好运，因为他们的实现通常都很强大。
有点偏题，不过如果你非常担心你的Trie树中的节点数量，可以考虑把单词的后缀也合并起来。我建议你看看DAWG（有向无环单词图）的概念：http://en.wikipedia.org/wiki/Directed_acyclic_word_graph
不过这些结构的缺点是它们不太灵活，创建起来可能比较困难。但是，如果你的字典是静态的（也就是说不经常变化），它们可以非常紧凑。
一看就知道，你实现的可能是一个叫做Patricia Trie的结构。这种方法在一些文献中也被称为路径压缩。应该有一些不需要付费就能看到的论文副本，其中会包含插入算法的内容。
另外，还有一种压缩方法你可以了解一下：层级压缩。路径压缩的想法是把一串只有一个子节点的字符串替换成一个超级节点，并且这个节点有一个“跳过”计数。而层级压缩的想法是把完整或几乎完整的子树替换成一个超级节点，这个节点有一个“度”计数，表示这个节点解码了多少位的键。还有一种叫做宽度压缩的方法，但我记不清具体内容了，快速搜索也没找到相关描述。
层级压缩可以大大缩短平均路径，但插入和删除的算法会变得相当复杂，因为它们需要像动态数组一样管理这些节点。对于合适的数据集，层级压缩的树可以非常快。我记得它们是存储IP路由表的第二快的方法，最快的则是某种哈希树。