文档章节

霍夫曼编码

如比如比
 如比如比
发布于 2015/10/21 05:43
字数 613
阅读 164
收藏 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文件格式详解
如比如比
粉丝 127
博文 178
码字总数 286951
作品 0
日本
程序员
私信 提问
深入学习二叉树(三) 霍夫曼树

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

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

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

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

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

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

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

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

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

jdflyfly
2014/04/13
179
0

没有更多内容

加载失败,请刷新页面

加载更多

作为一个(IT)程序员!聊天没有话题?试试这十二种技巧

首先呢?我是一名程序员,经常性和同事没话题。 因为每天都会有自己的任务要做,程序员对于其他行业来说;是相对来说比较忙的。你会经常看到程序员在发呆、调试密密麻麻代码、红色报错发呆;...

小英子wep
59分钟前
12
0
【SpringBoot】产生背景及简介

一、SpringBoot介绍 Spring Boot 是由 Pivotal 团队提供的全新框架,其设计目的是用来简化新 Spring 应用的初始搭建以及开发过程,该框架使用了特定的方式来进行配置,从而使开发人员不再需要...

zw965
今天
4
0
简述并发编程分为三个核心问题:分工、同步、互斥。

总的来说,并发编程可以总结为三个核心问题:分工、同步、互斥。 所谓分工指的是如何高效地拆解任务并分配给线程,而同步指的是线程之间如何协作,互斥则是保证同一时刻只允许一个线程访问共...

dust8080
今天
6
0
OSChina 周四乱弹 —— 当你简历注水但还是找到了工作

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @花间小酌 :#今日歌曲推荐# 分享成龙的单曲《男儿当自强》。 《男儿当自强》- 成龙 手机党少年们想听歌,请使劲儿戳(这里) @hxg2016 :刚在...

小小编辑
今天
3.2K
22
靠写代码赚钱的一些门路

作者 @mezod 译者 @josephchang10 如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。 今天给大家分享一个精彩的 GitHub 库,这个库整理...

高级农民工
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部