哈夫曼编码和二进制编码优缺点比较

比较如下：

1、码字不同。

哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以他的优点是编码效率唯一性。而二进制编码所构造的码字是唯一。

2、长度不同

哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字，比较精准，二进制编码是用预先规定的方法将文字、数字或其他对象编成二进制的数码，或将信息、数据转换成规定的二进制电脉冲信号。二进制是最基础的编码。

3、稳定性不同

哈夫曼编码的稳定性比较差。如果改变其中一位数据就会产生改变。二进制编码具有抗干扰能力强，可靠性高等优点。

参考资料来源：百度百科-哈夫曼编码

参考资料来源：百度百科-二进制编码

给你一段程序,自己研究下吧!\x0d\\x0d\clc\x0d\clear\x0d\closeall;\x0d\%定义HufData/Len为全局变量的结构体\x0d\globalHufData;\x0d\globalLen\x0d\disp('计算机正在准备输出哈夫曼编码结果,请耐心等待');\x0d\%原始码字的灰度\x0d\a=imread('kidstif');\x0d\\x0d\%分区画出原始图像和灰度直方图\x0d\figure;\x0d\subplot(1,2,1)\x0d\imshow(a);\x0d\%取消坐标轴和边框\x0d\axisoff\x0d\boxoff\x0d\title('MATLAB自带图像','fontsize',13);\x0d\subplot(1,2,2);\x0d\axisoff\x0d\boxoff\x0d\imhist(a);\x0d\title('图像灰度直方图','fontsize',13);\x0d\%图像的灰度统计\x0d\GrayStatistics=imhist(a);\x0d\GrayStatistics=GrayStatistics';\x0d\GrayRatioo=GrayStatistics/sum(GrayStatistics);\x0d\GrayRatioNO=find(GrayRatioo~=0);\x0d\Len=length(GrayRatioNO);\x0d\%初始化灰度集，防止系统随即赋予其垃圾值\x0d\GrayRatio=ones(1,Len);\x0d\\x0d\fori=1:Len\x0d\GrayRatio(i)=GrayRatioo(i);\x0d\end\x0d\\x0d\GrayRatio=abs(sort(-GrayRatio));\x0d\%将图像灰度概率赋予结构体\x0d\fori=1:Len\x0d\HufData(i)value=GrayRatio(i);\x0d\end\x0d\\x0d\%哈夫曼编码/霍夫曼编码\x0d\HuffmanCode(Len);\x0d\%输出码字\x0d\\x0d\zippedHuffman=1;\x0d\fori=1:Len\x0d\tmpData=HufData(i)code;\x0d\str='';\x0d\forj=1:length(tmpData)\x0d\str=strcat(str,num2str(tmpData(j)));\x0d\zippedHuffman=zippedHuffman+1;\x0d\end\x0d\disp(strcat('a',num2str(i),'=',str))\x0d\end\x0d\i;\x0d\%计算计算机一共输出多少个哈夫曼编码/霍夫曼编码\x0d\zippedHuffman;\x0d\%计算在删去0灰度级压缩之前的原始图像字节容量\x0d\unzipped_delete=i8;\x0d\\x0d\%计算压缩比率\x0d\ratio_delete=zippedHuffman/unzipped_delete;\x0d\\x0d\%计算图像的压缩比率\x0d\ad=num2str(ratio_delete100);\x0d\str2=strcat(ad,'%');\x0d\disp(strcat('哈夫曼编码压缩比率','=',str2))\x0d\\x0d\%子程序：哈夫曼编码/霍夫曼编码函数HuffmanCodem\x0d\functionHuffmanCode(OriginSize)\x0d\globalHufData;\x0d\globalLen\x0d\fori=1:Len\x0d\%%霍夫曼编码树左边纪录为1\x0d\HufData(i)left=1;\x0d\%%霍夫曼编码树右边纪录为0\x0d\HufData(i)right=0;\x0d\%%输出码初始化为0\x0d\HufData(i)code=[];\x0d\%%排序列表初始化\x0d\SortList(i)symbol=i;\x0d\SortList(i)value=HufData(i)value;\x0d\end\x0d\%初始化原始消息数目\x0d\newsymbol=OriginSize;\x0d\forn=OriginSize:-1:2\x0d\%将N个消息进行排序\x0d\SortList=sortdata(SortList,n);\x0d\%将最后两个出现概率最小的消息合成一个消息\x0d\newsymbol=newsymbol+1;\x0d\HufData(newsymbol)value=SortList(n-1)value+SortList(n)value;\x0d\HufData(newsymbol)left=SortList(n-1)symbol;\x0d\HufData(newsymbol)right=SortList(n)symbol;\x0d\%将消息添加到列队的最后，为N-1个消息重新排序作好准备\x0d\SortList(n-1)symbol=newsymbol;\x0d\SortList(n-1)value=HufData(newsymbol)value;\x0d\end\x0d\%遍历霍夫曼树，获得霍夫曼编码/哈夫曼编码\x0d\visit(newsymbol,Len,[]);\x0d\end\x0d\\x0d\%子程序：冒泡排序法函数sortdatam\x0d\functionreData=sortdata(SortList,n)\x0d\%根据消息概率进行排序\x0d\fork=n:-1:2\x0d\forj=1:k-1\x0d\min=SortList(j)value;\x0d\sbl=SortList(j)symbol;\x0d\if(min0)\x0d\%遍历左分支接点输出1，这里采用子函数嵌套调用\x0d\ocode1=[ocode1];\x0d\visit(HufData(node)left,n,ocode1);\x0d\end\x0d\if(HufData(node)right>0)\x0d\%遍历右分支接点输出0，这里采用子函数嵌套调用\x0d\ocode2=[ocode0];\x0d\visit(HufData(node)right,n,ocode2);\x0d\end\x0d\end\x0d\end

本文主要介绍一下霍夫曼编码，

Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码

先说一下背景，编码的含义：
给出定义：
待编码字符集S：待编码的字符的集合
待编码序列s：一个字符序列，其中每个字符来自带编码字符集

编码字符集S'：用于编码的字符的集合
编码方法：对S中的每个字符，给定一个唯一对应的序列，其中序列中每个字符来自S'

举例来说：
S={a,b,c,d,f} 可以是一个 待编码字符集
abbcdaf 是一个待编码序列

S'={0,1} 是一个编码字符集
编码可以理解为一个映射关系，比如
a -> 0
b -> 1
c-> 01
d-> 10
f->001

那么编码方法可以看成一个函数，实际上的编码过程，就是
把序列s中的字符，依次按照编码方法映射为编码字符序列的过程；
比如 abbcdaf 经过上述编码方法编码后变为：
01101100001

如果编码字符集S' ={0,1} ，则称为2进制编码；

编码长度：对于待编码序列s;其中每个字符经过编码方法编码后，所得到的的最终序列的总长度

其中因为 可能是相同字符，它们对应的l也相等；
进一步，可以求出相对长度，其实就是 ， 表示编码序列的总长度；因此，如果某个字符在 中出现的频率为
则编码相对长度公式如下:
i遍历所有不同的字符集合，后文中不加说明都是指相对长度

以上就是编码定义；

下面介绍两种编码方式，
定长编码，不定长编码；
定长编码很好理解：每个字符经过编码方法之后的映射字符序列都是固定长度的；不定长就是长度不固定；
上述范例中的是不定长编码；

下面说说定长和不定长的区别：
首先，编码就意味着要解码，对于定长来说，只要编码方法和固定长度的大小，解码相当容易，隔固定间隔读取，再做逆向映射就ok了；

但对于不定长编码，可能出现冲突；

比如 a编码为 0
b编码为1
c编码为01

此时如果我收到一个编码后的序列为 01,
那么有两种可能，原序列为ab 或者原序列为c,这两种都合理，将无法正确解码；

不定长既然有这种缺陷，为何实际编码还是用不定长，原因就是不定长编码能够节省空间；
举例来说，如果有8个不同字符，用定长编码，每个字符的编码长度至少为3；( )
但如果不定长编码，可以少一些，后文中将会给出一个例子；

那么不定长编码的缺陷怎么解决，我们发现之所以出现上述缺陷，一个主要原因在于，某些编码恰好是另外一个编码的前缀；
比如0是 01的前缀，如果不定长编码可以保证编码后的字符序列中没有一个是另外一的前缀，则这个问题就可以解决了；

满足这种条件的编码叫做前缀编码；
当然即使不是前缀编码，有没有办法让它可以正确解码，也是有的，但是这里为了简化先不讨论这种情况；

下面给出最优编码的定义；
就是给定一个序列，设计一种不定长编码方法，使得这个序列按照这个编码方法编码后的长度最小；（前提当然是要可以正确解码）
可以证明（略）最优编码方式可以在前缀编码中取到，因此我们可以只考虑前缀编码中的最优方式；

那么具体的最优编码是什么，就是本文主题，霍夫曼编码，就是最优前缀编码（也是最优编码）

在讲解霍夫曼编码之前，先说一下编码树的概念：
我们只考虑2进制编码，
显然大家都知道2叉树，
那么如果我给定一个完全无穷极2叉树，根节点不放值，左节点存0，右节点存1，
则任何一种2进制编码比如 0100101,我们可以把它在该树中的路径画出来；经历过的节点标上记号；
对于所有字符的所有编码，我们把这些路径上的节点全部标上记号（已经有的不用重复标记）
之后把这个无穷2叉树剪裁，只保留那些标记颜色的节点，得到一个2叉树，这个树，就是该编码的编码树；
比如我们上面的demo，这个树长这样:

我们有些节点打上了括号，表示这个节点对应的路径对应着一个编码，从图中可以看出，显然前缀编码意味着所有打括号的节点都是叶子节点，（这是因为叶子节点一定有括号，这一点是显然的，如果有不是叶子节点的节点右括号，它下面的叶子节点也有括号，便和前缀编码相矛盾了）

这样每一种编码，尤其是前缀编码，都可以用一个编码树来描述，前缀编码的编码树连括号都不需要用，因为默认都在叶子节点，则一个编码树（无括号）可以完全对应一种前缀编码

有了以上基础，我们来描述，霍夫曼编码，显然只需要把它的编码树结构描述清楚，霍夫曼编码也就描述清楚了，霍夫曼编码的编码树构造方法如下：
1，输入序列s,
首先计算s中出现的每个字符出现的频率，并且按照从小到大排序；
2，找到最小的两个，分别赋值0,1作为左右2个节点，并生成其父节点，其值取为两者的和，（这一次 *** 作称为合并）
3，从S中去掉这两个字符，把这个父节点看成一个新字符加入到S中，其对应频率为两者的合，再重复上述过程，
4，如果在生成节点的过程中发现某个字符是新生成的，则直接拿这个字符对应的节点来用并保留其子节点

下面举个例子:
a:10 b:3 , c: 5 d:1
这是出现频率
先取 b,d 标记为0，1
合并频率为 4(新字符记录为bd),变为
a:10 bd:4 c:5
再去bd 和 c 合并，新字符可记为c'，频率为9，最后和a合并；
对应树如下:

这个树对应的就是霍夫曼编码，除了叶子节点是原字符集中的，其余的是新生成的中间字符不用考虑；
编码如下:
a :1
b:000
c:01
d:001
长度计算公式为:

那么这个编码方式的编码长度为何最短

终于可以说的全文最关键的部分，下面给出一个简明的证明：
首先，给出几个引理：
1，最优编码下，频率越小的字符编码必然越长
证明：如果不是这样，比如字符x的频率fx < 字符y的频率fy
并且它们在树中的路径长度（编码长度）lx<ly
显然，我们可以交换这两个字符在树中的位置（也就是交换它们的编码方式）得到一个新的前缀编码方式，
由于其他的不变，考虑这两者的编码长度差：就是
fx lx+fy ly-(fx ly+fy lx) = (lx-ly)(fx-fy) >0,说明后者的编码长度更小
矛盾；
2，最优编码下，频率最小的那两个字符的编码长度相等
证明：根据1，如果不是这样，则频率最小那个字符将有一个独一无二的最长的编码路径l，那么我们可以调整编码方式，把字符编码（对应某个叶子节点）的父节点作为其编码,并去掉该节点，那么这个新的叶子节点对应的路径必然不是其他字符编码的前缀，这是因为其他的长度l'<=l-1,如果新叶子节点是其他字符编码的前缀，则只有一种可能l'=l-1，这意味着这个其他字符的编码就是该编码，那它就是原来的最优编码的那个节点的前缀，矛盾；
同时其他编码不是它的前缀是显然的；

现在我们看霍夫曼编码方式：
首先从构造方式可以看出满足引理2，之后，那么意味着求最优编码长度的公式： 不妨设 就是频率最小的两个，则它们长度一定相等
公式变为:
从公式即可看出，该式子对应一个新的霍夫曼编码问题，也就是上文中去掉 1,2号字符，引入一个新的频率对应 的字符的编码问题；原来的最小值一定在新的和取最小值时取到；
这是因为：
新字符的频率为 ,因此实际上最优编码对应方程为:

也就是求满足条件的编码使得上式最小；
显然如果找到了这个编码，
对于原编码来说:
显然也取到最小值，因为两个式子完全相等（ 是大前提）

并且一旦新编码是前缀码，1,2号生成的节点增加两个孩子，再去掉该节点编码这一 *** 作，不会影响前缀码的正确性；

这样就证明了霍夫曼编码是最优编码；
实际上本文不单证明了霍夫曼编码是最优编码，实际上是给出了构造最优编码的思路，顺着该思路设计编码方式就自然而然的导出霍夫曼编码，

为了理解熵，必须讲一点物理学。

19世纪，物理学家开始认识到，世界的动力是能量，并且提出"能量守恒定律"，即能量的总和是不变的。但是，有一个现象让他们很困惑。物理学家发现，能量无法百分百地转换。比如，蒸汽机使用的是热能，将其转换为推动机器的机械能。这个过程中，总是有一些热能损耗掉，无法完全转变为机械能。一开始，物理学家以为是技术水平不高导致的，但后来发现，技术再进步，也无法将能量损耗降到零。 他们就将那些在能量转换过程中浪费掉的、无法再利用的能量称为熵。后来，这个概念被总结成了"热力学第二定律"：能量转换总是会产生熵，如果是封闭系统，所有能量最终都会变成熵。

熵既然是能量，为什么无法利用？它又是怎么产生的？为什么所有能量最后都会变成熵？这些问题我想了很久。物理学家有很多种解释，有一种我觉得最容易懂：能量转换的时候，大部分能量会转换成预先设定的状态，比如热能变成机械能、电能变成光能。但是，就像细胞突变那样，还有一部分能量会生成新的状态。这部分能量就是熵，由于状态不同，所以很难利用，除非外部注入新的能量，专门处理熵。总之，能量转换会创造出新的状态，熵就是进入这些状态的能量。

现在请大家思考：状态多意味着什么？状态多，就是可能性多，表示比较混乱；状态少，就是可能性少，相对来说就比较有秩序。因此，上面结论的另一种表达是： 能量转换会让系统的混乱度增加，熵就是系统的混乱度。 转换的能量越大，创造出来的新状态就会越多，因此高能量系统不如低能量系统稳定，因为前者的熵较大。而且，凡是运动的系统都会有能量转换，热力学第二定律就是在说，所有封闭系统最终都会趋向混乱度最大的状态，除非外部注入能量。

熵让我理解了一件事，如果不施加外力影响，事物永远向着更混乱的状态发展。比如，房间如果没人打扫，只会越来越乱，不可能越来越干净。

不清楚题主的学科背景，以下回答面向从未系统学习热力学和信息论的朋友，从三个层次讨论“熵”的意义——这其实也是这个概念本身发展的历程。文字有些长，性急的同学可以直接看最后的总结。

“熵”是一个十分古老的概念，可以上溯至蒸汽时代人们对热机的研究。和热量、温度等其他热力学概念相比，它的确因抽象而难以理解。为避免读者被公式和其它概念吓到，我们从大家喜闻乐见的“永动机”的故事开始。

我们都知道，第一类永动机（即不消耗能源却可以不断对外做功的机器）因为违反能量守恒定律所以是不存在的。但不甘心的工程师们很快又设想出了另一种神奇的机械，被称为第二类永动机。由于它过于神奇，为了理解它，我们必需先研究一艘正常的船。

假设这艘船的动力系统是一座蒸汽机，当它工作的时候，煤在锅炉里燃烧，释放它的化学能变为热能，然后再经卡诺循环转化为船的机械能。而船在航行的时候，又要不断克服水的阻力做功，机械能转化为水的内能。所以在船匀速航行的情况下，煤燃烧释放的能量最终转化为了水的内能（也许表现为使海水的温度上升了一亿亿分之一摄氏度）。而我们为了保持船的航行，只能不断地烧煤。

而如果我有一艘新船，它有一个棒棒的动力系统，能直接从海水里吸收能量，并完全转化为船的机械能。这样一来，我们就能见证一个奇迹：船从海水里获得能量，航行时克服水的阻力做功，又把能量还给海——在这个过程中船和海的总能量没有变多也没有变少，因此丝毫不违反能量守恒定律——然而它不需要烧一粒煤就能环游世界。

这当然是不可能的。但是为了证明这个“不可能”，当时的科学家付出了很多的努力。最终，鲁道夫·克劳修斯发现，任何可以自发进行的过程中，恒温热Q和温度T的比值永远是一个正值。

克劳修斯是德国人，便用德语Entropie命名这个比值，直到几十年后南京大学的胡刚复教授才将这个概念引入国内，并命名为“熵”（意指Q和T的商数）。由定义式我们不难知道，它的量纲是J/K。

熵就像一个固执的沙漏，能量每进行一次转化，它就向前走一点，而它每向前走一点，能量被利用的能力就减少一点。这个过程犹如时间流逝、人的衰老一样不能逆转。这也就是著名的熵增原理：任何孤立系统的总熵不会减少。如果说能量守恒定律限定了能量的数量，那么熵增原理就限定了能量的质量：较优质的能量可以完全转化为较劣质的能量，但较劣质的能量却不可能完全转化为较优质的能量。比如一根简单的电阻丝就能把电能完全转化为热能，但最先进的发电机也不可能把这些热能重新转变为等量的电能。这就是第二类永动机不能实现的原因——机械能是比内能优质的能量，所以直接从海水里吸收热量，并完全转化为船的机械能的装置压根就不存在。

1877年，玻尔兹曼提出了著名的玻尔兹曼原理：S=klnΩ。也就是熵的微观形式，其中的k是玻尔兹曼常数，量纲为J/K，由于后面对数项不具量纲，所以玻尔兹曼熵的量纲也是J/K，这是证明它和宏观形式等价的前提。

公式中的Ω是微观状态数，即微观上构型的所有可能的排列数。Ω有时也被理解成“混乱度”，这是合理的。因为作为越有规律的系统，构型就越少，而混乱的系统可以有较多个构型。例如，设想有一组10个硬币，每一个硬币有两面，掷硬币时得到最有规律的状态是10个都是正面或10个都是反面，这两种状态都只有一种构型（排列）。反之，如果是最混乱的情况，有5个正面5个反面，排列构型可以有 =252种。（这个例子摘自维基百科）

这也形成了熵最广为人知的理解： 熵是系统混乱度（无序程度）的量度。 其实，由于宏观系统的Ω是一个天文数字，以至于我们往往无法计算，所以实际应用中熵的微观描述远不如宏观描述常见。但由于我们处在一个看脸的世界，连物理定律也不能例外，这种金光闪闪的表达式和解释比土里土气的宏观描述容易流传太多了（同样可以解释为什么 这种东西连幼儿园小朋友都知道）。

其实我觉得玻尔兹曼原理反过来想更令人震撼——对于一个系统，如果某一时刻它的熵确定，那么它可能的微观状态数也是一定的。如果这个系统是整个宇宙的话，这就意味着我们这个世界的可能性也是有限的（尽管非常非常多）……OMG！我要去看女神自拍压压惊了。另外需要注意的是，熵的微观形式是直接和状态数Ω对应的，因此是一个绝对值而非相对值。而由于Ω是自然数，所以熵一定非负；特别的，绝对零度下的晶态物质Ω为1，所以S=kln1=0，这也就是热力学第三定律。
以上两种熵都叫做“热力学熵”，因为它们的等价性已经被证明。

信息熵的来历和热力学熵完全不同。把它也叫做“熵”完全是因为香农老爷子当年提出这个概念时参考了热力学熵，并且它的表达式和热力学熵的微观形式非常相似（但和宏观描述看不出任何相似性）的缘故。后来也有人提出了信息熵的其他表述形式，为了方便，下文以最早也最重要的香农熵为准。信息熵的表达式:H=-ElnP(x) 其中E是期望，P(x)是出现的概率（含义下面会提到）。大家发现了吧，它和玻尔兹曼熵表达式S=klnΩ形式完全一样，只有常数上的差别。实际应用中，为了对应二进制数，更常见的是以2为底的形式： ，此时结果的量纲为比特。

它的意义非常明确，指观察者对某一事件（结果）的未知程度。举个例子：我要抛一次骰子，在观测到结果之前，骰子六个面向上都有可能，而且概率完全一样（都是1/6)这时，这一事件的信息熵为 。现在万能的女神给了我一个提示，这次骰子的结果一定是偶数，于是可能的结果由6种降低为3种，事件的熵也就变成了 。也就是说，当我得到提示后，对于事件结果的不确定性降低了。我们把信息熵降低的量规定为信息量I。上面那条提示对我的信息量是 ，正好是1比特，相当于对一个完全未知的命题做一次是非判断需要的信息量。而如果我要得到唯一确定的结果，P(x)就必须等于1，此时的信息熵为零。我们需要得到的信息量就是原本的熵 。

看到这里，聪明的你一定已经可以自己总结出另一个金光闪闪的结论：信息就是负熵。需要特别注意的是，这句话里的“熵”指而且仅指信息熵，试图将这个结论扩大到热力学熵的解释往往都缺乏足够的事实基础，并且含义也经常是含混的。

我们再来看另一个例子：甲乙丙三个实力相当的运动员要进行一次比赛，老王是比赛的裁判和记分员，他必须观察并如实记录三位选手的名次。所以对于他来说，比赛结果有 =6种。由于运动员实力相当，每种结果出现的可能性一样，所以结果的熵是

小花是运动员甲的女朋友，她如此爱自己的男友以至于只关心他有没有取得冠军而完全不在意其它选手的成绩。对于小花来讲，比赛的结果只有两种，它的熵大约是092（计算略去，大家应该不会对数学计算感兴趣吧）。有的同学会奇怪，这里的熵为什么不是1？原因是由于甲乙丙三个运动员实力相当，所以甲获得冠军的几率只有1/3。也就是说如果小花足够聪明的话，在比赛前就可以知道甲获得冠军的可能比不获得冠军的可能小。这种预期降低了事件的未知程度（熵），也降低了结果对小花的信息量。

老李是比赛场地的管理员，他完全不关心谁胜谁负，而只想等到比赛结束下班回家，那么比赛对他的熵是多少呢？答案是零，因为他只关心比赛有没有结束，而比赛只要一开始就注定会结束，这个结果是唯一确定的。所以老李根本不用观察比赛，只要坐着等就可以了。

这个例子说明对于不同的观察者，由于目的和观测能力的差异，同一个事件的熵也可能是不同的。

我们再回头看老王的记分板，他用三组二进制数记录比赛结果。第一组记录甲的名次，第二组记录乙的名次，第三组记录丙的名次，由于名次有三个可能的值(第1第2第3)，每组二进制数都必需是两位的，所以老王对比赛结果的记录由六位二进制数构成。

老王的儿子小王是一个多才多艺的程序员，他看到了老王的记分板开始了吐槽：由于比赛只有三位选手，只要其中两位选手的名次确定第三位选手的名次也就确定了。因此第三组二进制数完全是没有必要的（我们也称它为冗余），老王只需要四位二进制数就能表示全部的信息。

老王十分羞愧，忙请教小王能否更加简洁。小王想了想，把所有六种可能的结果罗列了出来，并给每种情况赋予了一个代号，比如001表示甲乙丙的结果，010表示甲丙乙的结果……这样老王每次就只需要三位二进制数（3比特）就可以记录原本要6比特才能表示的信息了。 这个故事告诉我们，同样的信息用不同形式描述，会产生长度不同的记录（我们称之为消息），因此无损压缩是可能的。这也是清晰度差不多的视频文件有的格式卡成狗有的格式却十分流畅的原因。

故事的最后，老王贪心不足，希望用更短的消息来记录比赛结果，然而多次尝试之后可耻的失败了。这是因为比赛结果的熵是log2(6)，大约是258，因此至少需要3位二进制数（3比特）才能描述，即 消息不可能比它所包含的信息更短。也就是说无损压缩有其极限，判断这个极限是信息熵的另一个应用。

好了，我们现在总结一下，并试着回答题主的问题。

那么信息熵和热力学熵有什么区别和联系呢？

首先要说的是，信息熵和热力学熵是完全不同的两个概念。它们形成于不同的理论体系中，无论含义、量纲、研究对象、作用都不相同。据我所知，目前也没有成熟的理论揭示二者有实质上的联系。

那么为什么许多人把这两者联系在一起呢？我想最重要的原因就是二者的数学表达式实在太像了，以至于它们在数学上的性质也很类似，甚至可以把统计力学中研究热力学熵的方法直接移植到信息论中研究信息熵，这导致了“信息热力学”的建立。

其实除了信息熵之外，生态学家和社会学家也借鉴热力学熵，在各自领域中提出了类似概念。

看到有同学在追问，补充几点：

1我们理解一个概念时不应脱离产生这个概念的并使之发挥作用的理论体系。比如脱离热力学的框架谈热力学熵，或者脱离信息论的框架谈论信息熵在逻辑上都是脆弱的。

2如果要证明二者是一回事，不能只看形式是否相似，而是要通过严格的理论证明。而做到这一点的前提是必须有一套理论体系能够把二者都包括进去。比如热力学熵的两种形式等价是严格的理论计算证明了的，于是热力学和统计力学也就变成了一门统一的学科。而目前信息论和热力学并没有统一的迹象。

3前排回答中的某些计算，在我看来很明显是错误的。比如抛硬币的那个例子：原答主计算“抛硬币”系统的玻尔兹曼熵和香农熵，并认为二者是相等的。然而玻尔兹曼公式中的Ω意义很明确，就是微观状态数。它由系统的结构、温度、体积、质量等因素决定，是一个客观的物理量（它的取值不依赖于观测者）。而“抛硬币”是一个抽象的逻辑模型，显然不具有这些性质，因此根本无法计算它的热力学熵。说得更普遍些：你无法计算一个逻辑模型的热力学熵，同样也无法计算热力学系统的信息熵（因为缺乏明确的观测者和观测标准）。这也是为什么说上面第一点很重要的原因。其次，这个计算中该答主将玻尔兹曼常数遗漏了，以至于竟得出了以比特为量纲的“热力学熵”。

4有人说玻尔兹曼熵是信息熵的上限。这个说法在哲学上也许是正确的，但它目前似乎也只有哲学上的意义。

“熵”这一概念原本来自于化学和热力学，用于度量能量退化的指标，即熵越高，物体或系统的做功能力越低。后来香农将这一概念引入到信息论中，用于表示消息的平均信息量。信源的熵通常可以表示信源所发出信息的不确定性，即越是随机的、前后不相关的信息，其熵越高。

在信息论中，香农提出了信源编码定理。该定理说明了香农熵与信源符号概率之间的关系，说明信息的熵为信源无损编码后的平均码字长度的下限。任何的无损编码方法都不可能使编码后的平均码长小于香农熵，只能使其尽量接近。

基于此，对信源进行熵编码的基本思想，是使其前后的码字之间尽量更加随机，尽量减小前后的相关性，更加接近其信源的香农熵。这样在表示同样的信息量时所用的数据长度更短。

（插入参考 三分钟学习 | 熵编码 ）
那什么是熵编码？在信息熵的极限范围内进行编码就是熵编码。例如信息熵算出来是3bit/字符，你用4bit/字符来编码，就是熵编码，你用2bit/字符来编码，就不叫熵编码，因为这种情况下，就失真了嘛。 从这里也看以看出，信源熵是编码这个信源平均所需要的最小位数。所以，熵编码是无损压缩。

熵编码有很多种：

在实际使用中，常用的熵编码主要有变长编码和算术编码等方法。其中变长编码相对于算术编码较为简单，但平均压缩比可能略低。常见的变长编码方法有哈夫曼编码和香农-费诺编码等。例如JPEG用的是Huffman编码和算术编码，H264用的是CAVLC和CABAC。

戴维·哈夫曼（David·A·Huffman）于1952年在麻省理工学院的罗伯特·费诺的指导下攻读博士学位时，发明了一种基于有序频率二叉树的编码方法，该方法的编码效率超过了他的导师和信息论之父香农的研究成果（香农-费诺编码），因此又称作“最优编码方法”。

哈夫曼编码时变长编码方法的一种，该方法完全依赖于码字出现的概率来构造整体平均长度最短的编码方法。进行哈夫曼编码的关键步骤是建立符合哈夫曼编码规则的二叉树，该树又称作哈夫曼树。

哈夫曼树是一种特殊的二叉树，其终端节点的个数与待编码的码元的个数等同，而且每个终端节点上都带有各自的权值。每个终端节点的路径长度乘以该节点的权值的总和称为整个二叉树的加权路径长度。在满足条件的各种二叉树中，该路径长度最短的二叉树即为哈夫曼树。

在使用哈夫曼编码执行对码元的实际编码过程时，码元的权值可设置为其概率值，那么可以根据其权值来构建哈夫曼树。我们假设使用哈夫曼编码对以下概率的码字进行编码：

根据概率表构建哈夫曼树的过程如下图所示：

最终我们可以得到如下图所示的哈夫曼树：

例如上图的哈夫曼树，根节点访问左子树ABCF，赋予码字0；然后再访问左子树ABC，赋予码字0，此时整个码字为00，然后访问右子树得到终端节点C，赋予码字1，此时便可以得到C的哈夫曼编码码字001。以此规律，整个六个元素的码元集合的编码码表为：

从这个码表中还可以看出另外一个规律：哈夫曼编码的任意一个码字，都不可能是其他码字的前缀。因此通过哈夫曼编码的信息可以紧密排列连续传输，而不用担心解码时的歧义性。

缺点：

指数哥伦布编码同哈夫曼编码最显著的一点不同在于，哈弗曼编码构建完成后必须在传递的信息中加入码字和码元值的对应关系，也就是编码的码表，而指数哥伦布编码则不需要。

1先看例子，再说概念：
使用指数哥伦布编码来表示数值codeNum = 10，那么其前缀0的长度为prefixLen = floor[log2(codeNum+1)] = 3，因此指数哥伦布码的前缀为 0 0 0。其后缀部分的二进制表示为codeNum+1-2^prefixLen = 11-8 = 3 = b(0 1 1)，因此10的指数哥伦布编码码字为0 0 0 1 0 1 1。

也就是说，哥伦布编码以中间的1为对称轴，前缀全写0，需要先算出一共要写几个0。然后再算后缀的信息位，上面使用的公式暂时先不解释。

看一下怎么还原：当读取到指数哥伦布编码码字为0 0 0 1 0 1 1时，先计算前缀个数是3，然后越过中间的1，得到后缀信息位是二进制的011，也就是十进制的3。那么解码值就是2^3-1+3=10

使用以上技巧再看下20的编码：

看一下解码：
前缀4个0，后缀信息位0101，也就是5。所以2^4-1+5=20

2概念
在H264的标准协议中，不同的语法元素指定了不同的熵编码方法。在协议文档中共指定了10种语法元素的描述符，这些描述符表达了码流解析为语法元素值的方法，其中包含了H264标准所支持的所有熵编码方法：

常用的指数哥伦布编码通常可以分为四类：ue(v)、se(v)、me(v)、te(v)。其中无符号指数哥伦布编码ue(v)是其他编码方式的基础，其余几种方法基本可以由ue(v)推导得出。

3指数哥伦布编码同哈夫曼编码的比较
指数哥伦布编码同前文中提到的哈夫曼编码都遵循了同一规律，即针对不同的码元分配了bit位长度不同的码字，因此各自都属于变长编码的一种。然而二者仍然具有较大的差别，具体如：

实际上，对于视频压缩这样的需求而言，类似于哈夫曼编码所提供的压缩比率的优势远远不够，而且像H264等编码标准都不会指望靠这样的方式来提高压缩比率。

在H264码流结构（如NAL Unit、Slice Header等）的解析中，大多使用定长编码或者指数哥伦布编码实现。而例如预测残差等占据码流大量体积的数据则必须使用压缩率更高的算法，如CAVLC和CABAC等。

霍夫曼编码是变长编码,思路：对概率大的编的码字短,概率小的编的码字长,这样一来所编的总码长就小,这样编码效率就高你上面那样求是不对的,除非你这6个码字是等概率的,各占1/6应该用对应的概率其对应得码长,再求和

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

2算术编码，是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足大于等于0小于1的小数n。

3、LZ编码，LZ系列算法用一种巧妙的方式将字典技术应用于通用数据压缩领域，而且，可以从理论上证明LZ系列算法同样可以逼近信息熵的极限。

霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。

赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。

赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好。

哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的,它借助了数据结构当中的树型结构,在哈夫曼算法的支持下构造出一棵最优二叉树,我们把这类树命名为哈夫曼树因此,准确地说,哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式,它的本身有着非常广泛的应用。

---