（毕业论文 页数：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
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


前言
数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩[1]。
无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2到1/4。一些常用的无损压缩算法有哈夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)压缩算法。
有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。
前用得最多和技术最成熟的无损压缩编码技术，包括包含霍夫曼编码、算术编码、RLE编码和词典编码。