哈弗曼编码方法和香农编码方法的理论依据

霍夫曼编码的基本思想：输入一个待编码的串，首先统计串中各字符出现的次数，称之为频次，假设统计频次的数组为count[ ]，则霍夫曼编码每次找出count数组中的值最小的两个分别作为左右孩子，建立他们的父节点，循环这个 *** 作2n-1-n（n是不同的字符数）次，这样就把霍夫曼树建好了。建树的过程需要注意，首先把count数组里面的n个值初始化为霍夫曼树的n个叶子节点，他们的孩子节点的标号初始化为-1，父节点初始化为他本身的标号。接下来是编码，每次从霍夫曼树的叶子节点出发，依次向上找，假设当前的节点标号是i，那么他的父节点必然是myHuffmantree[i]parent，如果i是myHuffmantree[i]parent的左节点，则该节点的路径为0，如果是右节点，则该节点的路径为1。当向上找到一个节点，他的父节点标号就是他本身，就停止（说明该节点已经是根节点）。还有一个需要注意的地方：在查找当前权值最小的两个节点时，那些父节点不是他本身的节点不能考虑进去，因为这些节点已经被处理过了

香农第一定理(可变长无失真信源编码定理)

设离散无记忆信源X包含N个符号{x1,x2,…,xi,,xN}，信源发出K重符号序列，则此信源可发出N^k个不同的符号序列消息，其中第j个符号序列消息的出现概率为PKj，其信源编码后所得的二进制代码组长度为Bj，代码组的平均长度B为

B=PK1B1+PK2B2+…+PKN^kBN^k

当K趋于无限大时，B和信息量H(X)之间的关系为BK=H(X)(K趋近无穷）

香农第一定理又称为无失真信源编码定理或变长码信源编码定理。

香农第一定理的意义：将原始信源符号转化为新的码符号，使码符号尽量服从等概分布，从而每个码符号所携带的信息量达到最大，进而可以用尽量少的码符号传输信源信息。

香农第二定理（有噪信道编码定理）

有噪信道编码定理。当信道的信息传输率不超过信道容量时，采用合适的信道编码方法可以实现任意高的传输可靠性，但若信息传输率超过了信道容量，就不可能实现可靠的传输。

设某信道有r个输入符号，s个输出符号，信道容量为C，当信道的信息传输率R<C，码长N足够长时，总可以在输入的集合中(含有r^N个长度为N的码符号序列)，找到M （(M<=2^(N(C-a)))，a为任意小的正数)个码字，分别代表M个等可能性的消息，组成一个码以及相应的译码规则,使信道输出端的最小平均错误译码概率Pmin达到任意小。

香农第三定理（保失真度准则下的有失真信源编码定理）

保真度准则下的信源编码定理，或称有损信源编码定理。只要码长足够长，总可以找到一种信源编码，使编码后的信息传输率略大于率失真函数，而码的平均失真度不大于给定的允许失真度，即D'<=D

设R(D)为一离散无记忆信源的信息率失真函数，并且选定有限的失真函数，对于任意允许平均失真度D>=0，和任意小的a>0，以及任意足够长的码长N，则一定存在一种信源编码W，其码字个数为M<=EXP{N[R(D)+a]}，而编码后码的平均失真度D'(W)<=D+a。

请采纳。

费诺编码结果不唯一的原因是

将信源符号按照概率大小进行递减排序。将一组信源符号分成概率之和尽可能相等的两组，将上面的一组编码为0，下面一组编码为1（反之亦可）。重复该步骤，直至不能分组。费诺编码属于概率匹配编码，编码方法不唯一。但一般也不是最佳的编码方法，只有当信源的概率分布呈现p(ai)=sli分布形式的条件下，才能达到最佳码的性能。

[优点]：该编码考虑了信源的统计特性，使概率较大的信源符号能对应码长较短的码字，较之香农编码一定提升了编码效率。

[缺点]：它不一定是最佳码。当信源符号较多时，有一些符号概率比较接近，使分组变多码长也随之增加，编码过程复杂，有时短码未必能得到充分利用。

[应用]：费诺编码在电子计算机、电视、遥控和通讯等方面广泛使用。

计算机上压缩的概念最早是在1942年由美国贝尔实验室的著名数学家克劳德· 埃尔伍德· 香农提出的。他认为现在的计算机程序基本都存在信息冗余，通过一些方法对程序进行修改，将可以有效减少它们的容量大小，并且发布了一个名为"香农编码"的压缩方法。但是这个压缩方法离真正的可用还差得很远。

1952年，一个名为哈夫曼的年轻人在麻省理工学院读书，但是他并不喜欢上课，于是他询问自己的计算机老师，自己怎么样才能不去上课，老师要求他给出一个具有说服力的设计。于是哈夫曼回到宿舍，设计了一个用来压缩计算机文件的算法拿到了老师面前，瞬间征服了他的老师，随后也征服了世界。这个为了不上课而设计出来的压缩算法被称为哈夫曼编码，成为了现在各种压缩算法和软件的基础。

在哈夫曼编码出现后的几年，网络出现了，软件也在高速发展，但是计算机储存容量的发展却出现了瓶颈，有时候安装一个软件甚至需要十张软盘，人们对压缩软件出现了巨大的需求。许多商业公司推出了压缩软件进行销售，只是这些压缩软件压缩速度慢、价格昂贵，并没有真正的流行起来。这时，又一位天才出现了，他的名字叫菲利普·卡兹。

在1988年菲利普·卡兹迷恋着上网逛BBS论坛，但是此时的网络速度非常慢，即使只是纯文字也需要等待很长时间进行传输。于是很多人都会使用压缩软件将文字进行压缩，再上传到网上。菲利普·卡兹在找到当时美国最多人购买的压缩软件ARC时，觉得这东西又差又贵，不应该进行收费。于是他在业余时间模仿ARC开发了一个名为PKARC的压缩软件，免费发布到了网络上。

虽然当时PKARC不见得比ARC好用，但是在免费的吸引力下人民群众毫不犹豫地选择了PKARC。利益受损的ARC公司非常生气，向法院提起了诉讼，法院判决菲利普·卡兹侵犯了ARC公司的权益，要求菲利普·卡兹不得再继续开发和传播PKARC。这回，轮到菲利普·卡兹不开心了，他回到了家中，花费两周的时间，总结了哈夫曼等前辈们的经验，研究出了属于自己的压缩算法，并且开发了压缩软件PKZIP，这也是我们现在常用的压缩软件WinZip的前身。

和PKARC一样，PKZIP同样完全免费开放给了所有人。更好的质量和免费让这个软件迅速占领市场，曾经与他争斗的ARC就此消失在了历史的长河中，压缩软件真正的流行了起来，菲利普·卡兹成为了压缩软件和计算机界的英雄。PKZIP的出现为菲利普·卡兹赢得了尊重，却没有为他赢得面包。2004年，穷困潦倒的菲利普·卡兹被发现因过度酗酒死在了一家廉价酒馆内，结束了他的传奇人生，此后虽然与压缩的原则相违背，但每个Zip文件编码的开头都会写上他的名字缩写"PK"。

香农编码是是采用信源符号的累计概率分布函数来分配字码的。香农编码是根据香农第一定理直接得出的，指出了平均码长与信息之间的关系，同时也指出了可以通过编码使平均码长达到极限值。香农第一定理是将原始信源符号转化为新的码符号，使码符号尽量服从等概分布，从而每个码符号所携带的信息量达到最大，进而可以用尽量少的码符号传输信源信息。

香农编码属于不等长编码，通常将经常出现的消息变成短码，不经常出现的消息编成长码，从而提高通信效率。 香农编码严格意义上来说不是最佳码，它是采用信源符号的累计概率分布函数来分配码字。

编码步骤如下：

(1)将信源符号按概率从大到小顺序排列，为方便起见，令

；

(2)按

计算第i个符号对应的码字的码长(取整)；

(3) 计算第i个符号的累加概率 ；

(4)将累加概率变换成二进制小数，取小数点后 位数作为第i个符号的码字。

香农编码的效率不高，实用性不大，但对其他编码方法有很好的理论指导意义。一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的。即不是紧致码(最佳码)。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高。

符号概率为2的负幂次方。香农编码效率何时能达到100%是因为符号概率为2的负幂次方，诺编码同样能够达到100%的编码效率。香农编码的理论基础是符号的码字长度N完全由该符号出现的概率来决定。

香农第一定理(可变长无失真信源编码定理)

设离散无记忆信源X包含N个符号{x1,x2,…,xi,,xN}，信源发出K重符号序列，则此信源可发出N^k个不同的符号序列消息，其中第j个符号序列消息的出现概率为PKj，其信源编码后所得的二进制代码组长度为Bj，代码组的平均长度B为

B=PK1B1+PK2B2+…+PKN^kBN^k

当K趋于无限大时，B和信息量H(X)之间的关系为BK=H(X)(K趋近无穷）

香农第一定理又称为无失真信源编码定理或变长码信源编码定理。

香农第一定理的意义：将原始信源符号转化为新的码符号，使码符号尽量服从等概分布，从而每个码符号所携带的信息量达到最大，进而可以用尽量少的码符号传输信源信息。

以上就是关于哈弗曼编码方法和香农编码方法的理论依据全部的内容，包括:哈弗曼编码方法和香农编码方法的理论依据、费诺编码结果不唯一的原因、电脑什么压缩软件好用等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！