基于数据压缩算法的研究
作者：邹瑞芝
来源：《沿海企业与科技》2011年第02期
        基于数据压缩算法的研究
        邹瑞芝
        ［摘要］随着信息技术和计算机技术的飞速发展，人们面对的数据越来越多，在数据储存和传输的过程中，数据压缩的地位越来越重要。文章介绍LZW数据压缩算法,并给出一个编码实例，实验结果证明这是一种有效的数据压缩方法。
        ［关健词］数据压缩；无损压缩；LZW算法
        ［作者简介］邹瑞芝，广州华南商贸职业学院信息工程系专任教师，计算机应用硕士，广东广州，510000
        ［中图分类号］ TP391 ［文献标识码］ A ［文章编号］ 1007-7723（2011）02-0020-0002
        一、引言
        随着信息技术和计算机技术的飞速发展，人们面对的数据越来越多，在数据储存和传输的过程中，数据压缩[1]的地位越来越重要。一般来说，数据压缩可以按压缩的失真度分为有损压缩和无损压缩[2]。有损压缩顾名思义就是把使用压缩技术后的数据进行解码还原，得到的数据与之前的数据不是完全一样，却不会使人们对原始资料引起错误的理解。有损压缩一般应用在压缩后的数据不一定要和原始数据完全一致的场合。无损压缩就是指把压缩后的数据进行解码还原，得到的数据与原始数据一模一样，没有改变。目前流行的无损压缩编码有哈夫曼编码、LZW编码、算术编码、行程编码等。
        目前，数字化和网络化正在给我们的生活带来翻天覆地的变化，图像的数字化也将成为一个必然的趋势。占据我们大量存储空间和传输带宽的图像，如果采用数字化处理，会使得图像数据有如下优点：（1）数字化处理后的图像容易储存而且方便处理，不再是一块难嚼的鸡肋，能够满足人们的各种需求；（2）数字化处理后的图像在传输过程中容易传输且快速；（3）数字化处理后的图像与原始图像一样高分辨率，优质量；（4）数字化处理后的图像更增强了稳定性和传输过程中的抗干扰能力。但是，通常数字化后的图像仍然面临着对海
量数据的存储与传送问题。所以，在计算机的存储空间和信道有限的条件下，怎样高质量、高效率地对数字化后的图像进行可靠压缩成为计算机技术的热门研究领域。
        Lempel-Ziv-Welch（LZW）编码就是一种主要用于图像数据压缩的算法。这种算法对一些简单平滑的图像和一些噪声小的数据具有比较高的压缩比，而且本算法有比较快的压缩和解压缩速度。本文主要介绍了LZW算法,并给出了一个编码实例，通过实验结果可以证明这是一种有效的数据压缩方法。
        二、LZW算法
        LZW算法是在数据压缩经典算法LZ77和LZ78二者的基础上改进而成的，由Terry Welch于1984年提出[3][4]。
        LZW算法在开始压缩之前，字典中只有单个字符和编码的串表。开始压缩时，读入字符串，按一定的顺序与字典中已包含的字串进行匹配，如果能够匹配成功，则将匹配好的字符串对应编码输出；如果不能进一步匹配，则将导致匹配失败的字符与之前的字符串合并在一起，加入串表并给以相应编码。
        LZW算法的串表具有前缀性 [5]，即表中任何一个字符串的前缀字符也在串表中。也就是说，如果由某个字符串P和某个单字符C所组成的字符串PC在表中，则P也在表中。C叫作前级串P的扩展字符。
        LZW算法与LZ78算法有着相似的编码和解码过程。这两种算法的主要区别在于进行编码时，因为在压缩时，字典中已经包含有每个单字符及其编码的串表，所以在LZW算法的码字中省略了LZ78算法的码字中关于未匹配字符这项，只是含有已经匹配成功的字符串的索引值，由此来降低LZW算法的码字的长度以便提高数据压缩比；解码时，由于表中需要的未匹配字符要在解压缩下一个输入码字后才可以获得，因此建表的过程相对于压缩时要推迟一步。
        三、LZW算法实例
        本文使用VC来编译代码和制作界面。
        在压缩开始时，首先要对存放字符串的hash表、结束标志、清除标志、输入/输出缓冲的位置进行初始化。必须使hash表不是空值，从0开始记输出缓冲位。需要定义前缀字符串
Old和当前读入字符Pixel。如果Old+Pixel字符串存在hash串表当中，就从中取出该字符串的索引编号Index。
字符串长度压缩
        部分代码可表示为：
        if (this->Encode_IsInTable (Old, Pixel))
        Old = m_pHash[(Old
        如果Old+Pixel字符串不在hash串表当中，就把Old+Pixel字符串添加到String Table编码表。
        部分代码可表示为：
        this->Encode_WriteIndex (Old) ;
        this->Encode_AddStringToTable (Old, Pixel) ;
        Old = Pixel ;
        进行压缩完成后要清除hash表。在数据解码过程中，hash串表能依据原始字典和Index再次生成。
        数据的解压缩过程其实是压缩的逆过程。首先还是必须对字符串表、清除标志、结束标志和输入/输出进行初始化。需要定义前缀字符串Old和当前读入字符Pixel（当前输入的经压缩后的字符）。如果Code既不是清除标志也不是结束标志时，算法进行数据解码工作。
        部分代码可表示为：
        if (this->Decode_IsInTable (Code))
        this->Decode_AddStringToTable(Old, this->Decode_GetFirstChar (Code)) ;
        else
        this->Decode_AddStringToTable(Old, this->Decode_GetFirstChar (Old)) ;
        进行解码完成后，要清空m_pStrBegin指针，即清空指向String Table表的指针。
        下面我们采用一个示例图像，使用本文的LZW算法来进行压缩。原始图像zuoye如图1所示，是一个大小为486 Byte，宽度和高度均为12像素的彩图像。本文用VC做的界面图，选择zuoye为压缩文件后，单击编码按钮就可进行压缩操作。压缩结果如图2所示。
        从图2可知，原文件大小为486字节，利用LZW算法进行压缩后为132字节，压缩率为27%。
        四、结论
        通过实验结果可以看出，本文提出的算法是一种有效的无损数据压缩算法。许多学者一直在对LZW及其派生算法加以不断地改进和完善,使之成为了当今数据压缩的主流算法。
        ［参考文献］
        ［1］David Salomon.吴乐南,等.数据压缩原理与应用（第二版）［M］.北京:电子工业出版社,2007.
        ［2］侯阳.数据压缩技术及C语言实例［M］.北京:学苑出版社,2005.
        ［3］张凤林,刘思峰.一个改进的LZW数据压缩算法［J］.小型微机计算机系统，2010，27（10）.
        ［4］林小竹,籍俊伟.一种改进的LZW压缩算法［J］.计算机工程,2009,31（14）.
        ［5］寇海洲,夏江涛,赵文东.LZW算法C语言实现及改进［J］.淮阴工学院学报,2007,(12).

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。