一笔“划算的交易”

1、报告人：林枫报告人：林枫小组成员：鲍宏德、林枫、李雁南小组成员：鲍宏德、林枫、李雁南 压压缩缩衣服通过“压缩”才能装进行李箱 便于携带类似地，数据可以通过“压缩”打包 便于信息的传播与交流 1.1.人们对人们对“概率概率”的认识的认识2.C.E.Shannon2.C.E.Shannon与信息论与信息论远早于计算机的出现！远早于计算机的出现！1948年 通信的数学理论(A Mathematical Theory of Communication) （发表于贝尔系统技术杂志第27卷）信息论的“开山之作”！ 字面上看：字面上看：多余的信息传播学理论：传播学理论：信息中包含的、不影响信息完整的的那一部

2、分。事实上信息冗余可以理解为：事实上信息冗余可以理解为： 传输传输信信息所用数据位的数目息所用数据位的数目 与信信息中所包含的实际信息的数据位的数目息中所包含的实际信息的数据位的数目的差值差值，即，即 “不成为目标信息的那一部分不成为目标信息的那一部分”。例例1： 你比赛赢了么？ 第一局我赢了，第二局他赢了，第三局还是我赢了。例例2：吃过了啊？（打招呼的一种方式）香农指出：任何信息都存在冗余，冗余大小与信息中每个符号(数字、字母、单词)的出现概率或者说不确定性有关系。用冗余度冗余度表征这种信源信息的不确定性。质的评估：质的评估：难以评定（超出自然科学范围、缺乏统一标准）量的评估：量的评估：较好

3、评价，是当代信息论的出发点冗余度与信息的冗余度与信息的“量量”紧密相关紧密相关 例例1：马上要举行世界杯赛了。大家都很关心谁会是冠军。假如我错过了看世界杯，赛后我问一个知道比赛结果的观众“哪支球队是冠军”，他不愿意直接告诉我， 而要让我猜，并且我每猜一次，他要收一元钱才肯告诉我是否猜对了，那么我需要付给他多少钱才能知道谁是冠军呢? 我可以把球队编上号，从1到32， 然后提问： “冠军的球队在 1-16 号中吗?” 假如他告诉我猜对了， 我会接着问： “冠军在 1-8 号中吗?”假如他告诉我猜错了， 我自然知道冠军队在 9-16 中。这样最多只需要五次，我就能知道哪支球队是冠军。所以，谁是世界杯

4、冠军这条信息的信息量只值五块钱。 定义定义1 从两种可能性中作出判断需要的信息量为从两种可能性中作出判断需要的信息量为1 bit.由此，我们知道上述例1中谁是世界杯冠军这条信息的信息量为5bit.例例2：甲手持一张扑克牌让乙猜是什么花色的。对乙的提问，甲只能回答“是”或“不是”，要求乙尽可能少地提问并猜中花色，那么乙该如何发问？最少次数是多少？错误问法：“是黑桃吗？”正确问法：“是黑的吗？”“是桃吗？”因此： 从从4 4种可能性中作出判断所需要的信息量为种可能性中作出判断所需要的信息量为 2 2 bit. bit. 由上述定理我们知道： 作出判断需要的次数越多，需要的信息量越大，也就意味着缺少

5、的信息量越多。 因此信息量的度量实际上与我们的判断紧密相关，而我们的判断又与我们对事件的了解相联系。对于有N种可能性的事件，在不了解它的时候，它是具有不确定性的。我们只能假设每种事件出现的概率均为 。但现实中并非所有事件都是等可能事件，比如：猜测世界杯的冠军很可能不需要5次，因为巴西、德国、意大利等少数几支球队获胜可能性比其他球队要大很多。那么，这种情况下，香农便引入了“熵熵”的概念。 从从8 8种可能性中作出判断所需要的信息量为种可能性中作出判断所需要的信息量为 3 3 bit.bit. 从从1616种可能性中作出判断所需要的信息量为种可能性中作出判断所需要的信息量为 2 2 bit.bit

6、. 依次类推，可以得到如下定理：定理定理1 1 从从N N种可能性中作出判断所需要的信息量为种可能性中作出判断所需要的信息量为Nn2logNKnln或者写成：或者写成：其中其中2ln1KN1 热力学中，“熵”是一个状态函数，用于表征系统的混乱、无序的程度。表征系统的混乱、无序的程度。 热力学熵满足玻尔兹曼公式： 这里为与某一宏观状态对应的微观状态数。 事实上，我们发现所谓“混乱、无序”，在某种意义上就是一种不确定性，是一种缺乏规律的表现。Shannon引入热力学中“熵”的概念，来表征信息的不确定性。 在事件N种可能性相等，均为 的情况下，Shannon告诉我们： 定理定理2 2 作出完全判断所

7、需要的信息量为作出完全判断所需要的信息量为)/1038. 1(ln23KJkkSN1PKNKnlnln2ln1K其中可以改写为可以改写为NKSln Shannon把S称为信息熵（又叫香农熵）信息熵（又叫香农熵）. . 可以发现：Shannon的公式与玻尔兹曼公式具有相同形式。本质上，信息熵与热力学熵具有统一性。且两常数有换算公式：K=k 即1bit=kln2 J/K1bit=kln2 J/K 香农熵表征信息量的缺损信息量的缺损，是对信息不确定性的衡量。 香农熵减少，意味着信息量的增加；反之则意味着信息量的减少。信息量与信息熵是反相关的。 香农熵与冗余度描述香农熵的推广公式： 定理定理4 4 对

8、于N种不完全相同可能性的情况，信息熵的大小由下式给出NiiiPPKS1ln3.3.数据压缩与信息熵数据压缩与信息熵 本质上而言数据压缩的目的就是为了消除信息中的冗余。 在实现更接近实际信息描述前提下，尽可能减少描述用的信息量在实现更接近实际信息描述前提下，尽可能减少描述用的信息量 信息熵计算公式给出了信息编码的极限 在一定的概率模型下，无损压缩的编码长度不可能小于熵公式给出在一定的概率模型下，无损压缩的编码长度不可能小于熵公式给出的结果的结果 熵编码即编码过程中按熵原理不丢失任何信息的编码。（无损编码） （如：1948香农编码以及后续的算术编码、哈夫曼编码）数学手段数学手段 1.1.真正的编码

9、真正的编码 香农编码香农编码(Shannon)(Shannon)1948 先驱 哈夫曼编码哈夫曼编码(Huffman)(Huffman)1952最小冗余度代码的构造方法 （第一个实用编码方法） 对信息熵极限的挑战对信息熵极限的挑战 1968 P.Elias 1968 P.Elias 香农费诺香农费诺-Elias-Elias编码编码 1976 J.Rissanen 1976 J.Rissanen 算术编码算术编码 1982 J.Rissanen 1982 J.Rissanen和和G.G.Langdon G.G.Langdon 改进算数边按摩改进算数边按摩 1984 J.G.Cleary 1984

10、 J.G.Cleary和和I.H.Witten I.H.Witten 提出部分匹配预测模型提出部分匹配预测模型 逼近信息熵极限！逼近信息熵极限！ 2.LZ2.LZ系列算法系列算法提出者：J.Ziv和A.Lempel发展历程：1977 Ziv和Lempel 顺序数据压缩的一个通用算法 1978 Ziv和Lempel 通过可变比率编码的独立序列的压缩 1984 T.A.Welch 高性能数据压缩技术 1990 T.C.Bell 改进版本 原理：构建一个字典，用索引代替重复出现的字符和字符串 3.Burrows-Wheeler3.Burrows-Wheeler变换（变换（BWTBWT）提出者：M.Burrows和D.J.Wheeler提出时间：1994年核心思想：对字符串轮转后得到的字符矩阵排序变换应用：开放源码的压缩工具bzip4.4.现代压缩技术现代压缩技术无损压缩技术有损压缩技术 未来的研究工作将主要集中在四个方面：未来的研究工作将主要集中在四个方面： (1)设计新的压缩算法，支持对压缩域数据直接操作；设计新的压缩算法，支持对压缩域数据直接操作； (2)研究用小波、矢量量化、分形等方法压缩的多媒体数据的研究用小波、矢量量化、分形等方法压缩的多媒体数据的 压缩域处理算法；压缩域处理算法； (3)设计专用的压缩域数据处理芯片；设计专用的