数据结构-哈夫曼树(python实现)
数据结构-哈夫曼树(python实现)
好,前面我们介绍了一般二叉树、完全二叉树、满二叉树,这篇文章呢,我们要介绍的是哈夫曼树。
哈夫曼树也叫最优二叉树,与哈夫曼树相关的概念还有哈夫曼编码,这两者其实是相同的。哈夫曼编码是哈夫曼在1952年提出的。现在哈夫曼编码多应用在文本压缩方面。接下来,我们就来介绍哈夫曼树到底是个什么东西?哈夫曼编码又是什么,以及它如何应用于文本压缩。
哈夫曼树(Huffman Tree)
给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
首先,我们有这样一些数据:
sourceData = [('a', 8), ('b', 5), ('c', 3), ('d', 3), ('e', 8), ('f', 6), ('g', 2), ('h', 5), ('i', 9), ('j', 5), ('k', 7), ('l', 5), ('m', 10), ('n', 9)]
每一个数据项是一个元组,元组的第一项是数据内容,第二项是该数据的权重。也就是说,用于构建哈夫曼树的数据是带权重的。假设这些数据里面的字母a-n的权重是根据这些字母在y一个文本出出现的概率计算得出的,字母出现的概率越高,则该字母的权重越大。例如字母 a 的权重为 8 .
好,拿到数据我们就可以来构建哈夫曼树了。
首先,找出所有元素中权重最小的两个元素,即g(2)和c(3),
以g和c为子节点构建二叉树,则构建的二叉树的父节点的权重为 2+3 = 5.
从除g和c以外剩下的元素和新构建的权重为5的节点中选出权重最小的两个节点,
进行第 2 步操作。
以此类推,直至最后合成一个二叉树就是哈夫曼树。
我们用图例来表示一下:
好,这里我们的哈夫曼树就构建好了,节点中字母后面的数字表示该字母的权重,就是前面给定的数据。在这里我要强调的是,同样的数据创建的哈夫曼树并不是唯一的,所以只要按照规则一步一步没有出错,你的哈夫曼树就是正确的。
我们现在将访问左节点定义为0,访问右节点定义为1.则我们现在访问字母a,则它的编码为0110,访问字母n的编码为111,这个编码就是哈夫曼编码。
通过比对不同字母的哈夫曼编码,你发现了什么?
权重越大的字母对应的哈夫曼编码越短,权重越小的字母对应的哈夫曼编码则越长。也就是说文本中出现概率大的字母编码短,出现概率小的字母编码长。通过这种编码方式来表示文本中的字母,那所得整个文本的编码长度也会缩短。
这就是哈夫曼树也就是哈夫曼编码在文本压缩中的应用。
下面我们用代码来实现:
定义一个二叉树类:
class BinaryTree:
def __init__(self, data, weight): self.data = data self.weight = weight self.left = None self.right = None
获取节点列表中权重最小的两个节点:
定义获取列表中权重最大的两个节点的方法:
def min2(li):
result = [BinaryTree(None, float('inf')), BinaryTree(None, float('inf'))] li2 = [] for i in range(len(li)): if li[i].weight < result[0].weight: if result[1].weight != float('inf'): li2.append(result[1]) result[0], result[1] = li[i], result[0] elif li[i].weight < result[1].weight: if result[1].weight != float('inf'): li2.append(result[1]) result[1] = li[i] else: li2.append(li[i]) return result, li2
定义生成哈夫曼树的方法:
def makeHuffman(source):
m2, data = min2(source) print(m2[0].data, m2[1].data) left = m2[0] right = m2[1] sumLR = left.weight + right.weight father = BinaryTree(None, sumLR) father.left = left father.right = right if data == []: return father data.append(father) return makeHuffman(data)
定义广度优先遍历方法:
递归方式实现广度优先遍历
def breadthFirst(gen, index=0, nextGen=[], result=[]):
if type(gen) == BinaryTree: gen = [gen] result.append((gen[index].data, gen[index].weight)) if gen[index].left != None: nextGen.append(gen[index].left) if gen[index].right != None: nextGen.append(gen[index].right) if index == len(gen)-1: if nextGen == []: return else: gen = nextGen nextGen = [] index = 0 else: index += 1 breadthFirst(gen, index, nextGen,result) return result
输入数据:
某篇文章中部分字母根据出现的概率规定权重
sourceData = [('a', 8), ('b', 5), ('c', 3), ('d', 3), ('e', 8), ('f', 6), ('g', 2), ('h', 5), ('i', 9), ('j', 5), ('k', 7), ('l', 5), ('m', 10), ('n', 9)]
sourceData = [BinaryTree(x[0], x[1]) for x in sourceData]
创建哈夫曼树并进行广度优先遍历:
huffman = makeHuffman(sourceData)
print(breadthFirst(huffman))
OK ,我们的哈夫曼树就介绍到这里了,你还有什么不懂的问题记得留言给我哦。
原文地址https://www.cnblogs.com/dongyangblog/p/11228930.html
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Java版Spring Cloud B2B2C o2o社交电商-客户端负载均衡策略
一、负载均衡介绍 负载均衡(Load Balance):建立在现有网络结构之上,它提供了一种廉价有效透明的方法扩展网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性。其意思就是分摊到多个操作单元上进行执行,例如Web服务器、FTP服务器、企业关键应用服务器和其它关键任务服务器等,从而共同完成工作任务。 1、服务端负载均衡:客户端请求到负载均衡服务器,负载均衡服务器根据自身的算法将该请求转给某台真正提供业务的服务器,该服务器将响应数据给负载均衡服务器,负载均衡服务器最后将数据返回给客服端。(nginx) 2、客服端负载均衡:基于客户端的负载均衡,简单的说就是在客户端程序里面,自己设定一个调度算法,在向服务器发起请求的时候,先执行调度算法计算出向哪台服务器发起请求,然后再发起请求给服务器。 二、负载均衡策略介绍 (1) AbstractLoadBalancerRule AbstractLoadBalancerRule是一个抽象类,里边主要定义了一个ILoadBalancer,定义它的目的主要是辅助负责均衡策略选取合适的服务端实例。 (2) RandomRul...
- 下一篇
Java版Spring Cloud B2B2C o2o社交电商-Hystrix的缓存使用
一介绍 在高并发的场景之下,Hystrix中提供了请求缓存的功能,可以方便地开启和使用请求缓存来优化系统,达到减轻高并发时请求线程的消耗、降低请求响应时间的效果。 二开启请求缓存功能 在实现HystrixCommand或HystrixObservableCommand时,通过重载getCacheKey()方法来开启请求缓存。 例如: public class CommandUsingRequestCache extends HystrixCommand<Boolean> { private final int value; protected CommandUsingRequestCache(int value) { super(HystrixCommandGroupKey.Factory.asKey("ExampleGroup")); this.value = value; } @Override protected Boolean run() { return value == 0 || value % 2 == 0; } //通过getCacheKey方法中返回的请求...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- CentOS8安装Docker,最新的服务器搭配容器使用
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- 设置Eclipse缩进为4个空格,增强代码规范
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS8编译安装MySQL8.0.19
- SpringBoot2整合Redis,开启缓存,提高访问速度
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Hadoop3单机部署,实现最简伪集群