霍夫曼编码霍夫曼编码-复旦大学.ppt

多媒体技术基础(第3版)第2章数据无损压缩
张奇
复旦大学计算机科学技术学院
2015年4月
2018年3月10日
第2章数据无损压缩
2 of 72
第2章数据无损压缩目录
数据的冗余
冗余概念
决策量
信息量
熵
数据冗余量
统计编码
香农-范诺编码
霍夫曼编码
算术编码
RLE编码
词典编码
词典编码的思想
LZ77算法
LZSS算法
LZ78算法
LZW算法
参考文献和站点
2018年3月10日
第2章数据无损压缩
3 of 72
数据无损压缩概述
数据可被压缩的依据
数据本身存在冗余
听觉系统的敏感度有限
视觉系统的敏感度有限
三种多媒体数据类型
文字(text)数据——无损压缩
根据数据本身的冗余(Based on data redundancy)
声音(audio)数据——有损压缩
根据数据本身的冗余(Based on data redundancy)
根据人的听觉系统特性( Based on human hearing system)
图像(image)/视像(video) 数据——有损压缩
根据数据本身的冗余(Based on data redundancy)
根据人的视觉系统特性(Based on human visual system)
2018年3月10日
第2章数据无损压缩
4 of 72
数据无损压缩概述(续1)
数据无损压缩的理论——信息论(information theory)
1948年创建的数学理论的一个分支学科,研究信息的编码、传输和存储
该术语源于Claude Shannon (香农)发表的“A Mathematical Theory munication”论文题目,提议用二进制数据对信息进行编码
最初只应用于通信工程领域,后来扩展到包括计算在内的其他多个领域,如信息的存储、信息的检索等。在通信方面,主要研究数据量、传输速率、信道容量、传输正确率等问题。
数据无损压缩的方法
霍夫曼编码(Huffman coding )
算术编码(arithmetic coding)
行程长度编码(run-length coding)
词典编码(dictionary coding)
……
2018年3月10日
第2章数据无损压缩
5 of 72
数据无损压缩概述(续2)
The Father of Information Theory——Claude Elwood Shannon
Born: 30 April 1916 in Gaylord, Michigan, USA
Died: 24 Feb 2001 in Medford, Massachusetts, USA
/news/2001/february/26/
信息论之父介绍
2018年3月10日
第2章数据无损压缩
6 of 72
数据无损压缩概述(续3)
Claude Shannon
——The founding father of munications age;American mathematical engineer
In 1936~1940, MIT:
Master's thesis, A symbolic analysis of relay and switching circuits
Doctoral thesis: on theoretical ics
In 1948:
A mathematical theory munication, landmark, climax
(An important feature of Shannon's theory: concept of entropy )
2018年3月10日
第2章数据无损压缩
7 of 72
数据的冗余
冗余概念
人为冗余
在信息处理系统中,使用两台计算机做同样的工作是提高系统可靠性的一种措施
在数据存储和传输中,为了检测和恢复在数据存储或数据传输过程中出现的错误,根据使用的算法的要求,在数据存储或数据传输之前把额外的数据添加到用户数据中,这个额外的数据就是冗余数据
视听冗余
由于人的视觉系统和听觉系统的局限性,在图像数据和声音数据中,有些数据确实是多余的,使用算法将其去掉后并不会丢失实质性的信息或含义,对理解数据表达的信息几乎没有影响
数据冗余
不考虑数据来源时,单纯数据集中也可能存在多余的数据,去掉这些多余数据并不会丢失任何信息,这种冗余称为数据冗余