精华内容
下载资源
问答
  • 哈夫曼编码习题
    万次阅读 多人点赞
    2019-11-07 19:57:45

    假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为

    0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10

    请为这8个字母设计哈夫曼编码。

    表格形式:

    NO.dataparentLchildRchild
    00.07(A)10NULLNULL
    10.19(B)12NULLNULL
    20.02(C)8NULLNULL
    30.06(D)9NULLNULL
    40.32(E)13NULLNULL
    50.03(F)8NULLNULL
    60.21(G)12NULLNULL
    70.10(H)10NULLNULL
    80.05925
    90.111183
    100.171107
    110.2813910
    120.41416
    130.614114
    141.0NULL1213

     

    该表格也就是静态三叉链表,小编自己由多加了一列编号,三叉链表从左到右依次为权值(data)、双亲序号(parent)、左孩子序号(Lchild)、右孩子序号(Rchild)。

    通俗的说,求哈夫曼编码就是根据三叉链表计算出最优二叉树,算法是(在链表权值内取最小的两位权值相加,然后删去最小的两位数,将它们的和存入链表,然后重复取最小的两个数,存入两个数的和,删去原来的两个相加的小数。这一个循环的过程,一直到最后算出的那个最终的数,就是最优二叉树的权值)

    本题来讲,第一步就是找到两个最小的数,编号分别为2(0.02),5(0.03).【一般以较小的数为左孩子,较大的数为右孩子】然后写入到编号为8的左孩子和右孩子的二叉链表处。直至填满编号为14的三叉链表。

    二叉树表示:

    根据三叉链表,便可以画出二叉树,A-H对应着相应的数据,可以在二叉树中找到对应的位置,按照左0右1的编码规则,得到每个字母对应的哈夫曼编码。(也就是每个字母对应的二叉树路径)

    Endeavor

    更多相关内容
  • 哈夫曼树 定义: 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较...

    哈夫曼树

    定义:

    给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    理解:

    举个栗子:假如你有一个衣柜里面有ABCDEF共6件衣服,但是每个衣服穿的频率都是不一样的,54%(问就是喜欢穿),10%,6%,3%,7%,20%
    那么现在问题来了,你该怎样把衣服放置才能避免每次找衣服的时候把衣柜搞得一团糟呢?
    答案肯定是把频率高的放到里你最近的地方
    没错!!哈夫曼树就是这样

    下面我们来看看怎样构建一个哈夫曼树来完成这个操作
    在这里插入图片描述

    只需要记住一句话:找两个最小的顶点合并
    在这里插入图片描述

    接下来一直重复一直重复~~
    在这里插入图片描述

    很显然~~~
    你可以发现
    它的每一个叶子都是衣服,而且,最大频率的里树根最近
    这就形成了一棵哈夫曼树


    接下来重点来了

    哈夫曼编码

    我们知道,编码方式有很多种常见的有ASCII编码,二进制编码等等
    下面介绍一种哈夫曼编码
    还是上面的衣服
    我们规定:右子树为1,左子树为0(就是向右找就是1,向左找就是0)
    可以根据图来分析一下
    在这里插入图片描述

    对于上面的衣服来说我们可以用ASCII编码也可以用2进制编码
    当然也可以用哈夫曼编码
    下面我们来分析一下哪一种效率最高(也就是用最短的码长实现编码)
    A S C I I : 8 b i t ASCII:8bit ASCII8bit
    二 进 制 : 3 b i t 二进制:3bit 3bit
    哈夫曼编码:因为哈夫曼编码的不定长性,我们要求出平均码长 ACL
    A C L = 0.54 ∗ 1 + 0.20 ∗ 2 + 0.10 ∗ 3 + 0.07 ∗ 4 + 0.09 ∗ 5 = 1.97 ACL=0.54*1+0.20*2+0.10*3+0.07*4+0.09*5 = 1.97 ACL=0.541+0.202+0.103+0.074+0.095=1.97

    显然!!哈夫曼要小于另外两种编码长度

    下面我们用代码实现上述哈夫曼树的构造

    结合表格理解效果更佳~~~
    这个表格也成为编译码表,可以说如果你用哈夫曼编码来给你朋友发信息,再厉害网警也绝对发现不了

    结点字符概率parent结点left结点right结点code
    1A5411001
    2B10900010
    3C670001111
    4D370001110
    5E78000110
    6F20100000
    79843
    816957
    9261028
    10461169
    11100101

    Huffman树节点结构

    struct HTNode
    {
    	char ch;   //对应的字母,比如a
    	int weight;//字母的出现次数,比如a出现了1000次
    	int parent;
    	int left;
    	int right;
    	char* code;
    };
    

    初始化树结构

    void InitHTTable(int AsciiCount[], HTNode* &HT)
    {
    	for(int i = 0; i <= 128; i ++) AsciiCount[i] = 0;//将数组初始化为0
    	
    	AsciiCount[65] = 54;
    	AsciiCount[66] = 10;
    	AsciiCount[67] = 6;
    	AsciiCount[68] = 3;
    	AsciiCount[69] = 7;
    	AsciiCount[70] = 20;
    	
    	HT=new HTNode[2 * 6];//生成动态空间[1...2n-1]
    	int	CurrentASCII=0;//当前ASCII码
    	HT[0].weight=0;
    	for(int i = 1; i <= 6; i ++)
    	{
    		while(AsciiCount[CurrentASCII] == 0)//可能ASCII中有断档,找到计数不为零的那个字符
    			CurrentASCII++;
    			
    		HT[i].ch = CurrentASCII;//j就是计数不为零的那个字符的ASCII码
    		HT[i].weight = AsciiCount[CurrentASCII];//这是字符j的出现次数,作为哈夫曼的权重
    		HT[i].parent = 0;//初始化双亲
    		HT[i].left = 0;//初始化左孩子
    		HT[i].right = 0;//初始化右孩子
    		
    		CurrentASCII++;//下一个ASCII码
    	}
    }
    

    找最小的两个概率

    void selectMin(HTNode* &HT,int end,int &min1,int &min2)
    {//在数组HT[1...end]中,找两个权值最小的
    	int i;
    	min1 = 0;
    	min2 = 0;
    	for(i = 1; i <= end; i++)
    	{
    		if(HT[i].parent != 0)//如果这个结点已经有双亲了,说明他已经在树上了
    			continue;
    		else
    		{
    			if(min1 == 0)
    				min1 = i;//记下最小值
    			else if(HT[i].weight < HT[min1].weight)//找到更小的值
    				min1 = i;			
    		}
    	}
    
    	for(i = 1; i <= end; i++)
    	{ 
    		if(HT[i].parent != 0 || i == min1)
    			continue;
    		else
    		{
    			if(min2 == 0)
    				min2 = i;
    			else if(HT[i].weight < HT[min2].weight)
    				min2 = i;			
    		}
    	}
    
    	if(min1 > min2)
    	{//保证min1是最小的
    		int t = min1;
    		min1 = min2;
    		min2 = t;
    	}
    
    }
    

    建树

    void createHT(HTNode* &HT)
    {//创建霍夫曼树,并得到霍夫曼编码
    	int i = 0;
    	for(i = 0; i <= 11; i++)
    	{//初始化全部哈夫曼表格
    		HT[i].parent=0;
    		HT[i].left=0;
    		HT[i].right=0;
    	}
    
    	for(i = 7; i <= 11; i++)
    	{//形成哈夫曼树
    		int min1, min2;
    		selectMin(HT, i - 1, min1, min2);//从哈夫曼表前面i-1项中选择两个最小值,min1最小,构造出来的哈夫曼树左子树小
    		HT[min1].parent = i;
    		HT[min2].parent = i;
    		HT[i].weight = HT[min1].weight + HT[min2].weight;//两个小概率合成一个结点
    		HT[i].left = min1;
    		HT[i].right = min2;
    	}
    
    	//生成叶子的哈夫曼节点
    	int code_length = 0;
    
    	for(i = 1; i <= 6; i++)
    	{
    		char code[128];//保存哈夫曼编码
    		int j = i, k = 0;
    		while(1)
    		{
    			int parentPosition = HT[j].parent;
    			if(parentPosition == 0)
    			{//这是根结点
    				code[k] = '\0';
    				HT[i].code = new char[k + 1];
    				for(int x = 0; x < k; x++)
    					HT[i].code[x] = code[k - 1 - x];
    				HT[i].code[k] = '\0';
    				
    				printf("%c : %d : %s\n",HT[i].ch, HT[i].weight, HT[i].code);// 输出字符概率和编码值 
    				break;
    			}
    
    			if(HT[parentPosition].left == j)
    				code[k++] = '0';
    			else
    				code[k++] = '1';
    
    			j = parentPosition;
    		}
    	}
    }
    

    完结撒花🌼🌻🌼🌻

    展开全文
  • 这是那个用c语言来实现的哈夫曼编码程序,可以对输入的数据进行相应的编码……
  • 例一现在有一个能装 100g 物品的背包,和一些可拆分的物品(见表格),怎么装才能使背包中物品价值最大?物品重量价值A100g100B60g120C50g150D20g50容易想到的方法是通过计算物品单价,从高到低往背包中放。例二在一个...

    理解贪心算法

    贪心算法是一种算法思想,并不是一个具体的算法,因此我们用两个例子来理解什么样的问题适合用贪心算法解决。

    例一

    现在有一个能装 100g 物品的背包,和一些可拆分的物品(见表格),怎么装才能使背包中物品价值最大?

    物品

    重量

    价值

    A

    100g

    100

    B

    60g

    120

    C

    50g

    150

    D

    20g

    50

    容易想到的方法是通过计算物品单价,从高到低往背包中放。

    例二

    在一个加权有向图中,求 A 到 G 的最短距离。

    99804cf6ee33681d42c6cd8825639648.png

    若依旧使用例一中的方法,则找到的路径是 A->B>D>E>G,明显不是最短的路径。

    综述

    例一和例二的相同点:

    要得到最终的结果,都需要多次决策,

    比如例一中每次决策选择一个物品,例二中每次决策选择一条路。

    例一和例二的区别:

    例一中每次决策都不会影响后续的决策范围,即选择了一个物品后,下次选择范围仍然是所有物品,而例二中,第一次决策选择一条路后,第二次决策的可选项会受到第一次决策的影响。

    假设我们给例一增加条件:物品 B 和 D 不能在背包中共存,如此,贪心算法便不可用了,因为当我们在某次决策中选择了物品 B 后,会影响到下一次决策。

    贪心算法,就是在每一次决策时,都选择当前最优的选项。

    贪心算法练习

    钱币找零问题。

    人民币有 1 元,5 元,10 元,20 元,50 元,100 元面值的钱,当我们要找零 98 元时,如何凑呢?

    通常做法是从面值大的开始凑,即 1 张 50,2 张 20,1 张 5,4 张 1,可以得到 98。

    区间覆盖问题

    现在有几个区间[6,8],[2,4],[3,5],[1,5],[5,9],[8,0],要求的是两两不相交的区间最多有几个?

    解决思路,首先对这些区间排序,以右边值从小到大排序,右边值相同的情况下,按左边值从小到大排序,决策时,候选区间左端点不能与已选择的区间相交。

    哈夫曼编码

    假设现在有 10000 个字符,均是由a,b,c,d,e,f,g这7个字符构成,每个字符占 8 bit,一共需要占 80000 bit,思考如何压缩呢?

    方法一:7 个字符可以使用 3 bit 来表示,因为 3 bit 可以表示 8 个字符

    000,001,010,011,100,101,110,111,每个字符用 3 位表示,总大小为 30000 bit。

    方法二:哈弗曼编码,统计 10000 个字符中,a,b,c,d,e,f,g的出现频率,频率高的编码少,频率低的编码多。

    每个字符的编码都不等长的话,在解码的时候,为了避免出现歧义,字符的编码不能存在前缀关系。

    计算哈夫曼编码一般是使用一个优先队列,将每个字符看做一个节点,节点的值是字符的出现频次,每次从队列中取两个节点,组合成一个节点,再入队。

    字符

    出现的频率

    编码

    a

    45

    0

    b

    13

    101

    c

    12

    100

    d

    16

    110

    e

    9

    1111

    f

    5

    1110

    以上述方法画出哈夫曼树:

    6e7dad3a13cbc3b105841aed2ab60fce.png

    展开全文
  • 哈夫曼树-哈夫曼编码

    2019-06-19 15:03:28
    哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为...

    哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。

    如果需要传输一段文字“BADCADFEED”,可以用二进制编码表示。

    这个时候数据编码后是“001000011010000011101100100011”,对方接受后每三位一分进行译码。但是在一段文章中,字母的出现频率肯定有高有低,出现频率高的元素的二进制越短,传输的时候的数据也会越短。如果把上面表格中多余的前导0去掉,例如:B:1,D:11,那么编码之后的二进制的确变短了,但是译码的时候无法知道接受的数据中的11代表两个B还是一个D。

        通过哈夫曼编码可以构造出最优的二叉树-哈夫曼树来确定如何编码。假设

    字母

    A

    B

    C

    D

    E

    F

    频率(%)

    27

    8

    15

    15

    30

    5

    哈夫曼编码的规则就是:

    1、先找出权值(频率){30,27,15,15,8,5}最小的两个作为左右子树构造一棵新树。即取5,8构成新树,其结点为5+8=13,如图:

    2、再把新生成的权值为13的结点放到剩下的集合中,所以集合变成{30,27,15,15,13},再根据1,取最小的两个权值构成新树,如图:

    3、再依次建立哈夫曼树,如下图:

    4、带入对应的字符,左分支为0,右分支为1。

    对字母用其从树根到所在叶子所经过路径的0或1来编码,可以得到下表:

    字母

    A

    B

    C

    D

    E

    F

    二进制字符

    01

    1001

    101

    00

    11

    1000

    对比一下两种编码方式:大于节约17%的存储或传输成本。

    编码中非0即1,长短不等的话其实很容易混淆的,所以若要设计长短不等的编码,则必须是任一字符的编码都不是另一个字符的编码的前缀,这种编码称作无前缀编码。

    哈夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合。如果考虑到进一步节省存储空间,就应该将出现概率大(占比多)的字符用尽量少的0-1进行编码,也就是更靠近根(节点少),这也就是最优二叉树-哈夫曼树。

    展开全文
  • Qt实现哈夫曼编码解压缩软件详解

    千次阅读 多人点赞 2020-06-02 22:52:37
    问题拆解:设计一个基于哈夫曼编码的解压缩软件,这个问题我认为可以分解为以下几个子问题: 读取传入文件,进行字符权重统计 将出现的字符放入哈夫曼树结点,构建哈夫曼树,获取哈夫曼编码 将编码相关信息写入压缩...
  • 哈夫曼编码4.1.哈夫曼编码的生成过程 1.计算机是如何存储信息的? 面对数不尽的中文和英文,你能识别,但计算机是无法识别的。我们都知道计算机运行过程中是需要电力进行支持的,所以计算机只能识别低电平和高电平...
  • 正文之前霍夫曼编码(Huffman Coding),又译为哈夫曼编码、赫夫曼编码,是一种用于无损数据压缩的熵编码(权编码)算法。由大卫*霍夫曼在1952年发明                  ——Wikipedia本节我们将介绍...
  • 贪心算法求哈夫曼编码

    千次阅读 2019-12-25 15:48:23
    贪心算法求哈夫曼编码 使用贪心算法解决如下问题 问题:已知字符出现的频率,现要求根据字符出现的频率求出该字符对应的哈夫曼编码。 举例:输入字符频率表 a b c d e 45 13 12 16 9 输出a:0 b:110 c:1110 d:10 e:...
  • 信息论之哈夫曼编码

    千次阅读 2018-11-06 19:01:06
    先将信源符号的概率按...码字W1是按照对应一行的信源符号ai的概率p(ai)在编码过程中担任了0or1,先标记的数字在后面,后标记的在前面。 码长Ki为二进制码字的位数。 将表5-5和5-6中编码过程横向看即可发现,...
  • 《数据结构与算法》课程设计——哈夫曼编码 一、 题目 赫夫曼编译码器 二、 实验目的 掌握赫夫曼编码原理。 熟练掌握赫夫曼树的生成方法。 理解数据编码压缩和译码输出编码的实现。 三、需求分析 初始化...
  • 哈夫曼树的目的是构造效率更高的搜索树。 定义: 例如 如果换一种排练顺序,即把权值低的放在浅层,权值高的放在深层。如下图,此时的WPL为50 所以如何构造一个让WPL最小的树,就是哈夫曼树解决的问题。 哈夫曼树...
  • 这里写自定义目录标题JavaFX实现哈夫曼树和哈夫曼编码的GUI界面的显示原理及作用GUI界面功能如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...
  • 数据结构与算法:哈夫曼树与哈夫曼编码

    千次阅读 多人点赞 2020-02-26 22:32:20
    我们先以成绩评级举例分析,一步一步的认识Haffman树和Haffman编码。 分数 0~59 60~69 70~79 80~89 90~100 成绩 不及格 及格 中等 良好 优秀 所占比例 5% 15% 40% 30% 10% 如果是要真实实现这个功能,...
  • 数据结构实训——哈夫曼编码/译码器

    千次阅读 多人点赞 2019-12-25 10:32:44
    利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输...
  • 给定一组权值,根据权值求其一个哈夫曼树,并通过中序遍历的顺序输出叶子节点的哈夫曼编码。 分析 首先回顾哈夫曼树的求解过程: 在权值中取最小的两个x,y,以这两个权值为叶子节点,生成一个权值为x+y的父亲节点;...
  • 在对输入的数据进行信源编码即哈夫曼编码前首先要统计数据中各个字符出现的频率。对文本中出现的128个ASCII字符进行编码。从输入框中统计数据,统计各个字符出现的频率和总的字符个数。二者相除,即可得到各个字符...
  • 文章目录数据结构(C++)——哈夫曼树及哈夫曼编码一、哈夫曼树的介绍及概念二、哈夫曼树的构造及打印①哈夫曼树的存储结构②构造哈夫曼树③Select()函数的代码实现④打印哈夫曼树⑤测试的完整代码二、哈夫曼编码①...
  • 利用哈夫曼编码压缩文件

    千次阅读 2017-09-05 17:54:48
    大作业报告  1. 简介/介绍/引言 本大作业主要考核如何以C实现集成电路测试向量文件的无损压缩。在通常的文件存储中,无论是二进制格式的文件还是...为了理解定长编码与变长编码的区别,假设某个文件纯粹由abcdef共
  • 什么是字符编码?&nbsp; &nbsp; &nbsp; &nbsp; 计算机只能处理数字,如果要处理文本,就必须先把文本转换为数字才能处理。最早的计算机在设计时采用8个比特(bit)作为一个字节(byte),所以,一个...
  • 哈夫曼树&哈夫曼编码

    千次阅读 2018-06-11 20:38:38
    哈夫曼树也是最优二叉树,首先我们来看哈夫曼树的定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。先再解释一下什么是带权...
  • 哈夫曼编码: HC[i]是二维的字符串数组,用来存放7个由0和1组成的字符串 cd[start]是字符数组,用来存放不断回溯的过程中得到的0或者1,'/0'是字符串结束标志,放在末尾 最终HC[i]表格为: 基本代码如下:...
  • 1 引言 对前缀编码进行解码时,最重要的问题是如何快速的确定...范式哈夫曼编码具有数字序列属性,因而能通过如下算法确定码字的长度: int len = 1; int code = bs.ReadBit(); while(code >= first[len])...
  • 二叉链表实现哈夫曼编码系统

    千次阅读 2019-02-08 23:47:35
    试编写一个Huffman编码系统,用于数据加密和解密。该系统应具有以下功能: 初始化:从键盘中可读取通信所使用的字符集和每个字符的权值。例如下表。 加密 :利用初始化中的数据建立Huffman树,对任意的可加密的字符...
  • 这一片是根据存在的字节转换成赫夫曼编码表 形式为:32->01 97->100 100->11000 新增的小段编码 /** * 思路: * 1.将赫夫曼编码表放在Map<Byte,String >中 * 形式为 32->01 97->100 100->...
  • 哈夫曼压缩与解压缩

    万次阅读 多人点赞 2018-08-13 12:52:01
    哈夫曼压缩与解压缩 目录 哈夫曼压缩与解压缩 一:引言 二:主要技术点 三:过程介绍 1、压缩: 2、解压缩 四:详细分析 一:准备过程 二:压缩 三:解压缩 五:结果演示 六:总结 七:源码地址 一:...
  • //哈夫曼编码 #include #include #include #include #define OK 1 #define ERROR 0 typedef struct{  charc;  intweight;  intparent;  intlchild,rchild;  char*HC; }HTNode;        
  • #include&lt;stdio.h&gt; typedef struct{ //节点的结构 unsigned int weight; unsigned int parent,lchild,rchild;... //动态分配数组存储哈夫曼编码表 //构造哈夫曼树,并求哈夫曼编码 Huffm...
  • 课程设计哈夫曼编/译码系统

    千次阅读 热门讨论 2017-07-03 10:29:01
    问题描述:利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(解码)。对于双工信道(即...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 756
精华内容 302
关键字:

哈夫曼编码表格

友情链接: FDFD_pc.rar