关于编码与压缩初步研究
资料包括： 论文(37页14296字) 图纸
说明：
摘要：通过介绍和比较常见的9种压缩编码和算法（香农-范诺编码、霍夫曼编码、算术编码、RLE编码、词典编码、 LZ77算法、LZSS算法、LZ78算法、LZW算法）。在对比中发现词典编码是效率较高的无损编码方法之一，这种技术根本依据是数据本身包含着重复代码的特性，在压缩查找重复代码时，沿数据流输入的方向找到完全匹配的字符串或者数据，用已经处理过的数据的指针代替正在处理的完全匹配的字符串或者数据。具有某种特征或者经过处理后具有某种重复特征的现象是较为普遍存在的。本文中涉及的到压缩算法都用到了词典编码思想，文中详细的讲述了LZ78和LZW算法的编码算法和译码算法过程。
关键字：算术编码 RLE编码 词典编码 LZ77算法 LZSS算法 LZ78算法 LZW算法
Abstract : By introducing and contrasting nine compression codes and algorithms (Shannon – Fano code, huffman code, arithmetic code, RLE code, dictionary code, LZ77 algorithm, LZSS algorithm, LZ78 algorithm, and LZW algorithm), the dictionary code is found to be one of the most efficient and no damage codes, the basis of this technology is that the data itself contains repetition code. When compressing and searching the redundant code, the matched character string or data will be found along the input direction of data stream, and replace the completely matched character string or data in processing by the data indicator already processed. All the compression algorithms referred here use the dictionary code, and the processes of coding and decoding algorithm LZ78 and LZW are narrated here.
Key word: Arithmetic-code; RLE-code; Dictionary code; LZ77- algorithm; LZSS- algorithm; LZ78- algorithm; LZW- algorithm
前言
数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩。
无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2到1/4。一些常用的无损压缩算法有哈夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)压缩算法。
有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。
前言1
1 编码算法1
1.1 香农-范诺编码1
1.2 霍夫曼编码3
1.3 算术编码4
1.4 RLE编码9
1.5 词典编码11
1.5.1 词典编码的思想11
2 压缩算法12
2.1 LZ77算法12
2.2 LZSS算法14
2.3 LZ78算法15
2.3.1 编码算法16
2.3.2 译码算法17
2.4 LZW算法18
2.4.1 编码算法18
2.4.2译码算法21
3 各种编码与算法的比较24
3.1 对比方案24
3.2 各种编码的比较结论25
3.3 各种算法的比较结论26
参考文献28
致谢29
附件30
参考文献：
王晓燕 郑建宏，视频压缩标准的技术及发展 清华大学出版 2004年.
李峰年，词典编码中的双向匹配压缩技术 清华大学出版 2003年
胡广书，语音数字信号处理，华中理工大学出版社，1996年
胡广书，数字信号处理，清华大学出版社，1999年
林福宗，多媒体技术基础，清华大学出版社，2000年
戚飞虎等，模式识别与图像处理[M].上海：上海交通大学出版社,1990.
Timothy C.Bell, John G.Cleary, Ian H.Witten, Text Compression, Prentice-Hall, Inc. 1990.
Terry A. Welch, A Technique for High-Performance Data Compression, Computer, June 1984.
Wayne E.Carlson, A Survey of computer Graphics Image Encoding and Storage Formats, Computer Graphics, Vol.25, No.2, April 1991.
Data Compression Reference Center，http://www.rasip.fer.hr/research/compress/index.html
Gerald L.Graef, Graphics Formats, Byte, Sept. 1989.
Julia Nguyen, Eric Hamiltom, JPEG File Interchange Format, Radius Inc, C-Cube Microsystems, April 10, 1991.
R.Hunter and A.H.Robison, International Digital Facsimile Coding Standards, Proceedings of the IEEE, Vol.68, No.7 pp854—867， July, 1980.
作者点评：
香农-范诺编码和霍夫曼编码有两个问题值得注意：
○1香农-范诺编码和霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。
○2霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。
与香农-范诺编码相比，这两种方法都自含同步码，在编码之后的码串中都不须要另外添加标记符号，即在译码时分割符号的特殊代码。此外，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。
在算术编码中，我们假定编码器和译码器都知道消息的长度，因此译码器的译码过程不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符，当译码器看到终止符时就停止译码。
算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程。需要开开发态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的键。
RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。然而，RLE对颜色丰富的自然图像就显得力不从心，在同一行上具有相同颜色的连续象素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。请注意，这并不是说RLE编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中还真少不了RLE，只不过是不能单纯使用RLE一种编码方法需要和其它的压缩编码技术联合应用。
词典编码是经典的效率较高的一种无损压缩技术，这种技术根本依据是数据本身包含着重复代码的特性，在压缩查找重复代码时，沿数据流输入的方向找到完全匹配的字符串或者数据，用已经处理过的数据的指针代替正在处理的完全匹配的字符串或者数据。具有某种特征或者经过处理后具有某种重复特征的现象是较为普遍存在的，如果能用这种特点，对数据进行处理，可能会压缩效果更好。同时，依据数据特征编码写算法来压缩数据也可以作为一种思路+]。
3.3 各种算法的比较结论
LZ77算法的核心是双向查找最长匹配，过程大致是首先用编码位置的字符和已处理过的字符匹配，若不成功，则编码位置前进一个字符，若成功，则取编码位置的下一个字符与已处理过的匹配的字符正反两个方向匹配，检测是否成功，始终取匹配串较长的一方，若正反两个方向匹配串长度相同则取正向。LZ77是输出真实字符解决在窗口中出现没有匹配串的问题，但这种处理思路中有冗余信息，冗余信息表现在两个方面，一是空指针；二是编码器可能输出额外字符，这种字符是指可能包含在下一个匹配串中的字符。
LZSS主要比较有效地解决了LZ77算法中的冗余信息问题，它的思想是如果匹配串长度比指针本身的指针长度长，就输出指针，否则就输出真实字符，由于输出的压缩数据流中包含有指针和字符本身，为了区别需要有额外的标志位ID。
LZ78算法的思想是不断地从字符流中提取新的缀—符串，通俗地理解为“词条”，然后用代号也就是码字表示这个词条，在这里需要特别说明，一个码字如果带有标识，假定用“-”表示反向匹配的码字，这样一来，对字符流的编码就变成了用码字去替换字符流，生成码字流，从而达到压缩数据的目的。
LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。在LZW算法中使用的术语与LZ78使用的相同，仅增加了一个术语—前缀根(Root)，它是由单个字符串组成的缀-符串(String)。在编码原理上，LZW与LZ78相比有如下差别：
○1LZW只输出代表词典中的缀-符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。
○2由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在词典中搜索的第1个缀-符串有两个字符。
通过对以上几个编码和压缩方法的对比我们可以得出词典编码的优势在于数据本身包含着重复代码的特性，在压缩查找重复代码时，沿数据流输入的方向找到完全匹配的字符串或者数据，用已经处理过的数据的指针代替正在处理的完全匹配的字符串或者数据。LZW算法速度比较快而且执行的操作比较少，不容易发生误码等错误。