前言
数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩[1]。
无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2到1/4。一些常用的无损压缩算法有哈夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)压缩算法。
有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。
前用得最多和技术最成熟的无损压缩编码技术，包括包含霍夫曼编码、算术编码、RLE编码和词典编码。
1 编码算法
1.1 香农-范诺编码
香农-范诺编码算法需要用到下面两个基本概念：
(1)Entropy(熵)的概念
○1熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。
○2某个事件的信息量用Ii＝-log2 pi表示 ， 其中pi为第i个事件的概率，0< pi 1
(2) 信源S的熵的定义
按照香农(Shannon)的理论，信源S的熵定义为:
...
其中pi是符号Si在S中出现的概率；log2(1/pi)表示包含在Si中的信息量，也就是编码Si所需要的位数。例如，一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为 pi=1/256，编码每一个象素点就需要8比特。
......

目 录

前言 1
1 编码算法 1
1.1 香农-范诺编码 1
1.2 霍夫曼编码 3
1.3 算术编码 4
1.4 RLE编码 10
1.5 词典编码 12
1.5.1 词典编码的思想 12
2 压缩算法 13
2.1 LZ77算法 13
2.2 LZSS算法 15
2.3 LZ78算法 17
2.3.1 编码算法 17
2.3.2 译码算法 18
2.4 LZW算法 20
2.4.1 编码算法 20
2.4.2译码算法 22
3 各种编码与算法的比较 26
3.1 对比方案 26
3.2 各种编码的比较结论 27
3.3 各种算法的比较结论 28
参考文献 30
致谢 31
附件 32

[参考文献
[1] 王晓燕,郑建宏. 视频压缩标准的技术及发展[M]. 清华大学出版,2004.
[2] 李峰年. 词典编码中的双向匹配压缩技术[M]. 清华大学出版,2003.
[3] 胡广书. 语音数字信号处理[M]. 华中理工大学出版社,1996.
[4] 胡广书. 数字信号处理[M]. 清华大学出版社,1999
[5] 林福宗. 多媒体技术基础[M]. 清华大学出版社,2000.
[6] 戚飞虎. 模式识别与图像处理[M].上海：上海交通大学出版社,1990.
[7] Timothy C.Bell, John G.Cleary, Ian H.Witten, Text Compression, Prentice-Hall, Inc. 1990.
[8] Terry A. Welch, A Technique for High-Performance Data Compression, Computer, June 1984.
[9] Wayne E.Carlson, A Survey of computer Graphics Image Encoding and Storage Formats, Computer Graphics, Vol.25, No.2, April 1991.
[10] Data Compression Reference Center，http://www.rasip.fer.hr/research/compress/index.html
[11] Gerald L.Graef, Graphics Formats, Byte, Sept. 1989.
[12] Julia Nguyen, Eric Hamiltom, JPEG File Interchange Format, Radius Inc, C-Cube Microsystems, April 10, 1991.
[13] R.Hunter and A.H.Robison, International Digital Facsimile Coding Standards, Proceedings of the IEEE, Vol.68, No.7 pp854—867， July, 1980.

通过介绍和比较常见的9种压缩编码和算法（香农-范诺编码、霍夫曼编码、算术编码、RLE编码、词典编码、 LZ77算法、LZSS算法、LZ78算法、LZW算法）。