Python中的Trie (前缀树)

Question

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

如果有什么不清楚的话，我很乐意澄清。

我刚刚在python中实现了一个特瑞。然而，有一点似乎比它应该更复杂(作为一个热爱简单的人)。也许有人也有类似的问题？

我的目标是通过在根中存储子trie的最大公共前缀来最小化节点的数量。例如，如果我们有单词stackoverflow，stackbase和基于堆栈的，那么树的外观如下所示：

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

请注意，仍然可以想到有一个字符的边(子节点的第一个)。

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

我的想法是依次插入密钥(从一个空的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

乍一看，听起来您已经实现了一个帕特里夏。这种方法在一些文献中也被称为路径压缩。应该有非ACM付费墙后面的文件的副本，这将包括一个插入算法。

还有另一种压缩方法，您可能需要查看:级别压缩。路径压缩的思想是将单个子节点的字符串替换为具有“跳过”计数的单个超级节点。水平压缩背后的想法是用一个超级节点替换满或几乎满的子树，并使用一个“度”计数来表示该节点解码的密钥的数字数。还有第三种叫做宽度压缩的方法，但恐怕我的内存不足了，我无法通过快速的googling找到它的描述。

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

Answer 2

我看不出你的做法有什么问题。如果您正在寻找一个尖峰解决方案，也许在案例4中所采取的操作对于前三种情况来说实际上是可行的，IE将找到k和k'的通用前缀，并考虑到这一点重新构建节点。如果键是另一个键的前缀，则生成的trie仍然是正确的，只有实现做的工作比实际要做的要多一点。但是，如果没有任何代码来查看，很难判断这在您的情况下是否有效。

Answer 3

有点切线，但是如果您非常担心Trie中的节点数，您也可以考虑加入单词后缀。我想看看DAWG (有向无圈字图)的想法：图表

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