LZW压缩编码

LZW压缩编码（精选4篇）

LZW压缩编码 篇1

0 引言

基于计算机控制的设备和电力电子装置的大量投入使用,对电能质量提出了更高的要求[1,2]。电能质量数据作为对电能质量改进控制的基础,为电能质量的分析和针对性补偿提供依据,为电网事故快速分析、事故快速定位、事后系统的快速恢复提供帮助。为获取电能质量信息,需要在高采样率下对电能质量数据进行长时在线记录,大量的电能质量数据必须经过压缩后存储和传输[3]。与此同时,为了掌握尽可能多的电能质量信息和节省硬件开销,要求数据压缩算法具有大的压缩比、低的失真度和小的计算量[4]。

在国内外学者提出的众多电能质量数据压缩算法中,FFT方法对暂态畸变波形压缩误差较大,且存在“旁瓣”和“频谱泄漏”现象;基于小波变换的各种压缩方法压缩比高、失真小,但是对稳态信号的压缩不理想,且计算量大,实现困难;而数据的编码压缩虽然实现容易、误差小,但是压缩率低,不能根据电能质量数据特点进行针对性压缩,常作为辅助算法对数据进一步压缩[5,6,7,8]。文献[5]提出了一种将FFT、小波包变换和LZW编码相结合的压缩算法,得到了很好的压缩性能,但是此算法需要通过二进小波变换检测待压缩信号的奇异性,然后对稳态和暂态信号分别进行FFT和WPT压缩,最后进行LZW编码压缩,计算量和硬件实现难度都非常大。

本文充分考虑电能质量数据特点,结合数据的周期性、对称性以及奇偶性,提出了一种将模式相似度与LZW压缩编码相结合的新型压缩方法,并在MATLAB7.10环境下进行了验证实验,与一维离散小波数据压缩性能进行对比,验证了该方法的效果和可行性。

1 数据压缩方法

本文提出的数据压缩和重构算法如图1所示。

电能质量数据具有周期性、关于1/4周期的对称性,是关于原点的奇函数,利用这些特点可以用1/4周期的数据完整地再现整个周期的波形。本压缩算法中,首先以1/4周期为单位,对原始信号进行基于模式相似度归一化距离测度的畸变判定,对畸变的数据进行完整记录的无损压缩,对未畸变数据用基准数据替换,而只记录个数的有损压缩;然后,因为电能质量正常波形和大多数扰动波形是周期性的,可以看成是围绕理想波形的波动,将故障数据与理想波形做差以降低数据幅值,减小编码所需位数和增加重复的字符量,为提高后面LZW编码压缩的压缩比奠定基础;最后将数据进行LZW编码压缩。数据的重构是压缩的逆过程。

2 模式相似度归一化距离测度

模式相似度距离测度广泛应用于模式识别领域,用于判定对比两向量的相似性,具有计算量小、容易实现等特点。常用的距离测度有:明氏距离、欧氏距离、绝对值距离、马氏距离、Camberra距离和归一化距离等[9]。欧氏距离和绝对值距离是明氏距离的特殊形式,欧氏距离放大了较大元素的差别在距离测度中的作用,绝对值距离则对向量中每个元素的差别同等对待;马氏距离则强调各元素之间的相关性;Camberra距离考虑了元素差值在本身的比重,做了自身的标准化;归一化距离将欧氏距离和Camberra距离相结合,在突出较大元素差值的同时,兼顾了各元素在总体的比重,具有很好的畸变检测能力,不受量纲限制,具有一定的抗噪声干扰能力[10,11]。图2是电压暂降归一化距离测度压缩效果图。图3给出了基于模式相似度归一化距离数据压缩流程图。以1/4周期数据为单位,逐次与基准数据进行归一化距离测度判定是否发生畸变,只记录畸变的数据和未畸变数据个数,并用畸变数据替代基准波形。

归一化距离计算方法为:

其中,x和y为需要检测的2个输入向量。

3 LZW数据压缩编码

LZW压缩编码是由Lemple-Ziv-Welch三人共同创造的一种新颖的基于字典模型的无损压缩方法,采用了一种先进的串表压缩[5,12]。LZW压缩编码中定义了字符流、字符、字符串、前缀、后缀、标号、根等概念。首先建立一个字符串表,把每一个第一次出现的字符串放入字符串表中,并用一个数字来表示,这个数字与此字符串在串表中的位置有关,并将这个数字存入压缩文件中,如果这个字符串再次出现,即可用表示它的数字来代替,并将这个数字存入文件中。原始数据串中子串重复得越多,压缩效果越好。LZW压缩编码的优点还在于不管是在压缩还是解压缩的过程中都能正确地建立这个字符串表,压缩或解压缩完成后,这个串表又被丢弃,使压缩效率有了较大提高。

LZW压缩编码实现的流程图如图4所示。编码开始时,字典中包含所有可能的根,且前缀为空;读取字符流中的下一个字符C,作为后缀与前缀组成字符串String;判断字典中是否存在当前String,如果存在,用String更新前缀,否则输出前缀,将String添加到字典,并用后缀更新前缀;判断是否已经是最后一个字符,如果是,输出表示前缀的标号结束,否则继续读取下一字符。

LZW的解码过程为编码的反过程。

4 实验结果与分析

为了验证所提压缩算法的压缩性能,在MATLAB7.10环境下,对6种常见的电能质量扰动信号进行了数学建模[13]、归一化距离测度畸变检测能力和抗干扰能力检测、压缩实验,包括暂升、暂降、中断、振荡、谐波、闪变等。采样率51.2 KSPS(每秒51 200个采样点),信号整体持续0.6 s(30周期),对于暂态故障信号持续时间为0.06 s(3周期),均含有30 d B高斯白噪声。

4.1 归一化距离测度畸变检测和抗干扰能力验证

为了检测归一化距离测度的畸变检测能力和抗干扰能力,在已建立的6种典型电能质量信号数学模型的基础上,按照IEEE标准,设定参数为最小临界值,进行畸变检测能力实验。实验中利用正常信号和6种典型电能质量扰动信号,添加40~60 d B的白噪声,以1/4周期的数据计算归一化距离范围。

图5给出了正常信号和6种典型电能质量扰动信号的归一化距离测度随信噪比(SNR)变化的波形。由图5可知,随着信号中噪声的增加,正常信号和6种扰动信号相对于正常信号的归一化距离测度有轻微的增大,但是直到信噪比为40 d B时,正常信号的归一化距离测度仍然小于6种扰动信号中归一化距离测度最小的谐波信号的最小值。因此,归一化距离测度可以很好地检测出扰动信号且具有一定的抗干扰能力。

4.2 压缩算法性能测试

压缩性能指标主要包括均方误差百分比(PRD)、压缩比(CR),分别如式(2)和式(3)所示:

其中,Sin为原始信号的数据量,Sout为压缩后信号的数据量,d(k)为原始信号,f(k)为重构得到的信号,N为信号的长度。

图6、7分别给出了中断、暂态振荡的压缩效果图。

表1给出了常见的6种电能质量扰动信号参数[13]和压缩效果指标。可知,在30 d B的强白噪声干扰下,除了电压闪变扰动的均方误差百分比为5.3%,其他扰动均在5%以下。对于电压暂降、暂升、中断和稳态的电压谐波,只需记录起始1/4周期、畸变产生和恢复时1/4周期的数据即可,有很高的压缩比;对于波形数据变化较为频繁和剧烈的波动和暂态振荡信号,往往需要记录多个1/4周期的数据,以保证较低的均方误差,导致压缩比相对较低。在模式相似度归一化距离测度压缩的基础上,将记录的数据与理想波形做差后,采用LZW编码压缩,大幅提高了压缩比,平均达到88.9。试验中为0.6 s内发生一次畸变,当1 min发生10次畸变时,平均压缩比将达到889。可见,此算法压缩比高,均方误差低,满足电能质量分析的要求。

注:A代表模式相似度;B代表模式相似度+LZW。

为了更充分地检验本文算法的性能,与一维离散小波变换(1-D-DWT)的电能质量数据压缩算法进行了性能比较。1-D-DWT采用压缩性能良好的db2[14]小波进行6层分解,利用分层能量阈值法[8]进行电能质量数据压缩,压缩性能见表2。各类扰动信号的参数与表1相同,在6层充分的小波分解下,6种典型信号均方误差百分比保持在3.56%~4.52%之间,具有更好的重构性能,但是压缩比平均为63.15,低于本文提出的压缩算法,并且基于模式相似度和LZW的压缩算法计算量远低于小波变换,更易于实现。综上,利用模式相似度和LZW的压缩算法性能优于一维离散小波变换的压缩算法。

5 结论

通过对常见的6种电能质量扰动数据的压缩实验分析及与1-D-DWT压缩性能对比表明,在强噪声下,本文提出的基于模式相似度和LZW压缩编码的数据压缩方法虽然在重构信号的均方误差百分比上不如1-D-DWT数据压缩算法,但是其均方误差百分比只有闪变信号超过了5%,能够满足分析要求;另一方面则可以达到更高的压缩比,平均为88.9,并且计算简单,硬件要求低。而LZW压缩编码的引入也大幅提高了基于模式相似度压缩算法的压缩比。本压缩算法受单位时间内的故障次数和故障偏离正常波形的幅值影响严重,故障次数越少、偏离幅度越低,则压缩比越高。

LZW压缩编码 篇2

小波分析用于图像去噪处理，主要是针对图像信号与噪声信号经小波变换后在不同的分辨率呈现不同的规律，在不同的分辨率下，设定阈值门限，调整小波系数，达到图像去噪目的。

在小波系数进行取舍之前，实际上按照一定准则（或者阈值化）将小波系数划分为两类：一类是重要的、规则的小波系数；另一类是被看作非重要的或者受噪声干扰较大的小波系数。通常以小波系数的绝对值作为小波系数的.分类单元。小波系数绝对值趋向于零，意味道着小波系数所包含的信息量并且强烈地受噪声干扰。最常用的阈值化去噪方法：一是默认阈值消噪处理，即在消噪处理过程中采用程序中设定的阈值，对分解信号进行分类处理，以求消除噪声；二是给定软（或硬）阈值消噪处理，阈值通过某一个经验公式获得，该阈值比默认的阈值去噪效果更有说服力。

对于“软阈值化”，绝对值小于阈值δ的小波系数数值用零代替；绝对值大于阈值δ的小波系数数值用δ来缩减。如下所示：

式中，W表示小波系数的数值；sgn(・)是符号函数，当数值大于零，符号为正，反之符号为负。对于“硬阈值化”，仅仅保留绝对值大于阈值δ的小波系数，并且被保留系数与系数相同（没有被缩减），如下式所示：

两种方法各有差异，前者具有连续性，在数学上容易处理，后者更接近实际应用。

阈值化处理的关键在于选择合适的并值δ。如果阈值门太小，处理后的信号仍有噪声存在；阈值太大，重要的图像特征将被滤掉，引起偏差。大多数阈值的选取过程是针对一组小波系数，即根据本组小波系数的统计特性，计算出一个阈值δ。Donoho等提出了一种典型的阈值选取方式，从理论上说明阈值与噪声的方差成正比，为：

其中，Nj表示第j层子带上小波系数的个数。

LZW压缩编码 篇3

1 LZW算法

LZW算法使用一种类似查字典的方式来进行压缩, 通常针对计算机系统中的8位ASCII字符进行压缩。基本原理是将输入的字符累积为字符串, 把已出现的字符串作为词条存入字典, 对重复出现的字符串输出其在字典中的位置而不是字符串来达到压缩数据的目的。

LZW算法流程主要是字典的维护和查询, 字典包含D项词条, 每项词条由m位前缀和n位后缀组成, 后缀位宽与输入数据位宽相等, 且满足D=2^m。压缩算法流程如下: (1) 字典的前256项初始化为8位ASCII字符集; (2) 将第一个字符作为后缀与前缀0组成待查数据进行查询, 必与字典初始化项中的某一词条匹配, 将前缀更新为匹配地址; (3) 将下一个输入字符作为后缀与前缀组成待查数据进行查询, 如果不匹配则将待查数据作为新词条写入到字典中, 将前缀输出并更新前缀为后缀的匹配地址, 如果匹配则将前缀更新为匹配地址, (4) 依次输入字符并按上步进行处理。LZW算法的解压缩流程与压缩流程类似, 区别在于解压缩查询字典时输出的不是匹配地址而是匹配字符或字符串, 解压缩算法可从压缩数据中重构出与压缩算法相同的字典, 并且压缩与解压缩都不用存储字典, 易于工程实现。LZW算法充分利用了数据的重复性, 只需扫描一次数据就可以完成压缩, 能够实时处理数据。

2 FPGA构建CAM字典

L Z W算法的关键在于构建字典和读写操作时间。传统的L Z W算法实现中多使用RAM (随机存储器) 来存储字典, 查找词条时需逐个查询从而造成压缩时间过长。建立字典地址与输入数据的哈希函数可提高查询速度, 但为解决地址冲突问题还要增加额外的开销。本文将CAM (内容可寻址存储器) 用于存储字典, CAM的原理是将输入数据与存储的数据进行比较, 给出是否匹配以及匹配地址, 这与L Z W算法的字典查询是相符的, 利用C A M构建字典简化了对字典的读写操作。

本文使用Virtex系列FPGA基于BRAM (块存储器) 的实现方法来构建CAM, 这种方法读写时间都只需一个时钟周期, 适合存储字典。CAM16x8表示可存储16项8bit数据, 实现框图如图1所示。图中RAM_Dual为BRAM, 将端口A配置成4096项1bit数据, 端口B配置成256项16bit数据, RAM_Erase由8个分布式RAM构成, 存储CAM中每个地址已存的内容。

C A M 1 6 x 8的写操作分为擦除和写入两个步骤。擦除是从RAM_Erase模块中读出地址addri中已存的数据, 作为RAM_Dual模块端口A写地址addra的高8位, addra的低4位为addri, 数据dia写0表示这一地址存储的数据已清零;下一时钟周期再进行写操作, 将datai与addri组合为addra, 数据dia写1表示这一地址已存储数据, 同时更新RAM_Erase中地址addri存储的数据为datai。当查询数据datam在CAM中的地址时, 将datam作为RAM_Dual模块端口B的读地址, 可读取数据dob, 将dob进行按位或运算, 如为1则表示匹配, 为0则不匹配, 并按照one-hot形式对dob进行解码, 获得实际匹配的地址addrm。one-hot是一种数据编码方式, 例如4bit十六进制数据0x7可表示为16bit二进制数据0000000010000000, CAM就是利用这种方式实现的。

3 FPGA资源和性能分析

V i r t e x系列F P G A中的B R A M单元可配置成C A M 1 6 x 8或CAM16x10或CAM16x11, 通过并行组合多个CAM单元可扩展存储位宽, 串行组合可扩展存储深度。令n=8, m=10, 11, 12, 13, 表1给出了不同的字典容量所需的B R A M单元数量。

本文使用仿真工具对实际采集的低频信号原始采样数据和傅里叶变换后的频谱数据进行了仿真分析, 两种数据均为16bit, 需先将其转换为两个8bit数再进行压缩。压缩算法的性能用压缩率来表示, 定义为压缩后数据量与原始数据量的比值, 在不同的字典容量条件下, 对100组每组80k B的数据进行压缩, 将压缩率取均值, 表2给出了字典容量与压缩率间的关系。

从表2可以看出, 频谱数据的压缩率随字典容量增加逐步下降, 在字典容量为8192x21bit时压缩率变换不大, 而采样数据的压缩率甚至略有增加, 这与字典容量扩大带来的输出位宽扩大有关。再结合所占FPGA资源, 字典容量选取2048x19bit就能获得较好的压缩率, 对两种数据都能满足压缩传输的工程需求。

4 结语

本文将基于F P G A实现的C A M存储器应用于L Z W算法的字典存储, 实现了对采集数据的实时无损压缩。对字典规模、FPGA占用资源与压缩率之间的关系进行了分析, 在FPGA资源占用率与压缩率之间找到平衡点, 对FPGA器件选型有一定的指导意义。这种实现方案不仅可用于原始采样信号和频谱数据的压缩传输, 也可用于文本、图像等其他数字信号的压缩传输, 具有较好的通用性。

参考文献

[1]陈晋敏, 黄春明, 周军.激光雷达数据无损压缩的FPGA实现[J].军事测控技术, 2007, 15 (1) :100-102.

[2]陈世海, 裴东兴, 张琦.FPGA实现滑动平均滤波算法和LZW压缩算法.电子设计工程, 2010, 18 (2) :67-69.

[3]An Overviw of Multiple CAM Designs in Virtex Famliy Device[M], Xilinx, Xapp201, 1999, 9.

LZW压缩编码 篇4

遥感技术增强了人类观察和探索世界的能力,扩展了人类可以观测的范围,缩短了观察宏观现象所需的时间,同时使得因自然条件恶劣无法实地观察的环境也能用遥感技术得以观察。人以眼睛进行观察活动时,可以快速处理观察到的图像并作出响应。应用遥感技术时,若能提高快速响应能力,将大大增强遥感技术的效果。但是,提高系统响应速度的一个巨大挑战来源于在带宽一定的条件下不断增大的遥感数据量和远距离的传输。数据压缩技术在发送端通过去除数据冗余而减少实际传输的数据量,从而缩短了数据传输时间。

基于字典的数据压缩算法在许多应用领域取得了良好的压缩效果。文献[1]提出的TCP自适应压缩传输方案中自适应压缩器采用基于字典的压缩方法与Huffman编码相结合的压缩编码方案。文献[2]对三大类共10种压缩的全文自索引方法进行了分析和比较,基于字典的LZ压缩算法的全文自索引算法在索引建立、定位和提取几个方面有明显的优势。

基于字典的数据压缩算法是一类无损压缩算法,其基本思想是,在数据中普遍存在着结构冗余,数据中的某些“词组”会重复出现。因此,基于字典的压缩算法使用滑动窗口或者显式的字典,用于存储已经压缩的数据中可能会在将来重复出现的“词组”,当发现再次出现的词组时,就发送字典的索引代表词组本身。当用于表示字典索引的数据量少于表示词组所需的数据量时,能够取得好的压缩效果。在基于字典的数据压缩算法中,字典容量大小与压缩效果有着密切的联系。本文对此进行研究,并提出了改进方法。

1 基于字典的压缩算法LZW及相关改进算法分析

1.1 应用LZW算法的数据压缩系统介绍

应用LZW算法[3]的压缩系统的编码过程一般可以用图1所示。

LZW压缩部分(即Ⅰ过程)在编码端完成两项工作:其一是在字典中查找当前的词组是否存在。如果存在,则继续查找是否存在更长的词组;否则,用对应字典索引替代当前词组作为编码输出。其二是将当前字典不存在的词组作为新词组加入字典,完成字典的更新。传统LZW算法每次形成并加入长度增加一个符号的新词组;LZMW[4]和LZAP等算法[5]在如何形成新词组方面做出改进,改进算法使字典适应输入数据的速度加快。

将LZW压缩后数据Y编码成信道可以传输的部分(即Ⅱ过程)主要包括定长编码和变长编码两种方式。记信源符号种类为s,信道符号种类为r。定长编码对不同信源符号分配不同码字,并满足单一可译原则[6],不同码字长度相同,为(即对logrs向上取整);变长编码将长度较短的码字分配给出现概率大的信源符号,将长度较长的码字分配给出现概率小的信源符号[6],从而使得LZW压缩后数据Y编码后产生的码字长度的统计平均更短。

1.2 应用LZW的压缩系统前后数据特性分析

如图1所示,应用LZW算法的压缩系统有过程Ⅰ和过程Ⅱ两个处理阶段。过程Ⅰ将值域为[Pmin,Pmax]的待压缩数据X处理形成值域为[Vmax-1]的数据Y,其中Vmax是LZW的字典容量大小。例如,用8 bit表示一个像素点的灰度图像使用字典容量为216的LZW算法经过程Ⅰ处理,是将值域为[0,28-1]的数据流X处理形成值域为[0,216-1]的数据流Y。

过程Ⅱ将数据流Y用信道符号集{α1,α2,…,αr}编码成适应信道传递的符号流Z。例如,二元离散信道符号集为{0,1},即α1=0,α2=1。则过程Ⅱ将值域为[0,216-1]的数据流Y按照单一可译的原则编码成{0,1}的比特流。

可以看出,在提高LZW压缩效率时,不仅应该关注由过程Ⅰ决定的,也应该关注由过程Ⅱ决定的反映了数据源Y用信道符号集编码的平均码长。

如1.1节所述,过程Ⅱ可以采用定长编码和变长编码两种方式将数据流Y转化为Z。采用定长编码取得的平均码长为。采用不同的变长编码算法会得到不同的平均码长,根据信源特性仔细设计的变长编码或者自适应的变长编码[7]往往可以取得比定长编码更短的平均码长。但变长编码获得的平均码长不能无限制小,已证明[6]在保证单一可译的前提下,平均码长的下界满足式:

其中,H(S)表示信源信息熵,即数据流Y的信息熵,r表示信道符号种类。这里以符号集为{0,1}的信道为例,因此上式改写为:

对于单一可译码平均码长的下界,可以通过扩展信源或采用优秀的编码算法如Huffman,算术编码的方式使平均码长接近这个下界[6]。Gzip压缩软件的一个核心部分就是LZ压缩算法与Huffman编码的组合。因此,本文用数据流Y(经过程Ⅰ处理后的数据)的信息熵作为衡量指标来比较在待压缩数据源X相同的情况下,过程Ⅰ使用不同的压缩算法产生的数据流Y可以达到的最短平均码长。

1.3 LZW改进算法分析

DTLZW算法[8]提出传统LZW是基于平稳遍历信源的假设,但是实际信源多为局部平稳。因此提出双串表,也可以看作是双字典的改进算法,利用信源是局部平稳的特点,在当前字典不能很好符合当前局部时(表现为在当前串表中找到匹配的概率降低),快速切换至另一个串表,从而保证压缩效率能维持在较高的水平上。

LZSWH算法[9]利用LZ77和LZ78两类压缩算法对于不同类型的数据压缩性能不同,将这两类算法的代表LZSS和LZW结合,并加入了H参数,控制LZSWH向LZSS和LZW的偏向程度,得到了对于不同类型数据比单一算法更好的适应性。

文献[10]提出一种综合了LZW远距离记忆性好和LZSS对于信源特性的快速适应特性优点的压缩算法,每轮压缩均先后使用LZW与LZSS进行编码,并采用能搜索到更长匹配的编码方式进行输出,同时用1 bit来标示采用的编码方式是LZW还是LZSS。另外因为小序号字典项输出时占用bit数少,但是常常被命中率低的字典项占用,提出将命中率低的字典项,主要是生成较长的字典项过程中产生的中间字典项,逆序加入字典,分配较大的字典序号,从而提高小序号字典项的命中率,增加了压缩效率。

LZC算法将字典的初始容量预设得较小,因此初始阶段,Y的平均码长将比较小。当字典装满时,将字典容量动态增长为2倍,此时生成数据Y的平均码长也增加1。如此重复,直至字典的大小达到预设的最大容量。LZC对字典采用动态增长的手段,降低了Y数据流的平均码长。例如,最大字典容量为216的LZW和LZC算法,LZW产生的数据流Y采用定长编码的平均码长为16 bit,LZC字典中项数少于初始容量512项时,产生的数据平均码长为9 bit;当字典逐渐装满,达到512项时,字典容量增长为2倍,产生数据的平均码长为10 bit;如此重复,直至字典达到216项,产生数据的平均码长为16 bit。因此LZC产生的数据Y的平均码长短于LZW产生的数据的平均码长。

LZT算法的一个特点是对数据流Y用phased-in码[11]进行编码,这将节约开始阶段的bit数,降低平均码长,但随着字典的装满,这部分的作用将逐渐变小。

通过实验结果分析,如表1所示,LZW或现有的各改进算法在字典容量增大时都会出现对数据流Y进行过程Ⅱ编码时平均码长快速增大的现象,这是不利于使用LZW的压缩系统的压缩效果的。字典容量越大,数据流Y的信息熵越大,使平均码长的下限越长。

但同时也不能过度限制字典容量的大小,因为大字典可以保存更多的词组,从而能找到更多的匹配,有利于压缩。因此,需要在保持大字典容量的情况下,在降低数据流Y的信息熵方面改进,以取得更低的平均码长。

2 改进算法的提出

LZW算法的大字典容量能保存更多词组,找到更多的匹配,所以,需要在保持大字典容量的前提下降低经过程Ⅰ处理的数据流Y的信息熵。

对不同图像进行观察,发现图像内部普遍存在空间周期性,即某个图像特征往往会重复出现,如图2所示。图3所示为某图像按行扫描后的像素曲线图,图中B段图像曲线与已经发生的A段曲线极为相似,说明这两段图像代表相似的图像模式。若B中当前的一个词组在A中F处找到匹配,说明当前区域B与区域A中有一部分特征相同,则B与A将以高概率属于相似的图像模式,即B中下一个词组也将以高概率落在这个图像模式中。因此在每次找到较长的字典项匹配后,我们可以记录下此次匹配的位置,即区域A中的F处,下轮搜索时就在F处的附近进行。

因此,本文提出以下改进处理。首先,将字典设计成能够保存图像空间周期性的结构,即空间上相邻的词组在字典中的位置也相邻。为了使字典具有这种性质,在将新词组写入字典时,用下式确定写入字典的位置:

其中Indexi代表第i个词组加入字典的位置,MOD为模运算,Vmax代表大字典的容量,Vstart代表LZW改进算法中不能被新字典项覆盖的部分,一般用字典的[0,Vstart-1]写入所有可能的单个信源符号,对于用8 bit表示一个像素点的灰度图像来说,Vstart为256。式(3)可以简单解释为“循环写入”,例如,对于字典容量为216项的改进字典,若上一项词组位置为4096,则下一项写入位置4097;若上一项位置为65 535,则下一项写入位置256。

这种改进字典中各项的相对位置如实反映了数据中存在的空间相关性。改进算法利用这种保存在字典中的空间相关性做如下操作,在每次搜索及输出之前,结合上次在字典中找到匹配的位置,做出是使用全部字典还是使用局部字典的决定,相应的处理如下:

因此,利用图像中的空间周期性,很多数据都可以在局部字典中找到;而在局部字典中找到的匹配可以用该匹配在局部字典中的相对位置代替匹配在整个大字典中的绝对位置作为输出。如果使用LZW,过程Ⅰ输出匹配在大字典中的绝对位置,因此数据流Y的值域为[0,Vmax-1]。而用本文提出的改进算法,如果上个词组在字典中找到匹配,则输出当前词组在局部字典中的相对位置,相对位置的值域为[0,2 L-1]。虽然改进算法编码后产生的数据流Y的值域相同,但分布不同。改进算法将一些分散在字典中各位置的输出集中在一个相对小的范围中,主要成分变为了[0,Vstart+2L],各成分概率分布更加不均匀,从而降低了数据流Y的信息熵。

综上所述,本文提出的改进算法的流程如图4所示。

3 改进算法实验

本文首先对一948×450的图像用LZW和本文提出的改进算法分别进行压缩(即图1中的过程Ⅰ),并对使用不同算法产生的数据流Y中各符号概率分布进行统计,并对出现频数取log得到直方图对比,即图5所示。由图5左侧直方图可以看出,在过程Ⅰ中用LZW处理后产生的数据流Y中各符号近似于均等分布,此时数据流Y的信息熵较大;由右侧直方图看出,若运用本文提出的改进算法,此时数据流Y的分布更加集中,因此信息熵更低。因此,用改进算法更加有利于过程Ⅱ取得更短的平均码长。

然后对此948×450的图像在图1的过程Ⅰ中采用不同字典容量,不同算法分别进行压缩,并计算产生的数据流Y的信息熵或最短平均码长,得到表2所示。从表2看出,改进算法在不同字典容量都能取得比LZW和LZC更加低的信息熵,在大字典容量时取得的降熵效果更加明显。

最后对53幅图像数据分别用相同容量的LZW,LZC和本文实现的改进算法加以压缩,将压缩后数据的平均信息熵进行比较,得到图6所示。改进算法相较采用动态增长字典的LZC取得了7.47%~20.3%的优化;相比LZW与熵编码的组合能取得2%~16.9%的降熵,说明在过程Ⅰ中采用改进算法能取得较好的降熵效果。图6同时说明改进算法较LZW算法能对不同特性的数据取得普遍的降熵效果,说明了本文提出的改进算法的有效性。

4 结语

本文对基于字典的压缩算法LZW进行了研究。研究结果显示:基于大容量字典的LZW压缩算法的相比基于小字典的LZW算法在压缩后数据的平均信息熵方面显著增大,这对于后续进行熵压缩编码不利。通过实验发现,数据中存在普遍的空间周期性,这为提出基于大容量字典的降熵压缩算法提供了可能性。本文使用在大容量字典中自动选取的局部字典进行实际压缩和编码,使压缩后数据流Y中各成分的概率分布更加集中,降低了平均信息熵。经实验验证,改进后的算法在降低压缩后数据的平均信息熵方面取得了2%~16.9%的优化。

今后的研究将集中在以下两个方面,其一,根据本文采用的局部字典选择策略和已有的实验结果,对局部字典选择算法进一步改进,以达到能在选择出的局部字典中以更大概率找到匹配。再配合以本文提出的改进算法本身具有的低平均信息熵特性,从而取得更好的压缩效果。其二,针对本改进算法使用局部字典进行搜索和输出的特性进一步设计字典的数据结构,优化本改进算法的运行效率。同时进一步分析本改进算法产生的数据流的分布特性,为下一步使用其他压缩算法提供先验知识,从而提升工程运用本改进算法的系统整体处理速度。

参考文献

[1]牟璇,王俊峰,王敏,等.TCP自适应压缩传输方案研究[J].计算机应用与软件,2013,30(11):279-282.

[2]路炜,刘燕兵,王春露,等.压缩的全文自索引算法研究[J].计算机应用与软件,2014,31(3):11-15,35.

[3]Terry A Welch.A Technique for High-Performance Data Compression[J].IEEE Computer,1984,17(6):8-19.

[4]Miller V S M N.Wegman IEEE International Conference on Digital Technology[C]//Spanning the Universe:Communications,1988.Berlin,Springer,1988:131-140.

[5]Salomon David,Motta Giovanni.Handbook of data compression[M].London:Springer,2010.

[6]姜丹.信息论与编码[M].安徽:中国科学技术大学出版社,2004.

[7]吴乐南.数据压缩[M].北京:电子工业出版社,2012.

[8]吴宇新,余松煜.对LZW算法的改进及其在图象无损压缩中的应用[J].上海交通大学学报,1998,32(9):112-115.

[9]华强.LZ77和LZ78在数据压缩中的组合带参运用[J].小型微型计算机系统,2000,21(2):100-104.

[10]崔业勤,高建国.基于“虚段”方法的LZ混合无损压缩算法[J].计算机应用与软件,2007,24(3):140-141.