精华内容
下载资源
问答
  • 之前弄明白了信息熵是什么,...如果信息熵不明白的请看这里:http://blog.csdn.net/hearthougan/article/details/76192381首先给出结果:最短平均编码长度 = 信源的不确定程度 / 传输的表达能力。其中信源的不确定

           之前弄明白了信息熵是什么,由于信息熵来源于信息论,要怎么才能跟编码联系起来呢?这个问题当时没有想明白,今天查了一下资料,理解了一下,做笔记整理一下,如有错误欢迎指正。

    如果信息熵不明白的请看这里:http://blog.csdn.net/hearthougan/article/details/76192381

    首先给出结果:

    最短的平均编码长度 = 信源的不确定程度 / 传输的表达能力。

    其中信源的不确定程度,用信源的熵来表示,又称之为被表达者,传输的表达能力,称之为表达者表达能力,如果传输时有两种可能,那表达能力就是,如果是传输时有三种可能,那表达能力就是。以例子来描述,尽量做到通俗易懂。


    例1:昨天小明错过一场有8匹赛马的比赛,编号为1~8号,每匹马赢的概率都一样,那么作为朋友的你要把获胜马的编号发送给他,那么你该怎么做?

    方法一:直接发送马的编号,这样描述一匹马需要3比特(000,001,010,011,100,101,110,111)。

    方法二:利用数据结构中的Huffman编码,如下:


    建立Huffman树:


    由上图可知,当等概率的时候,发送信息仍至少需要3比特。

    被表达者:直接根据概率求熵即可,1/8×log8 * 8 = 3比特。

    表达者:由图可以看出来Huffman树是一颗二叉树,要么是0,要么是1,所以表达能力就是log2.

    平均编码长度 = 3/log2 = 3比特,注意其中的log 都是以2为底的。


    例2:昨天小明错过一场有8匹赛马的比赛,编号为1~8号,1~8号获胜的概率分别为{1/2、1/4、 1/8、 1/16、 1/64、 1/64、 1/64、 1/64},那么作为朋友的你要把获胜马的编号发送给他,那么你该怎么做?

    方法一:仍然直接发送马的编号,这样描述一匹马需要3比特(000,001,010,011,100,101,110,111)。

    方法二:利用数据结构中的Huffman编码,如下:


    建立Huffman树:


    由于概率不相等,则根据Huffman树可知平均编码为:(1 × 1/2 + 2 × 1/4 + 3 × 1/8 + 4 × 1/16 + 6 × 1/64 + 6 × 1/64 + 6 × 1/64 + 6 × 1/64) = 2比特,当概率不相等的时候,发送的平均长度为2比特。

    由上图可知:

    被表达者(不确定程度):


    表达者:由图可以看出来Huffman树是一颗二叉树,要么是0,要么是1,所以表达能力就是log2.

    平均编码长度:2/log2 = 2比特。


    例3:假设有5个硬币:1,2,3,4,5,其中一个是假的,比其他的硬币轻。有一个天平,天平每次能比较两堆硬币,得出的结果可能是以下三种之一:
    左边比右边轻
    右边比左边轻
    两边同样重
    问:至少要使用天平多少次才能保证找到假硬币?

    答案:是2次,

    方法一:可作出如下图的抉择:


    所以至少称重2次,才可以确保找出。

    方法二:

    设X表示硬币,Y表示天平,则,X的取值可以是5枚硬币中的任意一枚,每个硬币的概率都是1/5,那么随机变量X的不确定程度就是:

    H(X) = 1/5×log5 + 1/5×log5 + 1/5×log5 + 1/5×log5 +1/5×log5 = log5

    Y表示天平,A、B两个硬币放在天平,有三种情况:A < B, A > B, A = B。也就是说Y的表达能力就是log3.因此:

    平均编码长度: log5 / log3 = 1.46;换算成次数,也就是至少2次可以确保找到假硬币!


    例4、假设有5个硬币:1,2,3,…5,其中一个是假的,比其他的硬币轻。已知第一个硬币是假硬币的概率是三分之一;第二个硬币是假硬币的概率也是三分之一,其他硬币是假硬币的概率都是九分之一。
    有一个天平,天平每次能比较两堆硬币,得出的结果可能是以下三种之一:
    左边比右边轻
    右边比左边轻
    两边同样重
    假设使用天平n次找到假硬币。问n的期望值至少是多少?

    方法一:同样利用Huffman编码的思想,得出下图:


           由上图可以知道,至少称重2次才可以找到假硬币,这一题与上一题的差别就是,是每一枚硬币的可能性都不一样,所以先比较概率最大的两枚1,2,找到假币的概率占了2/3,如果不在1 、2中,那么从3~5中随便取出两枚硬币,(上图选取的是3 、4两枚硬币)再称一次,就可以找打假硬币!


    方法二:

    设X表示硬币,Y表示天平,则,X的取值可以是5枚硬币中的任意一枚,每个硬币的概率分别是{1/3,1/3,1/9,1/9,1/9},那么随机变量X的不确定程度就是:

    H(X) = 1/3 * log3 + 1/3 * log3 + 1/9 *log9 + 1/9 *log9 + 1/9 *log9 = 4/3 *log3;

    天平的表达能力同样还是log3;

    则平均编码长度:4/3×log 3 / log 3 = 4/3,所以还是需要称重两次。

    总结:

    由上面4个例子,可以知道很清楚的知道,最短的平均编码长度(也就是我们猜的次数,称重的次数),是由随机变量的熵,除以,表达能力的,得到!

    展开全文
  • 算术编码步骤图.pptx

    2020-05-07 09:47:46
    1952 年,哈夫曼提出变长编码方法:对出现概率大的符号分配短字长的二进制码,对出现概率小的符号分配长字长二进制码,**得到符号平均码长最短的码**。变长编码也称最佳编码。 哈夫曼编码,采用一个码字代表一个...
  • 题目:给定一个字符串,求哈夫曼编码最短长度: 输入: abbcccdddd 输出: 19 分析:扫描一遍字符串,计算出每个字符的频度,然后把频度按照放到小顶堆中,每次取小顶堆堆顶的两个频度,把这两个频度的和加入到...

    题目:给定一个字符串,求哈夫曼编码的最短长度:
    输入:

    abbcccdddd
    

    输出:

    19
    

    分析:扫描一遍字符串,计算出每个字符的频度,然后把频度按照放到小顶堆中,每次取小顶堆堆顶的两个频度,把这两个频度的和加入到最短长度中,并且把这个和重新插入小顶堆中;如此循环,直到小顶堆只有一个元素。

    #include<iostream>    
    #include<string>
    #include<map>
    #include<vector>
    #include<queue>
    using namespace std; 
    map<char, int>M;
    priority_queue<int, vector<int>, greater<int>>Freq;
    int ret = 0;
     int main() { 
    	 string a;
    	 cin >> a;
    	 int L = a.length();
    	 for (int i = 0; i < L; i++)
    		 M[a[i]]++;
    	 for (auto it = M.begin(); it != M.end(); it++)
    		 Freq.push(it->second);
    	 while (Freq.size() > 1) {
    		 int a, b;
    		 a = Freq.top();
    		 Freq.pop();
    		 b = Freq.top();
    		 Freq.pop();
    		 ret += a + b;
    		 Freq.push(a + b);
    	 } 
    	 printf("%d\n", ret);
    	 return 0;
    }
    
    展开全文
  • 2018.2.14 Java中的哈夫曼编码

    千次阅读 2021-03-15 02:54:44
    Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。###哈夫曼原理 ###哈夫曼算法流程图 ###...

    ###概念

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

    ###哈夫曼原理

    6b6d15dce058dd248fb4e1ec2adac08a.png

    ###哈夫曼算法流程图

    5f4793ea88e77378923fc8e2762cd164.png

    ###哈夫曼树

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

    a31aafde9092c66d15a21dccc071ad76.png

    从树中的一个节点到另一个节点之间的分支构成两个点之间的路径,路径上的分支数目称作路径长度。

    图中二叉树a中,跟节点到D的路径长度就是4,b中根节点到D的路径长度为2。

    树的路径长度就是从树根到每一个节点的路径长度之和。二叉树a的路径长度就为1+1+2+2+3+3+4+4=20。二叉树b的树路径长度就为1+2+3+3+2+1+2+2=16。

    如果考虑带权的节点,节点的带权的路径长度就是从该节点到树根之间的路径长度乘该节点的权。

    数的带权路径长度就是所有叶子节点的带权路径长度之和。

    带权路径长度(WPL)最小的二叉树称作哈夫曼树。

    ###如何构造哈夫曼树

    下面我们以【5、8、4、11、9、13】为例来画出哈夫曼树(数字大小代表权重大小,越大的权重越大)

    第一步:按从小到大排序。

    【5、8、4、11、9、13】→【4、5、8、9、11、13】

    第二步:选最小两个数画出一个树,最小数为4和5。

    给定的4、5、8、9、11、13为白色, 红色的9为4+5,与给定的白9无关,新序列为:【红9(含子节点4、5)、8、9、11、13】

    7c32921730e11bf4bbcd3d27c9b22767.png

    ####之后一直重复第一、第二步:排序然后取两个最小值。实际就是一个递归过程

    排序:

    427752598b7e8bb28559faf6dcbad286.png

    取两个最小数8和9:

    88301ca443a1051d66f1f46521af7b89.png

    排序

    1737bb7a7aa7bf7d77408aa4426a7797.png

    区两个最小数11和9

    bb816ae09eb87a575a611687ad4ef4f2.png

    排序,然后取两个最小数13和17:

    9fe015ce56c7a4c6734d7d0931184813.png

    取两个最小数20和30:

    9fb61279d0b9f2ea5b5734649302d171.png

    展开全文
  • 哈夫曼编码

    2015-01-17 21:54:16
    用matlab写的 自编哈夫曼编码程序 输入为向量且和为1
  • 哈夫曼编译码

    2020-04-11 15:08:08
    在信息传输等实际应用中,需将...利用哈夫曼树可以得到平均长度最短编码,因此,在信息传输、数据压缩等方面,哈夫曼树有着广泛的应用。 相关概念 等长编码:每个字符的编码长度相同。 不等长编码:使用频率高的...
  • 信息熵是最小平均编码长度

    千次阅读 2019-02-16 20:05:00
    如何理解最后一句话呢,编码信息熵就是平均最小编码长度? 信息熵就是平均最小编码长度 信息熵想用最短的码表示信息。 熵公式,有数学期望,对概率求对数,表示单符号的信息量。 所以信息熵的期望就是平均...
  • 2016复旦大学计算机复试上机第三题——求哈夫曼编码最短长度 题目:给定一个字符串,求哈夫曼编码最短长度: 思路1:统计每个字符出现的字数,然后构建哈弗曼树,计算每个叶子的权值和路径长度的乘积之和。 ...
  • 最短平均码长(信息熵 香农提出) 平均码长 信息冗余量 哈夫曼码设计原则: 1.如果指令的字长固定,那么地址码越长,操作码越短 2.如果指令的字长可变,以指令使用频度为依据,使用频度高的指令用短操作码 使用频度低...
  • 哈夫曼编码(Huffman)

    2016-07-22 19:31:00
    今天看数据结构,看到哈夫曼编码。感觉挺有意思的。哈夫曼树的应用应该很多吧,还刚学,以后多深入看看。 #include <iostream> #include <cstdio> #include <stack> #include <algorithm...
  • else//访问到非叶子结点时分别向左右子树递归调用,并把分支上的0、1编码保存到数组a { //的对应元素中,向下深入一层时len值增1 return HuffManCoding(FBT->left, len + 1)+ HuffManCoding(FBT->right, len ...
  • 编码概念

    2020-01-29 16:28:27
    信息的熵为信源无损编码平均码长的下限(最短码长) 公式理解:编码一个符号的最佳bit长度是-logP,P是这个符号出现的概率;一段信息的长度就是所有符号长度求期望。 熵编码的基本思想: 尽可能的减少信源的冗余...
  • MATLAB实现霍夫曼编码

    2017-12-26 19:41:43
    霍夫曼编码依据字符出现的概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,其优越的性能被广泛使用在数字通信系统中。霍夫曼编码已经成为数据压缩的灵魂算法。本文介绍了无失真编码算法的构造,霍夫曼...
  • 编码所有符号S平均所需要的位数 那什么是熵编码?在信息熵的极限范围内进行编码就是熵编码。例如信息熵算出来是3bit/字符,你用4bit/字符来编码,就是熵编码,你用2bit/字符来编码,就不叫熵编码,因为这种情况下,...
  • 【贪心算法】哈夫曼编码问题

    千次阅读 多人点赞 2020-05-09 21:47:11
    哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。一个包含100,000个字符的文件,各...
  • 哈夫曼编码(Huffman Coding),是一种熵编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般...
  • 香农编码 哈夫曼编码 费诺编码的比较文章目录哈夫曼编码编码步骤例子优点缺点费诺编码编码步骤例子优点缺点香农编码编码步骤例子优点缺点参考备注:本文除了例子与数据,其他内容均为整合网络资源。哈夫曼编码编码...
  • 完全的哈夫曼编码是最优化的编码。但是这种编码的码长种类太多。如上表,7种指令就出现了4种码长,长度有1有2有3有5,不规整,不易于编码。为此,结合用一般的二进制编码,在哈夫曼编码的基础上进行扩展。
  • java实现哈夫曼编码

    2021-02-26 12:27:40
    java实现哈夫曼编码哈夫曼树...哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 哈夫曼编码在日常计算机的使用中,我们一定会出现下面这种情况:假如给定a、b、c、d、e五个字符,它们在文本中出现的概...
  • 信息论与编码

    千次阅读 2020-10-08 15:18:16
    编码是后人沿着香农指明的可行方向,为寻求有效而可靠的编译方法而发展起来的一门学科,主要研究在有噪信道条件下各种可行的编码方案及实施技术。 信息论 信息是什么? 信息是确定性的增加,信息的度量(熵)是信息不...
  • Xilinx哈夫曼编码 对一段数据序列进行哈夫曼编码,使得平均码长最短,输出各元素编码编码后的数据序列。 1. 设计要求 (1)组成序列的元素是[0-9]这10个数字,每个数字其对应的4位二进制数表示。比如5对应0101,9...
  • 哈夫曼编码的理论依据是变字长编码理论。在变字长编码中,编码器的...可以证明,按照概率出现大小的顺序,对输出码字分配不同码字长度的变字长编码方法,其输出码字的平均码长最短,与信源熵值最接近,编码方法最佳。
  • 信息论第8讲最佳不等长编码最佳不等长编码 第8讲 Fano编码 为使选出平均码长最小,自然想到:从每个节点出发的D种可能的分支出现的概率近于相等,Fano给出一种近于最佳的无失真不等长编码方法。 Fano编码:首先,将...
  • R元HuffMan编码的MATLAB实现R元HuffMan编码的MATLAB实现张月华 崔文超 ...这些编码平均长度接近于信源的熵。3. 算法及实现本算法的r元编码过程实现如下:(1)将q个信源按概率分布大小依递减次序排列:;(2...
  • 熵和编码长度

    2016-10-05 10:22:00
    信息论中,熵代表着根据信息的概率分布对信息编码所需要的最短平均编码长度。 举个简单的例子来理解一下这件事情:假设有个考试作弊团伙,需要连续不断地向外传递4选1单选题的答案。直接传递ABCD的ascii码的话,每个...
  • 信息熵与压缩编码基础
  • 哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 理解: 举个栗子:假如你有一个衣柜里面有ABCDEF共6件衣服,但是每个衣服穿的频率都是不一样的,54%(问就是喜欢穿),10%,6%,3%,7%,20% 那么现在...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 660
精华内容 264
热门标签
关键字:

平均码长最短的编码是