2021年1月21日星期四 62数据压缩的发展历程 1952年提出有效的压缩方法 Huffman编码; 80年代,设计出更能接近信息论中“熵”极限 的编码方法——算术编码。 1984年, Terry Welch实现了LZ78算法的一个变 种LzW 80年代中期以后,人们对LZ77进行了改进,目前, 基于字典方式的压缩已经有了一个被广泛认可的 标准,从古老的 PKZip到现在的 WinZip,特别 是随着 Internet上文件传输的流行,ZIP格式成 为了事实上的标准
2021年1月21日星期四 6.2 数据压缩的发展历程 1952 年提出有效的压缩方法Huffman 编码； 80 年代，设计出更能接近信息论中“熵”极限 的编码方法——算术编码。 1984年，Terry Welch实现了LZ78算法的一个变 种LZW 80年代中期以后，人们对LZ77进行了改进，目前， 基于字典方式的压缩已经有了一个被广泛认可的 标准，从古老的 PKZip 到现在的 WinZip，特别 是随着 Internet 上文件传输的流行，ZIP 格式成 为了事实上的标准
2021年1月21日星期四 63数据压缩的技术基础 熵的概念 数据压缩模型 数据压缩编码
2021年1月21日星期四 6.3 数据压缩的技术基础 ◼ 熵的概念 ◼ 数据压缩模型 ◼ 数据压缩编码
2021年1月21日星期四 63,1熵的概念 数据压缩不仅起源于40年代由 Claude Shannon首创的信息论,而且其基本原理即信 息究竞能被压缩到多小,至今依然遵循信息论中 的二条定理,这条定理借用了热力学中的名词 “熵”( Entropy)来表示一条信息中真正需要编 码的信息量,即数据压缩的理论极限。对于任何 种无损数据压缩,最终的数据量一定大于信息 熵,数据量越接近于熵值,说明其压缩效果越好, 假定一种无损数据压缩之后数据量小于信息熵, 能说明一个问题,说明其数据压缩肯定出错了
2021年1月21日星期四 6.3.1 熵的概念 ➢ 数据压缩不仅起源于 40 年代由 Claude Shannon 首创的信息论，而且其基本原理即信 息究竟能被压缩到多小，至今依然遵循信息论中 的一条定理，这条定理借用了热力学中的名词 “熵”( Entropy )来表示一条信息中真正需要编 码的信息量，即数据压缩的理论极限。对于任何 一种无损数据压缩，最终的数据量一定大于信息 熵，数据量越接近于熵值，说明其压缩效果越好， 假定一种无损数据压缩之后数据量小于信息熵， 只能说明一个问题，说明其数据压缩肯定出错了
2021年1月21日星期四 63,1熵的概念 信息熵如何来计算: 在计算机内部是用二进制来表示数据的,现在要 用0和1组成的二进制数码来为含有n个符号 的某条信息编码,假设符号Fn在整条信息中重 复出现的概率为Pnη,则该符号的熵En也即表示 该符号所需的位数为:En=log2(1/Pn)= log2(Pnη)整条信息的熵E也即表示整条信息所 需的位数为:E=∑En
2021年1月21日星期四 6.3.1 熵的概念 ➢ 信息熵如何来计算： ◼ 在计算机内部是用二进制来表示数据的，现在要 用 0 和 1 组成的二进制数码来为含有 n 个符号 的某条信息编码，假设符号 Fn 在整条信息中重 复出现的概率为 Pn，则该符号的熵En也即表示 该符号所需的位数为：En = log2( 1/Pn )= - log2( Pn ) 整条信息的熵E也即表示整条信息所 需的位数为：E = ∑En
2021年1月21日星期四 63,1熵的概念 举个例子:字符串: aabbaccbaa 字符串长度为10,字符a、b、C分别出现了5、 3、2次,则a、b、C在信息中出现的概率分别 为0.5、0.3、0.2,他们的熵分别为: Ea=-og2(0.5)=1 Eb=-og2(0.3)=1.737 Ec=-og2(0.2)=2.322 整条信息的熵为: E=Ea*5+助b*3+EC*2=14855位
2021年1月21日星期四 6.3.1 熵的概念 ◼ 举个例子 : 字符串：aabbaccbaa 字符串长度为 10，字符 a、b、c 分别出现了 5、 3、2 次，则 a、b、c 在信息中出现的概率分别 为 0.5、0.3、0.2，他们的熵分别为： Ea = -log2(0.5) = 1 Eb = -log2(0.3) = 1.737 Ec = -log2(0.2) = 2.322 整条信息的熵为： E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位