我不知道这是不是问问算法的地方。但让我们看看,如果我得到任何答案... :)Python中的Trie(前缀树)
如果有什么不清楚我很高兴澄清事情。
我刚刚在python中实现了一个Trie。然而,有一点似乎比它应该更复杂(就像一个热爱简单的人)。也许有人有类似的问题?
我的目标是通过在其根中存储子树的最大公共前缀来最小化节点数。例如,如果我们有话计算器,stackbase和stackbased,则树会是这个样子:
[s]tack
[o]verflow ______/ \_______ [b]ase
\___ [d]
注意,仍然可以认为有一个字符边缘(在第一个孩子节点)。
查找 - 查询很容易实现。 插入并不难,但有些较复杂的比我想.. :(
我的想法是插入后,其他的按键一个(从空开始特里),通过为将要优先搜索(k)(查找(k)),然后在查找过程停止的地方对节点进行本地重新排列/分割,结果为4种情况:设k是我们想要插入的密钥和k '是节点,在此处搜索结束)的关键
- k是相同的k'
- k是一个“适当的”前缀k'
- k'是k的“适当”前缀k和k'共享一些共同的前缀,但情况(1),(2)或3)发生。
似乎每个案例都是独一无二的,因此意味着Trie的不同修改。但是:这真的很复杂吗?我错过了什么吗?有更好的方法吗?
谢谢:)
在国家标准与技术研究院网站上有一些Patricia尝试实现(http://www.itl.nist.gov/div897/sqg/dads /HTML/patriciatree.html) – 2009-06-07 02:19:11
感谢Jason的参考和建议!哈希也可能是一个很好的技术,当它变得密集时。但让我们保持简单的插入:) – jacob 2009-06-07 03:01:53
感谢凯西的链接。 – jacob 2009-06-07 03:02:12