Python Trie树实现字典排序__self_python_Trie_num_calcElemIndex_

当前位置: 编程技术>python

Python Trie树实现字典排序

来源: 互联网发布时间：2014-10-04

本文导语: 一般语言都提供了按字典排序的API，比如跟微信公众平台对接时就需要用到字典排序。按字典排序有很多种算法，最容易想到的就是字符串搜索的方式，但这种方式实现起来很麻烦，性能也不太好。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__':
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