哈夫曼编码问题?请详细点,谢谢?
权值w={5,29,7,8,14,23,3,11},画出哈夫曼树.
个人认为, 图2的画法有不妥的地方.
问题点就是:
结点3和结点5组成新结点N8,那么新结点N8应该排在原有结点8的后面,还是前面?
个人认为,应该按照图1的做法,将新结点N8排在原有结点8的后面.
分析过程如下:
八个权值从小到大排序是: 3 5 7 8 11 14 23 29
图1 : 哈夫曼树
N100
/ \
N42 N58
/ \ / \
23 N19 29 N29
/ \ / \
11 N8 14 N15
/ \ / \
3 5 7 8
根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4
如此类推,哈夫曼树的带权路径长度(WPL)等于
29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271
哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
权值29: 10
权值23: 00
权值14: 110
权值11: 010
权值8 : 1111
权值7 : 1110
权值5 : 0111
权值3 : 0110
图2 : 哈夫曼树
N100
/ \
N58 N42
/ \ / \
N29 29 N19 23
/ \ / \
14 N15 8 11
/ \
7 N8
/ \
3 5
根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点3的路径长度是5,结点3的带权路径长度是3*5
如此类推,哈夫曼树的带权路径长度(WPL)等于
29*2 +23*2 +14*3 +11*3 +8*3 +7*4 +5*5 +3*5 = 271
哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
权值29: 01
权值23: 11
权值14: 000
权值11: 101
权值8 : 100
权值7 : 0010
权值5 : 00111
权值3 : 00110
从 WPL 的角度看,图1和图2的WPL都是等于271.
从 哈夫曼编码 的角度看:
图1, 权值29的编码是10, 权值3的编码是0110
图2, 权值29的编码是01, 权值3的编码是00110
图2的权值29和权值3的编码长度相差大了一点.
相比下,图1的方案更加合适,所以优先选择图1的哈夫曼树.
图1和图2出现编码差异大的主要原因是:
结点3和结点5组成新结点N8,那么新结点N8应该排在原有结点8的后面,还是前面?
图1的做法是将新结点N8排在原有结点8的后面,所以结点7与原有结点8先合并.
而图2的做法是新结点将N8排在原有结点8的前面,所以结点7和新结点N8先合并了.
个人认为,应该按照图1的做法,将新结点N8排在原有结点8的后面.
另外,个人认为,图1的结点11和N8的左右位置互换一下,结点23和N19左右位置互换一下,
这样会更加合适,保证从左到右,结点是从小到大,让最后编码的时候,更加统一.
以下是详细的构建过程:
(1) 从小到大排序 3 5 7 8 11 14 23 29 (这是有序序列)
(2) 每次提取最小的两个结点,取结点3和结点5,组成新结点N8,其权值=3+5=8,
取数值较小的结点作为左分支,结点3作为左分支,而结点5就作为右分支.
(3) 将新结点N8放入有序序列,保持从小到大排序:
7 8 N8 11 14 23 29 [注意,新结点N8排在原结点8的后面]
(4) 重复步骤(2),提取最小的两个结点,结点7与结点8组成新结点N15,其权值=7+8=15,
结点7的数值较小,将结点7作为左分支,结点8就作为右分支.
(5) 将新结点N15放入有序序列,保持从小到大排序:
N8 11 14 N15 23 29
(6) 重复步骤(2),提取最小的两个结点,N8与结点11组成新结点N19,其权值=8+11=19,
N8的数值较小,作为左分支,结点11就作为右分支.
(7) 将新结点N19放入有序序列,保持从小到大排序:
14 N15 N19 23 29
(8) 重复步骤(2),提取最小的两个结点,结点14与N15组成新结点N29,其权值=14+15=29,
结点14的数值较小,作为左分支,N15就作为右分支.
(9) 将新结点N29放入有序序列,保持从小到大排序:
N19 23 29 N29 [注意,新结点N29排在原结点29的后面]
(10)重复步骤(2),提取最小的两个结点,N19与结点23组成新结点N42,其权值=19+23=42,
N19的数值较小,作为左分支,结点23就作为右分支.
(11)将新结点N42放入有序序列,保持从小到大排序:
29 N29 N42
(12)重复步骤(2),提取最小的两个结点,结点29与N29组成新结点N58,其权值=29+29=58,
结点29与N29的数值相同,将原结点29作为左分支,N29就作为右分支.
(13)将新结点N58放入有序序列,保持从小到大排序:
N42 N58
(14)重复步骤(2),提取剩下的两个结点,N42与N58组成新结点N100,其权值=42+58=100,
数值较小的N42作为左分支,N58就作为右分支.
最后得到"哈夫曼树":
N100
/ \
N42 N58
/ \ / \
N19 23 29 N29
/ \ / \
N8 11 14 N15
/ \ / \
3 5 7 8
带权路径长度(WPL):
根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点23的路径长度是2,结点23的带权路径长度是23*2
根结点N100到结点14的路径长度是3,结点14的带权路径长度是14*3
根结点N100到结点11的路径长度是3,结点11的带权路径长度是11*3
根结点N100到结点8的路径长度是4,结点8的带权路径长度是8*4
根结点N100到结点7的路径长度是4,结点7的带权路径长度是7*4
根结点N100到结点5的路径长度是4,结点5的带权路径长度是5*4
根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4
所以,哈夫曼树的带权路径长度(WPL)等于
29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271
哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N100到结点29,先经历右分支,再经历左分支,结点29的编码就是10
从根结点N100到结点23,先经历左分支,再经历右分支,结点23的编码就是01
从根结点N100到结点14,经历两次右分支,再经历左分支,结点14的编码就是110
如此类推,得出所有结点的"哈夫曼编码":
权值29: 10
权值23: 01
权值14: 110
权值11: 001
权值8 : 1111
权值7 : 1110
权值5 : 0001
权值3 : 0000
哈夫曼编码问题?请详细点,谢谢?
权值w={5,29,7,8,14,23,3,11},画出哈夫曼树.个人认为, 图2的画法有不妥的地方.问题点就是:结点3和结点5组成新结点N8,那么新结点N8应该排在原有结点8的后面,还是前面?个人认为,应该按照图1的做法,将新结点N8排在原有结点8的后面.分析过程如下:八个权值从小到大排序是: 3 5 7 8 11 1...
求有关哈夫曼编码的问题?
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其...
求这道题 哈夫曼编码 详细
首先构造哈夫曼树，选择两个最小权值结点构造树，树的根权值是两个左右子树的权值之和，该权值放回到原来的序列中。然后再次构造直到只有一颗树为止。0.07 0.13 0.14 0.16 0.18 0.32 0.18 0.20 0.30 0.32 \/ \\ \/ \\ 0.07 0.13 0.14 0.16 ...
霍夫曼编码详解
霍夫曼编码，一种革命性的变长编码技术，以其卓越的效率和适应性，为信源传输提供了优化解决方案。它的核心理念在于，根据信源符号出现频率的高低，将高频符号映射为简短的二进制序列，反之则为较长序列，从而实现平均码长最小化的目标。编码过程遵循递归原则，首先将概率最小的两个符号配以0和1，然后将...
霍夫曼编码详解
霍夫曼编码是一种变长编码方法，通过将频繁出现的固定长度序列映射为较短的二进制序列，低频序列则对应较长序列，以实现信源的最优编码。其目标是使信源的平均码长接近或等于信源的信息熵。霍夫曼编码的步骤涉及对信源符号按概率进行排序和合并，形成新的符号和对应的二进制编码。编码效率受信源熵和平均码...
一道关于求哈夫曼编码的数据结构题,求解答
哈夫曼编码首先要构造哈夫曼树，其构造规则是从概率这个序列中选择两个最小结点的值构造一颗树，新的树根的权值为两个子树的概率权值和。如题中，首先选择0.02 和 0.03构造一颗树，将权值之和放回序列中，为：0.07 0.19 0.10 0.32 0.21 0.06 0.05 继续上述过程只剩下一颗树为止。最终哈...
一道关于哈夫曼编码的题该怎么做?
首先，亲请记住，无论是数学题政治题C语言，任何情况下都不可以选“以上都不是”。哈夫曼编码是非常经典的一种变长编码方案。我偷个懒，方法描述如下：首先，将符号按照概率由大到小排队。编码时，从最小概率的两个符号开始，可选其中一个支路为0，另一支路为1。再将已编码的两支路的概率合并，并...
什么是哈夫曼编码?
【答案】字符A，B，C，D出现的次数为9，1，5，3。其哈夫曼编码如下：A:1，B:000，C:01，D:001 。它们出现的频度为：A -- 9 B -- 1 C -- 5 D -- 3 它们的最优编码为：A -- 1 B -- 000 C -- 01 D -- 001
一个关于数据结构的问题,有关哈夫曼编码的,解答看不懂,求解答,谢谢...
第1点，编码长度不超过4，每一个“\/”边表示为0 ，“\\”边表示为1，如上图A的编码是：0000，B是0001，如果深度超过5，有六层的话，最下面的叶子结点编码有5位，所以编码长度不超过4，说明哈夫曼树深度不超过5 第2点，编码1 和 01 是在深度为2、3层，如上面的图Y。第3点，其他字符有可能...
哈夫曼编码问题
第三步：26 \/ \\ 11 15 E \/ \\ 7 8 A \/ \\ 3 5 C D 第四步：53 \/ \\ 26 27 \/ \\ B 11 15 E \/ \\ 7 8 A \/ \\ 3 5 C D 最后一步——编码：左分支为0，右分支为1，则结果为：A: 010 B: 1 C: 0110 D: 0111 E: 00 ...
贯岚亿恒： 两个最小的编码没有左右之分.是不同,哈夫曼编码不是唯一的,但是它们的WPL(带权路径长度)都是一样的.如果,最下面有两个二叉树,那么也不用考虑左右的问题,你只将最下面两个二叉树当作两个节点就可以了.记住:哈夫曼编码不...
昆都仑区13622445791： 有谁知道Huffman编码的详细编码 - ？
贯岚亿恒： 为了便于说明,我们先进行一些定义. 原始数据:需要被压缩的数据 压缩数据:被压缩过的数据 n:字母表的长度 a〔,j〕:字母表中第j个字符 t:已处理的原始数据中字符的总个数 k:已处理数据中各不相同字符的个数 显然1„j,k„n 在压缩开始...
昆都仑区13622445791： 求解,关于数据结构的哈夫曼编码的问题 - ？
贯岚亿恒： 方案一应该指的就是下面那个图了.下面那个图是一棵二进制的哈夫曼树,其中因为是二进制编码,所以使用的是0\1的边.那么对于每一个叶子节点来说,从根节点到叶子节点走过的边就是这个数字的编码.那么举一个例子,比如频数=2的也就是最...
昆都仑区13622445791： 哈夫曼编码的工作原理,性能,应用 - ？
贯岚亿恒： 哈夫曼编码(Huffman Coding)是一种编码方式,以哈夫曼树—即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩. 在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称＂熵编码法＂),用于数据的无损耗压缩....
昆都仑区13622445791： 哈夫曼编码,这道题应该怎么做 - ？
贯岚亿恒： 首先,亲请记住,无论是数学题政治题c语言,任何情况下都不可以选“以上都不是”.哈夫曼编码是非常经典的一种变长编码方案.我偷个懒,方法描述如下:首先,将符号按照概率由大到小排队.编码时,从最小概率的两个符号开始,可选...
昆都仑区13622445791： 哈夫曼树和哈夫曼编码 - ？
贯岚亿恒： 给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 哈夫曼树(霍夫曼树)又称为最...
昆都仑区13622445791： 求助有关哈夫曼树编码的问题?急! - ？
贯岚亿恒： 我去年数据结构课程设计做的就是这个,具体什么意思也忘得差不多了 反正做了好多天的 把这段代码复制给你void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC, LNode &L,int n){ //构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC ...
昆都仑区13622445791： 如何证明哈夫曼编码一定是不重复的最优编码 - ？
贯岚亿恒： 哈夫曼编码完全依据字符出现概率来构造异字头的平均长度最短的码字,所以频率相同的编码可以互换,两种编码之后的字符串的平均期望长度是相同的.这里你和你同学做出的结果不同是因为哈夫曼树是二叉树,编码频率相同,但插入到二叉树的顺序不同,所以出现了不同的结果.
昆都仑区13622445791： 哈夫曼编码??？
贯岚亿恒： 哈夫曼树的构造原理,就是先选取概率最小的两个,就是0.02和0.03,相加,得到0.05,同时删去0.02和0.03,然后把0.05放到原来的集合里面,再次选取最小的两个(现在是0.05和0.06)..这样不断进行,直到只剩一个元素为止.. 举个简单例子..生成哈夫曼树之后,左子树为0,右子树为1,根节点不算在内..您的电文哈夫曼编码是:
