文档章节

霍夫曼编码摘录(Huffman coding)

jdflyfly
 jdflyfly
发布于 2014/04/13 21:07
字数 573
阅读 179
收藏 5

计算机资料处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。

霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明霍夫曼树的WPL是最小的。


(一)进行霍夫曼编码前,我们先建立一个霍夫曼树。

  • ⒈将每个英文字母依照出现频率由小排到大,最小在左,如Fig.1

  • ⒉每个字母都代表一个终端节点(叶节点),比较F.O.R.G.E.T五个字母中每个字母的出现频率,将最小的两个字母频率相加合成一个新的节点。如Fig.2所示,发现FO的频率最小,故相加2+3=5。

  • ⒊比较5.R.G.E.T,发现RG的频率最小,故相加4+4=8。

  • ⒋比较5.8.E.T,发现5E的频率最小,故相加5+5=10。

  • ⒌比较8.10.T,发现8T的频率最小,故相加8+7=15。

  • ⒍最后剩10.15,没有可以比较的对象,相加10+15=25。

(二)进行编码

  • 1.给霍夫曼树的所有左链结'0'与右链结'1'。

  • 2.从树根至树叶依序记录所有字母的编码,如Fig.3






本文转载自:http://zh.wikipedia.org/wiki/%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81

jdflyfly
粉丝 5
博文 115
码字总数 30127
作品 0
杭州
程序员
私信 提问
数据结构-04-霍夫曼压缩(Huffman Compression)

Huffman Compression - 霍夫曼压缩 主要思想:放弃文本文件的普通保存方式:不再使用7位或8位二进制数表示每一个字符,而是用较少的比特表示出现频率最高的字符,用较多的比特表示出现频率低...

Corwien
2016/06/17
54
0
【工具使用系列】关于 MATLAB 图像编码 & 图像压缩,你需要知道的事情

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

AllenMoore
2018/01/27
39
0
简单聊聊 GZIP 的压缩原理与日常应用

前言 在基于 HTTP 协议的网络传输中 GZip 经常被使用,Nginx 中也可以使用半行代码开启 GZip。GZip 压缩的原理是什么呢?本篇文章是我在网上阅读了一些文档后做的简单总结。 从 RFC 1952 看起...

rccoder
2018/08/19
0
0
从零开始手敲次世代游戏引擎(JPEG特别篇)-2

接从零开始手敲次世代游戏引擎(JPEG特别篇)-1。 (首先说一下,这篇会非常难看。但是如果动手去做了,会对各项能力有极大的提高) 我们现在有了核心的算法库,接下来就是实际读取JPEG文件并...

陈文礼
2017/12/09
0
0
[~ Tue, 26 July 2016] Deep Learning in arxiv

Deep3D:Fully Automatic 2D-to-3D Video Conversion with Deep Convolutional NeuralNetworks 论文:http://homes.cs.washington.edu/~jxie/pdf/deep3d.pdf 代码:https://github.com/piiswr......

sunbaigui
2016/07/26
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

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部