Python Trie树实现字典排序
一般语言都提供了按字典排序的API,比如跟微信公众平台对接时就需要用到字典排序。按字典排序有很多种算法,最容易想到的就是字符串搜索的方式,但这种方式实现起来很麻烦,性能也不太好。Trie树是一种很常用的树结构,它被广泛用于各个方面,比如字符串检索、中文分词、求字符串最长公共前缀和字典排序等等,而且在输入法中也能看到Trie树的身影。 什么是Trie树 Trie树通常又称为字典树、单词查找树或前缀树,是一种用于快速检索的多叉树结构。如图数字的字典是一个10叉树: 同理小写英文字母或大写英文字母的字典数是一个26叉树。如上图可知,Trie树的根结点是不保存数据的,所有的数据都保存在它的孩子节点中。有字符串go,golang,php,python,perl,它这棵Trie树可如下图所示构造: 我们来分析下上面这张图。除了根节点外,每个子节点只存储一个字符。go和golang共享go前缀,php、perl和python只共用p前缀。为了实现字典排序,每一层节点上存储的字符都是按照字典排序的方式存储(这跟遍历的方式有关)。我们先来看看对单个字符如何进行字典排序。本文只考虑小写字母,其它方式类似。'a'在'b'的前面,而'a'的ASCII码小于'b'的ASCII码,因此通过它们的ASCII相减就可以得到字典顺序。而且python内置了字典排序的API,比如: 复制代码 代码如下: #!/usr/bin/env python #coding: utf8 if __name__ == '__main__': 而且也可以使用我之前的一篇文章介绍的bitmap来实现:Python: 实现bitmap数据结构 。实现代码如下: 复制代码 代码如下: #!/usr/bin/env python #coding: utf8 class Bitmap(object): def calcElemIndex(self, num, up=False): def calcBitIndex(self, num): def set(self, num): def clean(self, i): def test(self, i): if __name__ == '__main__': print '原始数组为: %s' % suffle_array bitmap的排序不能有重复字符。其实刚才所说的基于ASCII码相减的方式进行字典排序,已经有很多成熟算法了,比如插入排序、希尔排序、冒泡排序和堆排序等等。本文为了图简单,将使用Python自带的sorted方法来进行单字符的字典排序。如果读者自行实现单字符数组的排序也可以,而且这样将可以自定义字符串的排序方式。 实现思路 整个实现包括2个类:Trie类和Node类。Node类表示Trie树中的节点,由Trie类组织成一棵Trie树。我们先来看Node类: 复制代码 代码如下: #!/usr/bin/env python #coding: utf8 class Node(object): Node包含三个成员变量。c为每个节点上存储的字符。word表示一个完整的词,在本文中指的是一个字符串。childs包含这个节点的所有子节点。既然在每个节点中存储了c,那么存储word有什么用呢?并且这个word应该存在哪个节点上呢?还是用刚才的图举例子:比如go和golang,它们共用go前缀,如果是字符串搜索倒好办,因为会提供原始字符串,只要在这棵Trie树上按照路径搜索即可。但是对于排序来说,不会提供任何输入,所以无法知道单词的边界在哪里,而Node类中的word就是起到单词边界作用。具体是存储在单词的最后一个节点上,如图所示: 而Node类中的c成员如果这棵树不用于搜索,则可以不定义它,因为在排序中它不是必须的。 接下来我们看看Trie类的定义: 复制代码 代码如下: #!/usr/bin/env python #coding: utf8 '''Trie树实现字符串数组字典排序''' class Trie(object): def add(self, word): def preOrder(self, node): def find(self, node, c): def setWords(self, words): Trie包含1个成员变量和4个方法。root用于引用根结点,它不存储具体的数据,但是它拥有子节点。setWords方法用于初始化,调用add方法来初始化Trie树,这种调用是基于每个字符串的。add方法将每个字符添加到子节点,如果存在则共用它并寻找下一个子节点,依此类推。find是用于查找是否已经建立了存储某个字符的子节点,而preOrder是先序获取存储的word。树的遍历方式有三种:先序遍历、中序遍历和后序遍历,如果各位不太明白,可自行Google去了解。接下我们测试一下: 复制代码 代码如下: #!/usr/bin/env python #coding: utf8 '''Trie树实现字符串数组字典排序''' class Trie(object): def add(self, words): class Node(object): if __name__ == '__main__': 结束语 树的种类非常之多。在树结构的实现中,树的遍历是个难点,需要多加练习。上述代码写得比较仓促,没有进行任何优化,但在此基础上可以实现任何方式的字符串排序,以及字符串搜索等。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |