logo标签列表

Python中的Trie（前缀树）

pythonalgorithmtrie
18

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

如果有任何不清楚的地方，我非常乐意澄清。

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

我的目标是通过在其根节点中存储子Trie的最大公共前缀来最小化节点数量。例如，如果我们有单词stackoverflow，stackbase和stackbased，那么树的外观将类似于此：

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

请注意，仍然可以将边缘视为一个字符（子节点的第一个字符）。
“查找”查询很容易实现。插入不难，但比我想象的要复杂一些.. :(
我的想法是一个接一个地插入键（从空字典开始），首先搜索要插入的键k（Find(k)），然后在查找过程停止的位置本地重新排列/拆分节点。结果有4种情况： （设k是我们要插入的键，k'是搜索结束的节点的键）
1. k与k'相同 2. k是k'的“适当”前缀 3. k'是k的“适当”前缀 4. k和k'共享一些公共前缀，但没有出现（1），（2）或（3）中的任何一种情况。
似乎每种情况都是独特的，因此意味着对Trie的不同修改。但是：真的那么复杂吗？我错过了什么吗？有更好的方法吗？
谢谢 :)
5个回答
19
一眼看上去，你似乎已经实现了Patricia Trie。这种方法在一些文献中也被称为路径压缩。那篇论文应该有副本不在ACM的付费墙后面，其中会包括插入算法。
还有另一种压缩方法值得你去了解：层压缩。路径压缩的思想是用一个“跳过”计数的超级节点来替换单个子节点字符串。而层压缩的思想是用一个“度数”计数的超级节点来替换完整或近乎完整的子树，它表示节点解码的键位数。还有第三种方法叫做宽度压缩，但我记忆模糊，无法通过快速搜索找到其描述。
层压缩可以大大缩短平均路径长度，但插入和删除算法变得非常复杂，因为它们需要像动态数组一样管理trie节点。对于正确的数据集，层压缩树可以快速处理。据我所知，它们是存储IP路由表的第二快速方法，最快的是某种哈希trie。
4
国家标准与技术研究所网站上有一些Patricia树的实现（http://www.itl.nist.gov/div897/sqg/dads/HTML/patriciatree.html）。 - Kathy Van Stone
感谢Jason的推荐和建议！当数据变得密集时，哈希可能也是一种不错的技术。但是考虑到插入操作，我们还是保持简单吧 :) - jacob
2
我认为你的方法没有问题。如果你正在寻找一个快速解决方案，也许第四种情况中采取的行动实际上适用于前三种情况，即查找k和k'的公共前缀，并以此为依据重建节点。如果这两个键是彼此的前缀，那么得到的Trie仍然是正确的，只是实现过程比必要的工作多了一些。但是，没有代码可以查看，很难确定这在你的情况下是否可行。
感谢您的快速回复。第四种情况是，如果我们将“stackbattle”插入其中，我们必须创建一个新节点“ba”，并将一个新节点“ttle”放在左侧，以及旧的子树根据“base”（现在重命名为“se”）放在右侧。据我所知，情况1-3在本质上是不同的。（在这些情况下，从不需要创建2个新节点。） - jacob
2
有点离题，但如果您非常担心Trie中节点的数量，可以考虑将单词后缀合并。我建议看一下DAWG（有向无环图）的想法：http://en.wikipedia.org/wiki/Directed_acyclic_word_graph。
这些的缺点是它们不太动态，创建它们可能很困难。但是，如果您的字典是静态的，它们可以非常紧凑。
2
关于您的实现，我有一个问题。您决定将字符串拆分成什么级别以制作前缀树？您可以将stack拆分为s，t，a，c，k或st，ta，ac，ck和其他许多ngram。大多数前缀树的实现都考虑到了语言的字母表，基于此字母表进行拆分。
如果您要为Python构建前缀树实现，则其中的字母表将是def，：，if，else等等。
选择正确的字母表在构建高效前缀树方面起着巨大的作用。至于您的答案，您可以在CPAN上寻找使用trie计算最长公共子串的PERL程序包。那里有一些运行良好的实现，您可能会有所收获。
我没有使用固定的字母表，以允许所有字符串。我使用哈希表来确定链接是否已经存在。 - jacob
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接