1、无损数据压缩技术研究摘要近年来，随着计算机技术的发展，数据压缩技术的研究受到人们越来越多的关注。尤其是多媒体技术的兴起与信息通信技术的发展，更加促进了有关理论和技术的研究与开发并使之应用于工程实践。数据压缩技术在数据的存储、传输以及有效、快速获取信息方面的作用越来越来明显。本文首先分析了数据压缩技术研究的意义，以及该技术的发展与现状。接着对几种常见的压缩算法进行了了解，选择了 LZW 压缩算法进行数据的压缩，它的基本原理是采用了一种先进的串表压缩，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，压缩文件只存贮数字，而不存贮串，从而达到数据压缩的目的。本文采用 VB 语言进行编程，通过
2、 Visual basic 6.0 软件设计平台设计的LZW 数据压缩软件，经过测试，确实达到了数据压缩的目的。关键词：数据压缩，LZW 算法，无损压缩，VBResearch of lossless data compression technology AbstractIn recent years, with the development of computer technology, data compression technology has been taken more and more attention. In particular the rise of multimed
3、ia technology and the development of information and communication technology, to promote more on the theory and technology research and development and applied engineering practice. The role of data compression technology in data storage, transmission and effective, and rapid access to information
4、is more clearly. The first analysis of this paper is the significance of data compression technology and the technology development and the status quo. Then on some common understanding of the compression algorithm, by comparing choose the LZW compression algorithm for data compression, it is the ba
5、sic principle adopted a series of advanced compression table, each of the first-string The strings in the table, with a figure that the compressed file only digital storage, rather than storing strings to achieve the purpose of data compression. In this paper, VB programming language, Visual basic 6
6、.0 software through the design of the platform design LZW data compression software, has been tested, really achieve the objective of the data compression.Key words: data compression, LZW algorithm, lossless compression, VB第 I 页 共页目录1 引言 11.1 数据压缩技术研究的目的与意义 11.2 数据压缩技术发展与现状 21.3 现代数据压缩系统的特点 31.4 本论文
7、的主要原理与工作 32 数据压缩技术 52.1 数据压缩技术概述 52.2 数据压缩技术的分类 62.3 数据压缩算法介绍 82.3.1 Shannon-Fano 编码(仙侬 范诺编码) 82.3.2 霍夫曼编码 92.3.3 算术编码 102.3.4 游程编码 122.3.5 词典编码 133 软件压缩模块与硬件电路模块 173.1 数据压缩流程图 173.2 LZW 字典压缩步骤 193.3 VB 程序与代码说明 213.4.1 字典初始化及哈希表查找模块 223.4.2 字典清零模块 233.4.3 字典添加模块 23第 II 页 共页3.5 LZW 算法硬件电路模块 244 软件解压缩
8、模块 264.1 解压缩流程图 264.2 LZW 字典解压缩步骤 284.3 程序代码说明 294.3.1 字典初始化模块 294.3.2 判断编码开始与结束模块 294.3.3 查看编码是否存在于字典模块 295 工作总结 31附录 32参 考 文 献 34致谢 36第 1 页 共 36 页1 引言多媒体计算机技术、计算机网络技术以及现代多媒体通信技术正在向着信息化、高速化、智能化迅速发展。随着各个领域的应用与发展，各个系统的数据量越来越大，使数据的存储、传输以及有效、快速获取信息面临巨大挑战。而数据压缩技术成为解决这一问题的关键技术 1。1.1 数据压缩技术研究的目的与意义数据压缩是一门
9、既古老又年轻的学科。但由于技术实现的障碍，长期以来主要处于理论研究和计算机仿真阶段，然而随着数字信号处理方法、计算机技术、特别是数据压缩软件技术的发展，推动了数据压缩技术的普及与发展。近年来，随着计算机技术的发展，数据压缩技术的研究受到人们越来越多的关注。尤其是多媒体技术的兴起与信息通信技术的发展，更加促进了有关理论和技术的研究与开发并使之应用于工程实践，信息的观念也不断的在我们的思想中加深。信息的本质是要求交流和传播即将信息从这里传到那里典型的通信概念，或者将信息从现在传输到未来所谓的存储问题 2。本课题就是要解决数据的压缩问题，以尽可能少的数据表示信源信息，减少冗余量，提高信息熵，减少数据
10、所占存储空间和传输所耗时间 。数据压缩就是指以最少的数码表示信源所发的信号，减少容纳给定消息集合或数据采集集合的信号空间。有关数据压缩的理论研究是在仙侬信息论基础上开始的。仙侬创立信息论时，提出把数据看作是信息和冗余度的组合。因此，简单的说压缩就是用短的代码代替长的数据，把冗余度降到最低。总之，数据压缩技术在计算机技术飞速发展的今天，有着很重要的作用。数据压缩技术除了可以减少系统开销外，还有另外的好处。当数据压缩用于减少存储空间时，可以减少程序的总体执行时间。这是因为存储量的减少将导致磁盘存取次数的减少。虽然数据的压缩还原会增加额外的程序指令，但由于程序的执行时间通常少于数据存取和转换的时间，
11、故其总的执行时间将减少 3。当数据压缩被用于数据传输时，由于传输的字符较少，可以减少传输数据发生错误的概率同时提高了效率。由于传输的是压缩了的数据，而不是ASCII码，增加了系统的安全性。第 2 页 共 36 页根据以上的介绍，信息的传播(如电视)、传输(如语音通信)与存储(如云图的计算机存储) 都离不开数据的压缩，因此也就不难明白，数据压缩技术的应用前景自然是无可限量的 4。1.2 数据压缩技术发展与现状信息论之父 C.E.Shannon第一次用数学语言阐明了概率与信息冗余度的关系。在1948年发表的论文“ 通信的数学理论 (A Mathematical Theory of Communic
12、ation)”中，Shannon指出，任何信息都存在冗余，冗余大小与信息中每个符号(数字、字母或单词) 的出现概率或者说不确定性有关。Shannon 借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵” ，并给出了计算信息熵的数学表达式。这篇伟大的论文后来被誉为信息论的开山之作，信息熵也奠定了所有数据压缩算法的理论基础 5。第一个实用的编码方法是由 D.A.Huffman在1952年的论文“最小冗余度代码的构造方法(A Method for the Construction of Minimum Redundancy Codes)”中提出的。从此，数据压缩开始在商业程序中实现并被
13、应用在许多技术领域。80年代初，Huffman编码又在CP/M 和DOS系统中实现，其代表程序叫 SQ。在数据压缩领域，Huffman的这一论文事实上开创了数据压缩技术一个值得回忆的时代，60年代、70年代乃至80年代的早期，数据压缩领域几乎一直被Huffman编码及其分支所垄断。直到今天，许多数据结构教材在讨论二叉树时仍要提及这种被后人称为Huffman编码的方法 6。80 年代，数学家们不满足于Huffman编码中的某些致命弱点，他们从新的角度入手，遵循Huffman编码的主导思想，设计出另一种更为精确的编码方法算术编码。凭借算术编码的精妙设计和卓越表现，人们终于可以向着数据压缩的极限前进
14、了。当然，算术编码同时也给程序员和计算机带来了新的挑战：要实现和运行算术编码，需要更为艰苦的编程劳动和更加快速的计算机系统。也就是说，在同样的计算机系统上，算术编码虽然可以得到最好的压缩效果，但却要消耗也许几十倍的计算时间 7。1977年，Ziv和Lempel发表题为“顺序数据压缩的一个通用算法(A Universal oAlgrithm for Sequential Data Compression)”的论文，该算法完全脱离Huffman及算术编码的设计思路，创造出了一系列比Huffman编码更有效，比算术编码更快捷的压缩算法。论文中描述的算法被后人称为LZ77算法。1978年，二人又发表了
15、该论第 3 页 共 36 页文的续篇“通过可变比率编码的独立序列的压缩(Compression of Individual Sequences via Variable Rate Coding)”，描述了后来被命名为LZ78的压缩算法。1984年，T. A. Welch 发表了名为“高性能数据压缩技术 (A Technique for High Performance Data Compression)”的论文，描述了他在Sperry研究中心的研究成果，这是LZ78算法的一个变种，也就是后来非常有名的LZW算法。LZW继承了LZ77和LZ78压缩效果好、速度快的优点，而且在算法描述上更容易被人
16、们接受(有的研究者认为是由于Welch的论文比Ziv和Lempel的更容易理解)，实现也比较简单。不久，UNIX上出现了使用LZW 算法的Compress程序，该程序性能优良，并有高水平的文档，很快成为了UNIX世界的压缩程序标准。紧随其后的是 MS-DOS环境下的ARC程序(System Enhancement Associates, 1985)，还有象PKWarePKARC等仿制品。LZ78和LZW 一时间统治了UNIX和DOS两大平台 8。上述表明，即便在日趋成熟的通用数据压缩领域，只要能在思路和技术上不断创新，数据压缩技术仍然能继续向前跃进，取得长足的进步。1.3 现代数据压缩系统的特
17、点1、现代数据压缩系统一般都运用计算机系统，这使得数据压缩的质量和效率等大为提高，同时，显著节省了硬件资源；2、软件在数据压缩系统中的作用越来越大，增加了数据压缩的灵活性；3、随着微电子技术的发展，数据压缩系统的体积越来越小，可靠性越来越高，不仅提高了信号传输带宽的利用率，而且减少了数据存储空间，降低了数字系统的成本 9。1.4 本论文的主要原理与工作本论文论采用 VB 语言编程实现数据压缩，编译软件采用 Visual basic 6.0，功能框图如图 1.1。该软件把待处理的数据通过软件压缩模块进行压缩处理生成新的数据，然后比较新数据与原始数据，分析压缩比；压缩数据再经过软件解压模块解压处理
18、恢复数据，再核对恢复数据与原始数据值，查看误码分析结果。第 4 页 共 36 页原始数据压缩后数据压 缩解压缩恢复数据图 1.1 功能框图软件模块2 数据压缩技术2.1 数据压缩技术概述数据压缩就是指以最少的数码表示信源所发的信号，减少容纳给定消息集合第 5 页 共 36 页或数据采集集合的信号空间，它主要研究数据的表示、传输和转换方法。多媒体计算技术的关键问题之一是实时地处理语音、图象和文本数据。除了硬件设备和系统软件的支持外，需要解决的一个重要的问题是大量数据的存储、处理和传输。数据压缩技术是能够比较有效解决这个问题的途径之一 10。有关数据压缩的理论研究是在仙侬信息论基础上开始的。仙侬创
19、立信息论时，提出把数据看作是信息和冗余度的组合。在信息论中用“熵” 来测量信息量的大小。对于单个事件( 如一个字符)来说，其熵定义为：H(i)=-log2(Pi)该式表示发生的概率为Pi的事件(字符)i所具有的信息量。单位是 “位”。为区别于热力学熵，又称其为信息熵。一个事件发生的概率越小，其信息熵越高，所含的信息量越大。因此，简单的说压缩就是用短的代码代替长的数据，把冗余度降到最低。数据压缩技术研究和处理的对象可以是数据的物理容积，如所占的空间；也可以是时间间隔，例如，传输某个指定数据集合所需的时间；还可以是传输指定数据集合所需的频带宽度。数据压缩的这三个对象是相互关联的：物理容积f(时间，
20、带宽)在某一特定的应用环境中，一般说来不太可能同时对全部三个参数进行压缩，通常只有一项做为压缩的关键。不过，在这些年的研究中，人们对这几个参数的关注程度发生了一些变化。最初，大家对在通讯系统中减少传输模拟信号所需的带宽有极大的兴趣(现在该问题仍是人们关注的焦点问题之一)。随后，在传真类系统中，对提高传输速度关注起来 11。近年来，在许多系统，特别是计算机与数字通讯系统中，数据所占存储空间的大小成为压缩的关键参数。衡量压缩程度的指标之一是压缩比。到目前为止，关于压缩比的定义尚无统一的方法。在信息论中，压缩比定义为压缩前后数据的熵之比。这种定义方法基于对要压缩数据的统计分析结果而提出。而现在所使用
21、的许多压缩技术并不依赖于数据的统计结果。因此采用这种定义方法有相当的局限。为与实际的概念相一致，我们拟采用如下形式定义压缩比：压缩比 = ( 源代码长度- 压缩后代码长度)源代码长度 %其含义是被压缩掉的数据占原数据的比例。例如，若压缩后的代码长度与源第 6 页 共 36 页数据相同，则压缩比为0；若压缩后的代码长度为0，则达到100的压缩比；若压缩后的代码长度是源数据的30，则表示被压缩了70，即其压缩比是70。数据压缩技术所探讨和研究的各种压缩方法，都是为了提高压缩比。不同的文件，不同的压缩方法，不同的图象分辨率都将影响到压缩比的大小。从数据压缩的目的来说，我们希望压缩比越大越好。但实际上
22、，压缩比是有上限的。对基于统计的编码方法而言，这个上限与信息的熵有着密切的关系。如果压缩比超过了这个上限，还原时将无法恢复原状，出现失真。一般说来，数据压缩的工作是将符号流或数据流转换成相应的代码。显然，只有输出的代码流小于源符号流时，所做的数据压缩才是有效的。数据压缩的工作是在模型的基础上进行的。这里提到的模型是数据和规则的集合。规则用来处理输入符号，使之转换成相应的输出代码。构造数据压缩的模型和编码是两件不同的事情。但许多人常常把编码看作是数据压缩的全部内容。实际上编码仅仅是数据压缩的一部分。模型的构造和编码是两个分离的部分 12。换句话说，压缩 = 模型 + 编码。如下图 2.1所示：符
23、号 概率 代码图2.1 压缩模块图如果我们用汽车做比喻，那么，编码可以被看做是车轮，模型的构造则被看做是发动机。模型若不能提供合适的规则和数据，编码器的编码效果再好也无法完成预定的压缩工作。2.2 数据压缩技术的分类数据压缩技术有多种不同的分类方法。若按压缩技术所使用的方法进行分类可分为预测编码、变换编码和统计编码三大类。这种分类方法是以不同的数学理论和方法为准则设计编码模型，进行压缩编码 13。另一种是按压缩过程的可逆性进行分类。这是多数学者认同的比较一致的分类方法。这样更能说明它们的本质区别。通常分为熵压缩和冗余度压缩两种。熵压缩是不可逆压缩也称为有损压缩。在熵压缩的过程中，会损失掉一部分信息(即损失了信息源) 。这样，在还原压缩文件时就无法做到无失真地再现被压缩的数据，因此这种压缩又称为有损压缩。它是以丢失部分信息为代价而获得较好的压缩效输入 模型 编码 输出
