文档章节

霍夫曼编码

如比如比
 如比如比
发布于 2015/10/21 05:43
字数 613
阅读 166
收藏 7

哈夫曼树(Huffman Tree)

 

路径:若一棵树中存在一个结点序列k1,k2,…,kj,使得ki是ki+1的双亲(1≤i<j),则称此结点序列是从k1到kj 的路径。

路径长度(Path Length):两个结点之间的路径长度 PL是连接两结点的路径上的分支数。树的路径长度是各叶结点到根结点的路径长度之和。

带权路径长度(Weighted Path Length, WPL)

树的带权路径长度是树的各叶结点所带的权值与该结点到根的路径长度的乘积的和。

 

霍夫曼树(最优二叉树)

 

带权路径长度达到最小的二叉树即为霍夫曼树。在霍夫曼树中,权值大的结点离根最近。

 

霍夫曼算法

 

(1)由给定的n个权值 {w0, w1, w2, …, wn-1},构造具有 n棵二叉树的森林 F = { T0, T1, T2, …, Tn-1},其中每棵二叉树 Ti 只有一 个带权值 wi 的根结点, 其左、右子树均为空。

(2)重复以下步骤, 直到 F中仅剩下一棵树为止:

①在F 中选取两棵根结点的权值最小的二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

② 在F中删去这两棵二叉树。

③ 把新的二叉树加入F。

 

霍夫曼编码 主要用途是实现数据压缩。

设给出一段报文:CASTCASTSATATATASA

字符集合是 { C, A, S, T },各个字符出现的频度(次数)是 W={ 2, 7, 4, 5 }。

若给每个字符以等长编码A : 00T : 10C : 01S : 11

则总编码长度为( 2+7+4+5 ) * 2 = 36

若按各个字符出现的概率不同而给予不等长编码,可望减少总编码长度。

各字符出现概率为{ 2/18, 7/18, 4/18, 5/18},化整为{ 2, 7, 4, 5 }.

以它们为各叶结点上的权值, 建立霍夫曼树。左分支赋0,右分支赋1,得霍夫曼编码(变长编码)。A : 0T : 10C : 110S : 111

它的总编码长度:7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。

总编码长度正好等于霍夫曼树的带权路径长度WPL。霍夫曼编码是一种无前缀编码。解码时不会混淆。

 

© 著作权归作者所有

上一篇: Java处理Zip文件
下一篇: ZIP文件格式详解
如比如比
粉丝 126
博文 178
码字总数 286951
作品 0
日本
程序员
私信 提问
深入学习二叉树(三) 霍夫曼树

1 前言 霍夫曼树是二叉树的一种特殊形式,又称为最优二叉树,其主要作用在于数据压缩和编码长度的优化。 2 重要概念 2.1 路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点...

进击的Hello_World
2018/05/05
0
0
数据压缩算法----游程编码和霍夫曼编码

游程编码 定义: 用一个 符号值/串 代替具有相同值的连续符号(连续符号构成了一段连续的“游程”。游程编码因此而得名),使符号长度少于原始数据的长度。 应用场景: 游程编码经典应用场景...

SuperHeroes
2018/01/28
369
0
【工具使用系列】关于 MATLAB 图像编码 & 图像压缩,你需要知道的事情

如何进行图像压缩 图像压缩 统计编码 行程编码 霍夫曼编码 预测编码 预测编码 视频压缩 图像序列和电影 时间冗余和运动补偿 什么是图像压缩 图像编码概述 图像压缩编码的必要性和可能性 图像...

AllenMoore
2018/01/27
53
0
数据压缩----霍夫曼树和霍夫曼压缩

霍夫曼压缩的思想: 使用较少的比特表示出现频繁的字符而使用较多的比特表示使用较少的字符。这样表示字符串所使用的总比特数就会减少。 前提:所有字符编码都不会成为其他字符编码的前缀。使...

SuperHeroes
2018/01/28
0
0
霍夫曼编码摘录(Huffman coding)

在计算机资料处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之...

jdflyfly
2014/04/13
179
0

没有更多内容

加载失败,请刷新页面

加载更多

谁说多功能和低价格不能兼得?Aspose系列产品1024购买指南请查收!

你还在为了Word、Excel、PDF、CAD等文档格式转换而发愁吗? 你是否在寻找一款能够在应用程序中文档管理的工具呢? Aspose——支持100多种文件格式创建、编辑、转换和打印! 往下看,找一找哪...

mnrssj
19分钟前
3
0
hbase客户端API

本章介绍用于对HBase表上执行CRUD操作的HBase Java客户端API。 HBase是用Java编写的,并具有Java原生API。因此,它提供了编程访问数据操纵语言(DML)。 HBaseConfiguration类 添加 HBase 的配...

水木星辰
19分钟前
3
0
[插件化开发] 1. 初识OSGI

初识 OSGI 背景 当前product是以solution的方式进行售卖,但是随着公司业务规模的快速夸张,随之而来的是新客户的产品开发,老客户的产品维护,升级以及修改bug,团队的效能明显下降,为了解...

IsaacZhang
20分钟前
4
0
Webstorm 环境使用 nuxt.js 做开发,@ 和 ~ 别名配置

好的IDE + 好的代码提示 = 高效率的开发 webstorm 设置@和~别名,有助于代码查看和跳转. step 0 在项目下创建一个webpack.config.js,内容如下: const path = require('path')module.exp...

皇虫
24分钟前
3
0
Knative 实战:基于 Knative Serverless 技术实现天气服务-下篇

上一期我们介绍了如何基于 Knative Serverless 技术实现天气服务-上篇,首先我们先来回顾一下上篇介绍的内容: 通过高德天气 API 接口,每隔 3 个小时定时发送定时事件,将国内城市未来 3 天...

Mr_zebra
41分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部