TT 哈夫曼编码

朴灿烈づ我的快乐病毒、 2022-08-04 15:44 98阅读 0赞

某段文本中各个字母出现的频率分别是\{a:4，b:3，o:12，h:7，i:10\}，使用哈夫曼编码，则哪种是可能的编码：（）

*  a(000) b(001) h(01) i(10) o(11)
 *  a(0000) b(0001) h(001) o(01) i(1)
 *  a(000) b(001) h(01) i(10) o(00)
 *  a(0000) b(0001) h(001) o(000) i(1)

【解析】

创建一个哈夫曼树，原则如下：

1. 将每个英文字母依照出现频率由小排到大，最小在左，组成一个序列；  
2. 每个字母都代表一个终端节点（叶节点），比较每个字母的出现频率，将最小的两个字母频率相加合成一个新的节点，将两个字母从序列中删除，将生成的节点加入到字母队列中；

3. 重复前面两步，直到序列中没有字母为止。

哈夫曼进行编码：

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

2. 从树根至树叶依序记录所有字母的编码。

构造哈夫曼树：

v = ｛b(3)，a(4)，h(7),i(10),o(12)｝

取最小两个权值构成一棵树（如下）

\--------（7）

\---------/---\\

\-------/------\\

\-----b(3)---a(4)

然后将（7）加入序列：（7），h(7),i(10),o(12)

再取最小两个权值构成树：如下

\-----------------(14)

\--------------/--------\\

\------------/------------\\

\--------（7）---------h(7)

\---------/---\\

\-------/------\\

\-----b(3)---a(4)

将（14）加入权值序列：（14）,i(10),o(12)

现在取10跟12构成一颗新数：如下

\----------------(14)------------------(22)

\--------------/--------\\----------------/-----\\

\------------/------------\\ -----------/----------\\

\--------（7）---------h(7) ---i(10)--------o(12)

\---------/---\\

\-------/------\\

\-----b(3)---a(4)

最好权值相加:

\--------------------------(36)

\--------------------/-----------------\\

\------------------/---------------------\\

\----------------(14)------------------(22)

\--------------/--------\\----------------/-----\\

\------------/------------\\ -----------/----------\\

\--------（7）---------h(7) ---i(10)--------o(12)

\---------/---\\

\-------/------\\

\-----b(3)---a(4)

现在执行哈夫曼编码：从第二个接点开始：

进行编码：

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

2. 从树根至树叶依序记录所有字母的编码

\--------------------------(36)

\--------------------/-----------------\\

\------------------/---------------------\\

\----------------0(14)------------------1(22)

\--------------/--------\\----------------/-----\\

\------------/------------\\ -----------/----------\\

\--------0（7）---------1h(7) ---0i(10)--------1o(12)

\---------/---\\

\-------/------\\

\-----0b(3)---1a(4)

结果：a:001,b:000,h:01,i:10,o:11

答案：A

发表评论取消回复

表情：

评论列表（有 0 条评论，98人围观）

还没有评论，来说两句吧...

相关阅读

相关哈夫曼编码

哈夫曼编码是一种用于无损数据压缩的编码方式，它的原理是将数据中出现频率较高的字符用较短的编码表示，而将数据中出现频率较低的字符用较长的编码表示，以此来达到压缩数据的目的。哈夫曼

灰太狼/ 2024年03月25日 04:03/ 0 赞/ 82 阅读

相关哈夫曼编码

哈夫曼编码一、简介 1.1定义哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952

爱被打了一巴掌/ 2022年08月27日 11:56/ 0 赞/ 199 阅读

相关 TT 哈夫曼编码

某段文本中各个字母出现的频率分别是\{a:4，b:3，o:12，h:7，i:10\}，使用哈夫曼编码，则哪种是可能的编码：（） a(000) b(001) h(01)

朴灿烈づ我的快乐病毒、/ 2022年08月04日 15:44/ 0 赞/ 98 阅读

相关哈夫曼树与哈夫曼编码

在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN) 树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如 JPEG中就应用

曾经终败给现在/ 2022年07月30日 19:21/ 0 赞/ 298 阅读

相关哈夫曼树和哈夫曼编码

哈夫曼树给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径

快来打我*/ 2022年07月18日 01:23/ 0 赞/ 272 阅读

相关哈夫曼编码

哈夫曼编码（还有对应的实验报告，在我的上传资源里，可以免费下载）） ![Image 1][]1.设计内容 1.添加用户登录密码 2.建立哈夫曼树：

心已赠人/ 2022年06月18日 12:16/ 0 赞/ 208 阅读

相关哈夫曼编码

1. 问题描述假设某文本文档只包含26个英文字母，应用哈夫曼算法对该文档进行压缩和解压缩操作，使得该文档占用较少的存储空间。 2. 基本要求（1）假设文档内容

绝地灬酷狼/ 2022年03月28日 10:38/ 0 赞/ 359 阅读

相关哈夫曼编码

题目：给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串

矫情吗；*/ 2022年03月02日 03:25/ 0 赞/ 272 阅读

相关哈夫曼编码

哈夫曼编码给出一个字符串，求其最优[哈夫曼编码][Link 1]。思路：可以根据给出的字符串，分析其中出现过最多的单个字符是什么，并采用哈夫曼树的方式构建一颗

àì夳堔傛蜴生んèń/ 2022年01月23日 03:51/ 0 赞/ 243 阅读

相关哈夫曼编码

//哈夫曼树构造原则: 权值小的在前，相等的单节点在前； include "stdafx.h" include <stdio.h> i

ゝ一世哀愁。/ 2021年06月24日 15:56/ 0 赞/ 416 阅读