pythontrie树实现字典排序

一般语言都提供了按字典排序的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__’: arr = [c for c in ‘python’] arr.sort() print arr

而且也可以使用我之前的一篇文章介绍的bitmap来实现:python: 实现bitmap数据结构 。实现代码如下:

代码如下:

#!/usr/bin/env python#coding: utf8

class bitmap(object): def __init__(self, max): self.size = self.calcelemindex(max, true) self.array = [0 for i in range(self.size)]

def calcelemindex(self, num, up=false): ”’up为true则为向上取整, 否则为向下取整”’ if up: return int((num + 31 – 1) / 31) #向上取整 return num / 31

def calcbitindex(self, num): return num % 31

def set(self, num): elemindex = self.calcelemindex(num) byteindex = self.calcbitindex(num) elem = self.array[elemindex] self.array[elemindex] = elem | (1

Posted in 未分类