数据无损压缩.ppt

2.4词典编码(续2)第二类编码算法从输入的数据中创建一个“短语词典(dictionaryofthephrases)”编码器输出词典中的短语“索引号”，而不是短语图2-7第二类词典编码概念LZW算法第37页,共37页，星期六，2024年，5月2.0数据无损压缩概述(续2)TheFatherofInformationTheory——

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA/news/2001/february/26/1.html信息论之父介绍第5页,共37页，星期六，2024年，5月2.1数据的冗余冗余概念人为冗余在信息处理系统中，使用两台计算机做同样的工作是提高系统可靠性的一种措施---冗余设备在数据存储和传输中，为了检测和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据---检错码，纠错码视听冗余由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使用算法将其去掉后并不会丢失实质性的信息或含义，对理解数据表达的信息几乎没有影响数据冗余不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢失任何信息，这种冗余称为数据冗余，而且还可定量表达第6页,共37页，星期六，2024年，5月2.1数据的冗余(续1)决策量(decisioncontent)在有限数目的互斥事件集合中，决策量是事件数的对数值在数学上表示为H0=log(n)其中，n是事件数决策量的单位由对数的底数决定Sh(Shannon):用于以2为底的对数Nat(naturalunit):用于以e为底的对数Hart(hartley)：用于以10为底的对数第7页,共37页，星期六，2024年，5月2.1数据的冗余(续2)信息量(informationcontent)具有确定概率事件的信息的定量度量在数学上定义为

其中，是事件出现的概率一个等概率事件的集合，每个事件的信息量等于该集合的决策量第8页,共37页，星期六，2024年，5月举例：假设X={a,b,c}是由3个事件构成的集合，p(a)=0.5，p(b)=0.25，p(b)=0.25分别是事件a,b和c出现的概率，这些事件的信息量分别为，I(a)=log2(1/0.50)=1shI(b)=log2(1/0.25)=2shI(c)=log2(1/0.25)=2shp(a)=0.5是符号a在I中出现的概率；log2(1/p(a))表示包含在I中的信息量，也就是编码a所需要的位数。例如:一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为P=1/256，编码每一个象素点就需要8位。第9页,共37页，星期六，2024年，5月2.1数据的冗余(续3)熵(entropy)按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(meaninformationcontent)用数学表示为熵--最佳平均编码位数第10页,共37页，星期六，2024年，5月2.1数据的冗余(续4)数据的冗余量第11页,共37页，星期六，2024年，5月2.2统计编码 统计编码给已知统计信息的符号分配代码的数据无损压缩方法编码方法香农-范诺编码霍夫曼编码算术编码编码特性香农-范诺编码和霍夫曼编码的原理相同，都是根据符号集中各个符号出现的频繁程度来编码，出现次数越多的符号，给它分配的代码位数越少算术编码使用0和1之间的实数的间隔长度代表概率大小，概率越大间隔越长，编码效率可接近于熵第12页,共37页，星期六，2024年，5月2.2.1统计编码——香农-范诺编码 香农-范诺编码(Shannon–Fanocoding)在香农的源编码理论中，熵的大小表示非冗余的不可压缩的信息量在计算熵时，如果对数的底数用2，熵的单位就用“香农(Sh)”，也称“位(bit)”。“位”是1948年Shannon首次使用的术语。例如最早阐述和实现“从上到下”的熵编码方法的人是Shan