当前位置:首页 >> 计算机软件及应用 >> 哈夫曼编码_图文

哈夫曼编码_图文

哈夫曼编码
? ? ?

问题的提出 编码简介 哈夫曼编码方法
? 编码过程
构建哈夫曼树 ? 进行哈夫曼编码
?

? 译码过程
构建哈夫曼树 ? 进行哈夫曼译码
?

简易哈夫曼编码/译码系统

? ? ?

哈夫曼编码系统 哈夫曼译码系统 哈夫曼编码/译码例

问题的提出
?

设计开发一个简易的编码/译码系统
? 该系统模拟单向信息传输通道 ? 在发送端通过一个编码系统将欲传输的数据进行编码
?

称欲传输的数据为原码报文

? 在接收端通过一个译码系统对传来的数据进行译码(复 原)
?

称传来的数据为发送报文

? ?

如图所示 对该系统首先明确编码的基本概念

返回开头

一个简易编码/译码系统图示

发送端
发送报文 原码报文

接收端

编码系统
通信通道

译码系统

原码报文

返回问题的提出

编码简介
?

什么是编码
? 将源对象内容用预先规定的方法转换成另一种格式的过 程
?

称这种预先规定的方法为编码方法

? 编码方法有多种 ? 本问题采用哈夫曼编码方法
?

什么是哈夫曼编码方法
? 1952年由美国计算机科学家戴维· 哈夫曼先生提出 ? 是一种数据压缩技术 ? 该方法依据字符出现的概率进行编码 ,其基本思想为:
出现概率高的字符使用较短的编码 ? 出现概率低的则使用较长的编码 ? 使编码之后的码字的平均长 度最短
?

?

本问题的简易系统也可以如图所示

返回开头

一个简易哈夫曼编码/译码系统图示

返回 发送端
发送报文 原码报文

接收端

哈夫曼编码系统
通信通道

哈夫曼译码系统

原码报文

返回编码简介

哈夫曼编码方法
?

哈夫曼编码方法包含两个过程
? 编码过程和译码过程

?

编码过程
? 构建哈夫曼树 CreatHT(W,&HT)
?

输入是字符频度表W
? 表中记录的是原码报文中出现的不同符号个数和频率

?

输出是哈夫曼树HT

? 进行哈夫曼编码 HuffmanCoding(HT,&HC)
输入是哈夫曼树HT ? 输出是字符编码表HC
?

?

译码过程
返回开头

哈夫曼编码方法
?

哈夫曼编码方法包含两个过程
? 编码过程和译码过程

? ?

编码过程 译码过程
? 构建哈夫曼树 CreatHT(W,&HT)
?

输入是字符频度表W
? 表中记录的是原码报文中出现的不同符号个数和频率

?

输出是哈夫曼树HT

? 进行哈夫曼译码 HuffmanDecod(HT,CC,W,&OC)
输入的是哈夫曼树HT、代码报文CC和字符频度表W ? 输出的是原码报文OC
?

返回开头

构建哈夫曼树
?

构建哈夫曼树 CreatHT(W,&HT)
? 输入是字符频度表W
?

表中记录的是原码报文中出现的不同符号个数和频率

? 输出是哈夫曼树HT
?

例:
? 假设用于通信的电文仅由4个字母{ a,d,i,n } 构成,它们 在电文中出现的概率分别为{ 2,7,5,4},试构建相应的哈 夫曼树,以便为这4个字母进行哈夫曼编码 ? 字符频度表为:
W=((a,2),(d,7),(i,5),(n,4))

?

哈夫曼算法
返回开头

构建哈夫曼树例一
4个字母{ a,d,i,n } 在电文中出现的概率分别为{ 2,7,5,4}
a d i n

2

7

5

4
2

6
4 5

11
6 2 d 7 4 i

18
11 5 6

2
返回构建哈夫曼树

4
n

a

哈夫曼算法
?

?

根据给定的 n 个权值{ w1, w2,…, wn},构成 n 棵 二叉树的集合 F={ T1,T2 ,…,Tn },其中每棵二叉 树Ti中只有一个带权为 wi的根结点,其左右子树 均为空 在 F 中选取两棵根结点的权值最小的树作为左右 子树,构造一棵新的二叉树,且置新的二叉树的 根结点的权值为其左、右子树上根结点的权值之 和 在 F 中删除这两棵树,同时将新得到的二叉树加 入F中 重复(2)和(3),直到 F 只含一棵树为止
? 这棵树便是所求的哈夫曼树 返回构建哈夫曼树

? ?

构建哈夫曼树例二
?

对5个权值 {5,6,2,9,7} 构造哈夫曼树的过程

T1

T2

T3

T4

T5

T6

T7

T8

T9

5

6

2

9

7

7

13

16

30 7

5

2

6

7

9 5

13
2 6 7

16 9 5 7 2

返回

哈夫曼编码
?

例:
? 假设用于通信的电文仅由4个字母{ a,d,i,n } 构成,它们 在电文中出现的概率分别为{ 2,7,5,4},试构建相应的哈 夫曼树,并为这4个字母进行哈夫曼编码

? ?

构建哈夫曼树 进行哈夫曼编码
? 按左分支为0、右分支为1的规则对哈夫曼树的左右分支 进行标记 ? 将从根结点到叶子结点的路径上所有分支标记组成一个 代码序列
?

这个序列就是该叶子结点对应的字符的编码

返回开头

哈夫曼编码例一
4个字母{ a,d,i,n } 在电文中出现的概率分别为{ 2,7,5,4}
字母d的编码为0

18 0

可见:

1
11 0 5

字母i的编码为10

7 d 0 i 10

1
6 0 2 a 110

在电文中出现频率高的字 母其对应叶子结点离根结 点近;出现频率低的字母 其对应叶子结点离根结点 远

字母a的编码为110 字母n的编码为111

1
4 n

因此,在电文中出现频率 高的字母的编码相对短, 而出现频率低的字母的编 码相对长

111 字符编码表HC=((d,0),(i,10),(a,110),(n,111))

返回

2.2.2 哈夫曼编码
?

哈夫曼编码过程演示
0.23 0.21 0.18

编码

A1 A2 A3

1
0 1 0 1 0.10 0

0.44

01 0 00 1 111 1 0.56 1

A4
A5

0.15
0.13

0.33

110
101

A6
A7

0.07 1
0.03 0

0.23

0

1001
1000

可以看出,概率大的符号其编码短,概率小的符号其 编码长,符号使用其编码来表示,达到数据压缩目的

练习

设某信源有 5 种符号 x={A1 , A2 , A3 , A4 , A5} 。在数据 中出现的概率 p={0.25 , 0.22 , 0.20 , 0.18 , 0.15} ,试给 出 Huffman 编码方案,写出每个符号对应的 Huffman 编 码。 答案1:A1:10 A2:01 A3:00 A4:111 A5:110 答案2:A1:01 A2:10 A3:11 A4:000 A5:001

哈夫曼译码
?

接收端接收的是代码报文和字符频度表
? 代码报文为
11010111010111010111110010001001110

字符频度表为
( (a,2) , (d,7) , (i,5) , (n,4) )
? ?

返回

18
7 11 6

构建哈夫曼树 哈夫曼译码

d ? 逐个扫描代码报文 ? 按遇0向左、遇1向右的规则从根出发走一 5 条从根到叶子结点的路径 i ? 与路径对应的代码段就是叶子结点对应字 符的编码 ? 对照字符频度表得到相应字符的原码
继续

2
a

4
n

返回开头

哈夫曼译码例
11010111010111010111110010001001110
看方法

18 7 ai nd i ndinad iddidnd d 5 i 6 2 4 11

原码报文: aindindinadiddidnd

a

n
返回

哈夫曼编码系统
? ? ? ? ? ?

来自哈夫曼译码系统外

输入
?
?

简易哈夫曼编码/译码系统

输入原码报文
OC

原码报文OC
根据原码报文OC

形成字符频度表W 构建哈夫曼树
?
? ? ?

根据字符频度表W
根据字符频度表W和哈夫曼树HT 根据原码报文OC和字符编码表HC 发送报文
?
?

进行哈夫曼编码 形成代码报文CC 输出
字符频度表W
?

哈 夫 曼 编 码 系 统 功 能 流 程

形成字符频度表
W

构建哈夫曼树
HT W

进行哈夫曼编码
HC
OC

形成代码报文
CC

原码报文中出现的不同符号个数和频率

代码报文CC

输出CC和W 返回开头

到哈夫曼译码系统

哈夫曼译码系统
?

来自哈夫曼编码系统 输入W、 CC
W

简易哈夫曼编码/译码系统

?

?

?

哈 夫 ? 代码报文CC和字符频度表W 曼 构建哈夫曼树 编 ? 根据字符频度表W 码 进行哈夫曼译码形成原码报文OC 系 统 ? 根据代码报文CC 功 ? 哈夫曼树HT 能 流 ? 字符频度表W 程 输出 输入
? 原码报文OC

构建哈夫曼树
HT

W
CC

进行哈夫曼译码

形成原码报文
OC

输出OC 到哈夫曼译码系统之外 返回开头

哈夫曼编码/译码例
发送端:
? 接收的原码报文
0C=uvuwxxxvywyuyyvxxyxxuxuvvyvxy

?

? 求出字符频度表
W=( (u , 5),(v , 6),(w , 2),(x , 9),(y , 7) )

? 构建哈夫曼树HT ? 求出字符编码表
HC=( (u,110),(v,00),(w,111),(x,10),(y,01) )

0

30 1 0 13 16 1 1 0 7 y
01

6 v
00

9 x
10

7
0

1

? 求出代码报文

5 u
110

2 w
111

CC=11000110111101010000111101110010100101001101011010110000001001001

接收端

返回开头

哈夫曼编码/译码例
?

接收端:
? 接收代码报文CC

11000110111101010000111101110010100101001101011010110000001001001

? 接收字符频度表W
((u , 5),(v , 6),(w , 2),(x , 9),(y , 7))

? 构建哈夫曼树HT ? 求出原码报文OC uvuwxxxvywyuyyvxxyxxuxuvvyvxy

0

30 1
1

13
0

6 v

7 y

16 1 0 7 9 1 0 x 5 2 u w 返回开头

发送端

?

一个编码/译码简易系统

原码报文

发送报文

发送端:

编码系统

代码报文+字符频度表

发送报文

原码报文

接收端:

代码报文+字符频度表

译码系统


更多相关文档:

哈夫曼编码_图文.ppt

? 译码过程构建哈夫曼树 ? 进行哈夫曼译码 ? 简易哈夫曼编码/译码系统 ? ? ? 哈夫曼编码系统 哈夫曼译码系统 哈夫曼编码/译码例 问题的提出 ? 设计开发一个...

哈夫曼编码讲解_图文.ppt

哈夫曼编码讲解 - Huffman树及其应用 a 一、最优二叉树(霍夫曼树) b

哈夫曼编码方法Huffman_图文.ppt

哈夫曼编码方法Huffman - 数字图像处理 第十五章 图像压缩和编码 CH1

哈夫曼编码演示_图文.ppt

哈夫曼编码演示 - 哈弗曼编码的演示PPT,效果十分成功,可供参考... 利用编

哈夫曼树编码_图文.doc

哈夫曼树编码 - 通过对一个例题的详细解答,说明如何使用哈夫曼树构造哈夫曼编码... 哈夫曼树编码_电脑基础知识_IT/计算机_专业资料。通过对一个例题的详细解答,说明...

6.6哈夫曼编码_图文.ppt

6.6哈夫曼编码 - 先介绍二叉树的典型应用 平衡树 特点:所有结点左右子树

《信息论与编码》第5章哈夫曼编码_图文.ppt

《信息论与编码》第5章哈夫曼编码 - 编码简介 ? 什么是哈夫曼编码方法 ? 1

哈夫曼编码_图文.doc

哈夫曼编码 - 郑州轻工业学院本科生实验报告 实验 名称 课程 名称 姓名学号 1. 2. 哈夫曼编码 信息论与编码 ** *** 指导教 师 实验时 间 *...

进制哈夫曼编码_图文.ppt

进制哈夫曼编码 - 5.4 哈夫曼(Huffman)编码 二进制哈夫曼码的编码方

第24章哈夫曼编码的实现_图文.ppt

第24章哈夫曼编码的实现 - 第24章 哈夫曼编码的实现 ? 问题描述 ? 问题分析及实现 ? 开发过程常见问题及解决 第24章 哈夫曼编码的实现 ? 问题描述 ? 问题...

哈夫曼编码_图文.ppt

哈夫曼编码 - 哈夫曼编码 邹健 School of Information a

3)哈夫曼编码方法_图文.ppt

3)哈夫曼编码方法 - 数字图像处理 图像压缩和编码 图像压缩和编码 ? 一、序

哈夫曼编码_图文.ppt

哈夫曼编码 - 6.5 Huffman树及其应用 b d e a c f g 一

哈夫曼编码_图文.ppt

哈夫曼编码 - Huffman树及其应用 一、Huffman树 二、Huffman编码 Huffman树 Huffman编码 带权路径 长度最短 的树 是通信中 最经典的 压缩编码 1 最优二...

哈夫曼编码_图文.ppt

哈夫曼编码 - 实验一 哈夫曼编码 ? 实验目的 ? 掌握哈夫曼编码原理 ? 理解数据压缩的实现过程 实验要求 根据哈夫曼编码算法,对下列信源实现哈夫 曼编码。求出...

哈夫曼编码_图文.ppt

哈夫曼编码 - 哈夫曼编码 霍夫曼树 (Huffman Tree) 路径长度 (

数据结构实习报告哈夫曼编码_图文.doc

数据结构实习报告哈夫曼编码 - 数据结构课程设计 实习报告 题 目: Huffman 编码及译码 学姓年学专 号: 名: 级: 院: 业: 1210522 何厚华 大二 计算...

哈夫曼编码_图文.ppt

哈夫曼编码 - 第7章 树和二叉树 7.1 树 7.2 二叉树 7.3 以结点类

哈夫曼编码方法Huffman_图文.ppt

哈夫曼编码方法Huffman - CH15 图像压缩和编码 ? 一、序言 ? 二

C语言哈夫曼编码课程设计开题报告_图文.ppt

C语言哈夫曼编码课程设计开题报告_工学_高等教育_教育专区。数据结构关于哈弗曼编

网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com