文档章节

Python: Trie树实现字典排序

陈亦
 陈亦
发布于 2014/02/18 06:15
字数 2198
阅读 4567
收藏 30

一般语言都提供了按字典排序的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

$ python trie.py
['h', 'n', 'o', 'p', 't', 'y']

而且也可以使用我之前的一篇文章介绍的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 << byteIndex)

	def clean(self, i):
		elemIndex = self.calcElemIndex(i)
		byteIndex = self.calcBitIndex(i)
		elem      = self.array[elemIndex]
		self.array[elemIndex] = elem & (~(1 << byteIndex))

	def test(self, i):
		elemIndex = self.calcElemIndex(i)
		byteIndex = self.calcBitIndex(i)
		if self.array[elemIndex] & (1 << byteIndex):
			return True
		return False

if __name__ == '__main__':
	MAX = ord('z')
	suffle_array = [c for c in 'python']
	result       = []
	bitmap = Bitmap(MAX)
	for c in suffle_array:
		bitmap.set(ord(c))
	
	for i in range(MAX + 1):
		if bitmap.test(i):
			result.append(chr(i))

	print '原始数组为:    %s' % suffle_array
	print '排序后的数组为: %s' % result

$ python trie.py
原始数组为:    ['p', 'y', 't', 'h', 'o', 'n']
排序后的数组为: ['h', 'n', 'o', 'p', 't', 'y']

bitmap的排序不能有重复字符。其实刚才所说的基于ASCII码相减的方式进行字典排序,已经有很多成熟算法了,比如插入排序、希尔排序、冒泡排序和堆排序等等。本文为了图简单,将使用Python自带的sorted方法来进行单字符的字典排序。如果读者自行实现单字符数组的排序也可以,而且这样将可以自定义字符串的排序方式。

实现思路

整个实现包括2个类:Trie类和Node类。Node类表示Trie树中的节点,由Trie类组织成一棵Trie树。我们先来看Node类:

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

class Node(object):
	def __init__(self, c=None, word=None):
		self.c          = c    # 节点存储的单个字符
		self.word       = word # 节点存储的词
		self.childs     = []   # 此节点的子节点

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 __init__(self):
		self.root  = Node() # Trie树root节点引用

	def add(self, word):
		'''添加字符串'''
		node = self.root
		for c in word:
			pos = self.find(node, c)
			if pos < 0:
				node.childs.append(Node(c))
				#为了图简单,这里直接使用Python内置的sorted来排序
				#pos有问题,因为sort之后的pos会变掉,所以需要再次find来获取真实的pos
				#自定义单字符数组的排序方式可以实现任意规则的字符串数组的排序
				node.childs = sorted(node.childs, key=lambda child: child.c)
				pos = self.find(node, c)
			node = node.childs[pos]
		node.word = word

	def preOrder(self, node):
		'''先序输出'''
		results = []
		if node.word:
			results.append(node.word)
		for child in node.childs:
			results.extend(self.preOrder(child))
		return results

	def find(self, node, c):
		'''查找字符插入的位置'''
		childs = node.childs
		_len   = len(childs)
		if _len == 0:
			return -1
		for i in range(_len):
			if childs[i].c == c:
				return i
		return -1

	def setWords(self, words):
		for word in words:
			self.add(word)

Trie包含1个成员变量和4个方法。root用于引用根结点,它不存储具体的数据,但是它拥有子节点。setWords方法用于初始化,调用add方法来初始化Trie树,这种调用是基于每个字符串的。add方法将每个字符添加到子节点,如果存在则共用它并寻找下一个子节点,依此类推。find是用于查找是否已经建立了存储某个字符的子节点,而preOrder是先序获取存储的word。树的遍历方式有三种:先序遍历、中序遍历和后序遍历,如果各位不太明白,可自行Google去了解。接下我们测试一下:

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

'''Trie树实现字符串数组字典排序'''

class Trie(object):
	def __init__(self):
		self.root  = Node() # Trie树root节点引用

	def add(self, word):
		'''添加字符串'''
		node = self.root
		for c in word:
			pos = self.find(node, c)
			if pos < 0:
				node.childs.append(Node(c))
				#为了图简单,这里直接使用Python内置的sorted来排序
				#pos有问题,因为sort之后的pos会变掉,所以需要再次find来获取真实的pos
				#自定义单字符数组的排序方式可以实现任意规则的字符串数组的排序
				node.childs = sorted(node.childs, key=lambda child: child.c)
				pos = self.find(node, c)
			node = node.childs[pos]
		node.word = word

	def preOrder(self, node):
		'''先序输出'''
		results = []
		if node.word:
			results.append(node.word)
		for child in node.childs:
			results.extend(self.preOrder(child))
		return results

	def find(self, node, c):
		'''查找字符插入的位置'''
		childs = node.childs
		_len   = len(childs)
		if _len == 0:
			return -1
		for i in range(_len):
			if childs[i].c == c:
				return i
		return -1

	def setWords(self, words):
		for word in words:
			self.add(word)

class Node(object):
	def __init__(self, c=None, word=None):
		self.c          = c    # 节点存储的单个字符
		self.word       = word # 节点存储的词
		self.childs     = []   # 此节点的子节点

if __name__ == '__main__':
	words = ['python', 'function', 'php', 'food', 'kiss', 'perl', 'goal', 'go', 'golang', 'easy']
	trie = Trie()
	trie.setWords(words)
	result = trie.preOrder(trie.root)
	print '原始字符串数组:     %s' % words
	print 'Trie树排序后:       %s' % result
	words.sort()
	print 'Python的sort排序后: %s' % words

$ python trie.py
原始字符串数组:     ['python', 'function', 'php', 'food', 'kiss', 'perl', 'goal', 'go', 'golang', 'easy']
Trie树排序后:       ['easy', 'food', 'function', 'go', 'goal', 'golang', 'kiss', 'perl', 'php', 'python']
Python的sort排序后: ['easy', 'food', 'function', 'go', 'goal', 'golang', 'kiss', 'perl', 'php', 'python']

结束语

树的种类非常之多。在树结构的实现中,树的遍历是个难点,需要多加练习。上述代码写得比较仓促,没有进行任何优化,但在此基础上可以实现任何方式的字符串排序,以及字符串搜索等。

© 著作权归作者所有

陈亦
粉丝 241
博文 23
码字总数 53194
作品 0
浦东
高级程序员
私信 提问
加载中

评论(4)

陈亦
陈亦 博主

引用来自“magicoding”的评论

child 的复数形式其实是 children 哦~

是的,我一般在程序中将复数写成List后缀或加s的形式
magicoding
magicoding
child 的复数形式其实是 children 哦~
陈亦
陈亦 博主

引用来自“美好的2014”的评论

好!楼主我还看过一个Rope算法,也是字符串类算法。

Rope算法太复杂了27
优雅先生
优雅先生
好!楼主我还看过一个Rope算法,也是字符串类算法。
JavaScript: 实现简单的中文分词

中文分词在大数据横行的今天是越来越有用武之地了。它不仅被广泛用于专业的中文搜索引擎中,而且在关键词屏蔽、黑白名单以及文本相似度等方面也能大显身手。中文分词最简单也最常用的方式是基...

陈亦
2014/02/21
4.4K
2
LeetCode 208. Implement Trie (Prefix Tree) (实现Trie树)

原题 Implement a trie with , , and methods. Example: Note: You may assume that all inputs are consist of lowercase letters . All inputs are guaranteed to be non-empty strings. R......

dby_freedom
2018/12/03
0
0
算法 | 动画+解析,轻松理解「Trie树」

Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。 此外 Trie 树也称前缀树(因为某节点...

AI科技大本营
01/06
0
0
分词,难在哪里?科普+解决方案!

题图:by Lucas Davies 一、前言 分词,我想是大多数大前端开发人员,都不会接触到的一个概念。这个不影响我们了解它,毕竟我们要多方向发展。今天就来简单介绍一些分词,我尽量用简介的语言...

承香墨影
2018/10/29
0
0
Trie 树实现与应用

Trie树 基本概念  Trie树又称字典树,它是用来查询字符串的一种数据结构。它每一个节点都有26个子节点,所以是26叉树。优点查询字符串的时候速度快,缺点浪费大量空间。  当一个字符串长为...

sdoyuxuan
2018/01/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

rime设置为默认简体

转载 https://github.com/ModerRAS/ModerRAS.github.io/blob/master/_posts/2018-11-07-rime%E8%AE%BE%E7%BD%AE%E4%B8%BA%E9%BB%98%E8%AE%A4%E7%AE%80%E4%BD%93.md 写在开始 我的Arch Linux上......

zhenruyan
今天
5
0
简述TCP的流量控制与拥塞控制

1. TCP流量控制 流量控制就是让发送方的发送速率不要太快,要让接收方来的及接收。 原理是通过确认报文中窗口字段来控制发送方的发送速率,发送方的发送窗口大小不能超过接收方给出窗口大小。...

鏡花水月
今天
10
0
OSChina 周日乱弹 —— 别问,问就是没空

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享容祖儿/彭羚的单曲《心淡》: 《心淡》- 容祖儿/彭羚 手机党少年们想听歌,请使劲儿戳(这里) @wqp0010 :周...

小小编辑
今天
1K
11
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

非正式解决方案
今天
5
0
Spring Context 你真的懂了吗

今天介绍一下大家常见的一个单词 context 应该怎么去理解,正确的理解它有助于我们学习 spring 以及计算机系统中的其他知识。 1. context 是什么 我们经常在编程中见到 context 这个单词,当...

Java知其所以然
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部