嵌入式织造系统无损压缩算法研究

卢小杰，叶明全，黄道斌

皖南医学院计算机教研室，安徽芜湖，241000



嵌入式织造系统无损压缩算法研究

卢小杰，叶明全，黄道斌

皖南医学院计算机教研室，安徽芜湖，241000

针对嵌入式织造系统内存不足和计算能力较低的问题，提出了一种改进的LZW压缩算法。采用变长编码和动态存储的方法保障数据字典的完整性和优化非编码数据，同时使用Hash表查找算法来缩短算法时间。实验结果表明：改进的LZW压缩算法压缩效果得到了提高，也优于其他压缩算法。

嵌入式技术；数据压缩；LZW算法；Hash表；WINRAR/WINZIP

为了满足现代纺织企业生产的需要，嵌入式技术被应用到纺织领域。嵌入式系统是一个精简的系统，一般由上下位机构成，需要把控制数据从上位机传输到下位机中，为了提高传输效率，还要进行数据压缩[1]。信息论表明：任何一种数据都有一定的冗余度，嵌入式织造系统中的纹板数据也不例外。纹版数据是一种控制纺织机械针脚变换的二进制流数据，针脚下降(冲孔)表示为1，针脚上升(不冲孔)表示为0，可以看作0、1的二进制数据流，但由于这种数据0、1交替比较密集，不适合使用行程编码方式和算术编码方式。常用的无损压缩算法有Huffman、LZSS、LZW和WINZIP/WINRAR等，但不同算法针对不同的数据有各自的特点。因此，本文在前人研究的基础上针对LZW压缩算法进行改进，并且与其他无损压缩算法进行比较。

1 LZW压缩算法

LZW以其压缩过程实现简单、程序代码方便简洁、对硬件要求低等特点被用于嵌入式系统中。LZW压缩算法是对LZ78算法的改进，只保留第一个字段的标志位，只有一个指针指向字典。LZW压缩算法凭借其较低的算法复杂度和较易实现的特点被应用在数据压缩的各个方面，产生了多种变体，如ARC、RKARC、PKZIP等压缩方式；实际应用也比较广泛，如GIF图像压缩[2]、远程故障诊断[3]等。这种压缩算法实现较简单，压缩效果好。另外，它还是一种字典编码方式，动态生成字典。在织造系统通信过程中，不需要把字典传输到下位机上。解压缩是压缩的完全逆过程，解压中动态生成一个与编码字典相同的字典，提高了数据传输效率。

1.1 LZW压缩过程

LZW压缩算法一般有三个数据对象：数据流、编码表(码表)和编译表，在压缩过程中先自适应生成一个中间码表，预留256个字符空间作为字典，以后每个进入的字符与数据字典中的字符进行比较，匹配的则用2bit数字代替，然后存到压缩文件中。如原始字符串XYZZXXYZKKXXZZKY，X、Y、Z、K用数字表示：0-X、1-Y、2-Z、3-K。重复字符串有XY、ZZ，则表示成4-XY、5-ZZ，故编码后的字符码表示为45X4ZKKXX5KY[4]，短于原始字符串，对整个文件来说，压缩效果较好。

算法实现过程中，为了保证不会无限地扩大记录重复串的表，需要一个清空标识，当字符串超过一定长度时就清空，另外设置一个数据结束标识位。压缩完成后将码表丢弃。其压缩算法伪代码表示如下：

table[j]←all n single character,j=1,2,…，n

j←n+1

Prefix←the first character in CharStream

while((Code←next character)!=NULL)

Begin

If Prefix.Code is in table

Prefix←Prefix.Code

Else

CharStream←CW for Prefix

table[j]←Prefix.Code

j=j+1

Prefix←Code

End

1.2 LZW解压缩过程

压缩是动态生成码表，解压不需要上位机传输码表，解压可以和压缩同步建立数据字典，且生成方式一样。首先是把输入数据流(上位机中压缩后的数据)的前256个字符初始化为码表中的字符，再读入输入数据流，这些输入数据流包含指向字典的指针，用指针从字典中读取未压缩的字符并写入输出流(下位机中解压后的数据)。算法伪代码表示如下：

table[j]←all n single character,j=1,2,…，n

j←n+1

CW←the first code in CodeStream

Output←table[CW]

OldCode←CW

while((Code←next code word)!=NULL)

Begin

If CW is in table

Code←final character of table[CW]

Else

Code←final character of table[OldCode]

End if

Prefix←Table[OldCode]

table[j]←Prefix.Code

Output←Table[CW]

j=j+1

OldCode←CW

End

由上述程序伪代码可以看出：LZW算法实现简单，算法复杂度低，代码空间小，一般下位机的内存空间完全能满足其算法需求。另外，预先存入的256个字符的字典对于很多单片机都不成问题。

2 LZW压缩算法优化

2.1 变长编码和动态存储

传统的编码方式对不同大小的文件都使用12位的代码输出，前256个编码作为字典，256-4 096字符以匹配字符串的方式输出。对于较大文件的压缩，堆栈容易溢出，且压缩时间长，压缩效果差，刚开始压缩时，码表匹配数较少；对于较小文件，压缩效果也不明显，甚至出现负压缩现象。

本文的编码方式是采用动态编码长度来实现的，即一边建立数据字典一边进行数据压缩，码字是变长编码。另外传统的LZW压缩算法是直接存储最大编码位，这样浪费了存储空间，使得非编码位也需要同样的位数来存储，浪费一些高位空间，本文对此进行改进，按照编码长度的实际位来存储。动态编码存储可以保障字典的完整性，又可以作到对非编码数据的优化。为了在下位机中算法能够更好地实现，文本设置的字典长度为256字节。

2.2 Hash表查找建立码表

本文在算法实现过程中使用Hash函数构造字典，因为它构造简单，节省空间[5]，查找速度快，尤其随机查找方式也适合纹版数据处理。

本文使用拉链法解决冲突，用链地址法处理冲突[6]。假设查找表的字符有n个，算法中设置的Hash函数为：

H(k)=k%p

(1)

查找成功时的平均查找长度(ASLsucceed)为：

(2)

其中ci为查找第i条字符的比较次数。传统的LZW压缩的顺序查找方式查找成功时的平均查找长度：

(3)

由公式可以看出Hash表查找方式的平均查找长度要短很多，查找速度更快，效率更高，对硬件的要求更低。

3 与其他无损压缩算法比较分析

本文在研究LZW的算法同时，对比以下的无损压缩算法。

(1)动态Huffman压缩算法。动态Huffman压缩算法是常用的无损压缩算法[7]，代码实现简单，算法成熟，经常被人们改进后用在不同的嵌入式系统中。

(2)LZSS压缩算法。LZSS压缩算法也是单片机中常用的无损压缩算法，其算法较高的适用性和压缩效率而被应用于很多对硬件要求比较高和数据通信压缩的场合，如FPGA硬件实现压缩[8]和SPI信令压缩[9]等。

(3)精简的WINZIP/WINRAR压缩算法。WINZIP/WINRAR压缩是计算机中常用的无损数据压缩方法，具有较好的压缩效果，但是，如果直接用在单片机中显然是不合适的。在嵌入式织造系统中，需要把在PC机中复杂的WINZIP/WINRAR压缩方法精简，只保留核心算法。

WINZIP/WINRAR压缩一般是由两种无损压缩算法叠加而成，但又不是简单的叠加，一般先对数据文件进行分块处理，经过LZ77/LZ78压缩后再经过Huffman压缩处理[10]，如图1所示。这种压缩算法比单一的无损压缩算法占用的内存空间更大，不适合在内存较小的单片机中使用，但是，经过精简后的WINZIP/WINRAR压缩代码放在ADS工程中编译，可以看出其压缩代码有21 KB左右，解压代码为8 KB左右，解压程序中间变量空间需求为6 484 B，目前绝大多数单片机都满足这些内存要求。

图1 ZIP压缩过程示意图

4 仿真验证

本文使用型号M058LBN单片机，其内含有4KB RAM，内存大小完全满足算法实验需求。改进后的LZW压缩算法实验结果如表1所示。

表1 LZW压缩实验结果表

由实验结果可知：LZW压缩算法在嵌入式织造系统中能够实现且取得了不错的压缩效果。另外使用Hash表查找方式缩短了平均查找长度，减小压缩时间，满足了嵌入式织造系统较高的实时性要求。

本文同时把另外几种压缩算法与改进后的LZW压缩算法进行比较，在VS2010上编写压缩验证平台，如图2所示。

图2 压缩验证平台

对比以上压缩算法的实验结果如表2所示。

本文与常用的无损压缩算法进行对比发现：改进后的LZW压缩率较小，与Huffman压缩算法、LZSS压缩算法比较，压缩效果非常明显，几乎可以与WINRAR/WINZIP压缩效果媲美，但内存要求要远远低于WINRAR/WINZIP压缩算法，在单片机上能够更好地应用。经过上述分析得出：改进后的LZW压缩算法简单易行、压缩效果好、能够很好地在嵌入式织造系统上运行。

表2 改进的LZW与其他压缩算法对比表

5 结束语

本文主要针对LZW压缩算法进行三个方面的改进，经过改进后的LZW压缩算法与其他无损压缩算法比较，改进后LZW压缩算法具有更好的压缩效果和较小的内存要求，更易应用于嵌入式织造系统。这种无损压缩方法值得被推广至其他嵌入式系统中使用。

[1]王海威,倪宏,朱明,等.一种嵌入式系统多媒体文件快速传输协议[J].小型微型计算机系统,2011,2(2):208-213

[2]向涛,王安.安全的LZW编码算法及其在GIF图像加密中的应用计算机应用[J].计算机应用，2012，32(12):3462-3465

[3]胡平，张金钟.远程故障诊断终端的数据压缩技术研究与实现[J].计算机工程与应用，2012，48(34):130-135

[4]萨洛蒙.数据压缩原理与应用[M].2版.吴乐南,译.北京:电子工业出版社,2003:33-45

[5]Fouad Khelifi.Analysis of the security of perceptual image Hashing based on non-negative matrix factorization[J].IEEE Signal Processing Letters,2010,17(1):234-236

[6]裴小强,卫宏儒.基于Hash链的RFID安全双向认证协议[J].计算机应用,2014,34(S1):47-49,54

[7]Yin-Kai Lin,Shu-Chien Huang.A fast algorithm for Huffman decoding based ona recursion Huffman tree [J].The Journal of Systems & Software,2012,85(4):974-980

[8]王驰,王健,杨萌,等.一种新型的FPGA配置位流压缩算法[J].复旦学报:自然科学版, 2014,53(3):365-370

[9]马庆,吕玉琴.SIP信令压缩动态字典方案[J].计算机工程,2009,35(24):72-74

[10]李兵兵,王衍波,徐敏.基于ZIP文档格式的信息隐藏方法[J].计算机工程,2011,37(5): 155-160

(责任编辑：汪材印)

2015-08-30

安徽省教育厅自然科学研究重点项目“面向肿瘤基因表达数据的特征选择与集成分类研究”(KJ2014A266)。

卢小杰(1987-)，女，安徽阜阳人，硕士，助教，主要研究领域：数据处理、嵌入式技术。

TP311.13

：A

：1673-2006(2015)12-0096-03

10.3969/j.issn.1673-2006.2015.12.026