设为首页 收藏本站
查看: 777|回复: 0

[经验分享] Trie数的Python实现代码

[复制链接]

尚未签到

发表于 2017-4-29 14:55:45 | 显示全部楼层 |阅读模式
  关于Trie树的原理这里不做介绍,网上相关的资料非常多,可以参考July的文章:http://blog.csdn.net/v_july_v/article/details/6897097。不过Trie确实是非常的强大,原理不复杂,使用起来也非常的方便。代码实现其实也不难,如果用C++实现的话需要自己定义数据结构(结构体)来构建树,这里我介绍怎样用Python实现,用Python实现起来尤为的方便,不用自己定义数据结构,用Python的dictionary类型即可。说一句题外话:我发现自从学会用Python以后就爱不释手,确实是使用起来非常方便。言归正传,看看Python实现的简易Trie树,为什么说是简易呢?因为没有实现复杂的功能,只是为了说明Trie的基本原理,而且只支持ascii字符。实现了以下几项基本功能:
  1、添加单词:LBTrie的add方法;
  2、查找单词:LBTrie的search方法;
  3、打印Trie树:LBTrie的output方法。
  

class LBTrie:
"""
simple implemention of Trie in Python by authon liubing, which is not
perfect but just to illustrate the basis and principle of Trie.
"""
def __init__(self):
self.trie = {}
self.size = 0
#添加单词
def add(self, word):
p = self.trie
word = word.strip()
for c in word:
if not c in p:
p[c] = {}
p = p[c]
if word != '':
#在单词末尾处添加键值''作为标记,即只要某个字符的字典中含有''键即为单词结尾
p[''] = ''
#查询单词      
def search(self, word):
p = self.trie
word = word.lstrip()
for c in word:
if not c in p:
return False
p = p[c]
#判断单词结束标记''
if '' in p:
return True
return False         
#打印Trie树的接口
def output(self):
print '{'
self.__print_item(self.trie)   
print '}'
#实现Trie树打印的私有递归函数,indent控制缩进
def __print_item(self, p, indent=0):     
if p:
ind = '' + '\t' * indent
for key in p.keys():
label = "'%s' : " % key
print ind + label + '{'
self.__print_item(p[key], indent+1)
print ind + ' '*len(label) + '}'  
if __name__ == '__main__':
trie_obj = LBTrie()
#添加单词
trie_obj.add('hello')
trie_obj.add('help')
trie_obj.add('world')
trie_obj.add('abc')
#打印构建的Trie树
trie_obj.output()
#查找单词     
if trie_obj.search('hello'):
print 'Yes'
else:
print 'No'
if trie_obj.search('China'):
print 'Yes'
else:
print 'No'
  打印的Trie树如下图所示:
DSC0000.jpg

  查找输出结果为:
  Yes
  No

运维网声明 1、欢迎大家加入本站运维交流群:群②:261659950 群⑤:202807635 群⑦870801961 群⑧679858003
2、本站所有主题由该帖子作者发表,该帖子作者与运维网享有帖子相关版权
3、所有作品的著作权均归原作者享有,请您和我们一样尊重他人的著作权等合法权益。如果您对作品感到满意,请购买正版
4、禁止制作、复制、发布和传播具有反动、淫秽、色情、暴力、凶杀等内容的信息,一经发现立即删除。若您因此触犯法律,一切后果自负,我们对此不承担任何责任
5、所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其内容的准确性、可靠性、正当性、安全性、合法性等负责,亦不承担任何法律责任
6、所有作品仅供您个人学习、研究或欣赏,不得用于商业或者其他用途,否则,一切后果均由您自己承担,我们对此不承担任何法律责任
7、如涉及侵犯版权等问题,请您及时通知我们,我们将立即采取措施予以解决
8、联系人Email:admin@iyunv.com 网址:www.yunweiku.com

所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其承担任何法律责任,如涉及侵犯版权等问题,请您及时通知我们,我们将立即处理,联系人Email:kefu@iyunv.com,QQ:1061981298 本贴地址:https://www.yunweiku.com/thread-370902-1-1.html 上篇帖子: 《简明python教程》总结(三)-- 函数、模块 下篇帖子: 『Emacs 』发现python-mode文档注释一个Bug
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

扫码加入运维网微信交流群X

扫码加入运维网微信交流群

扫描二维码加入运维网微信交流群,最新一手资源尽在官方微信交流群!快快加入我们吧...

扫描微信二维码查看详情

客服E-mail:kefu@iyunv.com 客服QQ:1061981298


QQ群⑦:运维网交流群⑦ QQ群⑧:运维网交流群⑧ k8s群:运维网kubernetes交流群


提醒:禁止发布任何违反国家法律、法规的言论与图片等内容;本站内容均来自个人观点与网络等信息,非本站认同之观点.


本站大部分资源是网友从网上搜集分享而来,其版权均归原作者及其网站所有,我们尊重他人的合法权益,如有内容侵犯您的合法权益,请及时与我们联系进行核实删除!



合作伙伴: 青云cloud

快速回复 返回顶部 返回列表