盧小杰，葉明全，黃道斌

皖南醫(yī)學(xué)院計(jì)算機(jī)教研室，安徽蕪湖，241000

?

嵌入式織造系統(tǒng)無(wú)損壓縮算法研究

盧小杰，葉明全，黃道斌

皖南醫(yī)學(xué)院計(jì)算機(jī)教研室，安徽蕪湖，241000

針對(duì)嵌入式織造系統(tǒng)內(nèi)存不足和計(jì)算能力較低的問(wèn)題，提出了一種改進(jìn)的LZW壓縮算法。采用變長(zhǎng)編碼和動(dòng)態(tài)存儲(chǔ)的方法保障數(shù)據(jù)字典的完整性和優(yōu)化非編碼數(shù)據(jù)，同時(shí)使用Hash表查找算法來(lái)縮短算法時(shí)間。實(shí)驗(yàn)結(jié)果表明：改進(jìn)的LZW壓縮算法壓縮效果得到了提高，也優(yōu)于其他壓縮算法。

嵌入式技術(shù)；數(shù)據(jù)壓縮；LZW算法；Hash表；WINRAR/WINZIP

為了滿足現(xiàn)代紡織企業(yè)生產(chǎn)的需要，嵌入式技術(shù)被應(yīng)用到紡織領(lǐng)域。嵌入式系統(tǒng)是一個(gè)精簡(jiǎn)的系統(tǒng)，一般由上下位機(jī)構(gòu)成，需要把控制數(shù)據(jù)從上位機(jī)傳輸?shù)较挛粰C(jī)中，為了提高傳輸效率，還要進(jìn)行數(shù)據(jù)壓縮[1]。信息論表明：任何一種數(shù)據(jù)都有一定的冗余度，嵌入式織造系統(tǒng)中的紋板數(shù)據(jù)也不例外。紋版數(shù)據(jù)是一種控制紡織機(jī)械針腳變換的二進(jìn)制流數(shù)據(jù)，針腳下降(沖孔)表示為1，針腳上升(不沖孔)表示為0，可以看作0、1的二進(jìn)制數(shù)據(jù)流，但由于這種數(shù)據(jù)0、1交替比較密集，不適合使用行程編碼方式和算術(shù)編碼方式。常用的無(wú)損壓縮算法有Huffman、LZSS、LZW和WINZIP/WINRAR等，但不同算法針對(duì)不同的數(shù)據(jù)有各自的特點(diǎn)。因此，本文在前人研究的基礎(chǔ)上針對(duì)LZW壓縮算法進(jìn)行改進(jìn)，并且與其他無(wú)損壓縮算法進(jìn)行比較。

1 LZW壓縮算法

LZW以其壓縮過(guò)程實(shí)現(xiàn)簡(jiǎn)單、程序代碼方便簡(jiǎn)潔、對(duì)硬件要求低等特點(diǎn)被用于嵌入式系統(tǒng)中。LZW壓縮算法是對(duì)LZ78算法的改進(jìn)，只保留第一個(gè)字段的標(biāo)志位，只有一個(gè)指針指向字典。LZW壓縮算法憑借其較低的算法復(fù)雜度和較易實(shí)現(xiàn)的特點(diǎn)被應(yīng)用在數(shù)據(jù)壓縮的各個(gè)方面，產(chǎn)生了多種變體，如ARC、RKARC、PKZIP等壓縮方式；實(shí)際應(yīng)用也比較廣泛，如GIF圖像壓縮[2]、遠(yuǎn)程故障診斷[3]等。這種壓縮算法實(shí)現(xiàn)較簡(jiǎn)單，壓縮效果好。另外，它還是一種字典編碼方式，動(dòng)態(tài)生成字典。在織造系統(tǒng)通信過(guò)程中，不需要把字典傳輸?shù)较挛粰C(jī)上。解壓縮是壓縮的完全逆過(guò)程，解壓中動(dòng)態(tài)生成一個(gè)與編碼字典相同的字典，提高了數(shù)據(jù)傳輸效率。

1.1 LZW壓縮過(guò)程

LZW壓縮算法一般有三個(gè)數(shù)據(jù)對(duì)象：數(shù)據(jù)流、編碼表(碼表)和編譯表，在壓縮過(guò)程中先自適應(yīng)生成一個(gè)中間碼表，預(yù)留256個(gè)字符空間作為字典，以后每個(gè)進(jìn)入的字符與數(shù)據(jù)字典中的字符進(jìn)行比較，匹配的則用2bit數(shù)字代替，然后存到壓縮文件中。如原始字符串XYZZXXYZKKXXZZKY，X、Y、Z、K用數(shù)字表示：0-X、1-Y、2-Z、3-K。重復(fù)字符串有XY、ZZ，則表示成4-XY、5-ZZ，故編碼后的字符碼表示為45X4ZKKXX5KY[4]，短于原始字符串，對(duì)整個(gè)文件來(lái)說(shuō)，壓縮效果較好。

算法實(shí)現(xiàn)過(guò)程中，為了保證不會(huì)無(wú)限地?cái)U(kuò)大記錄重復(fù)串的表，需要一個(gè)清空標(biāo)識(shí)，當(dāng)字符串超過(guò)一定長(zhǎng)度時(shí)就清空，另外設(shè)置一個(gè)數(shù)據(jù)結(jié)束標(biāo)識(shí)位。壓縮完成后將碼表丟棄。其壓縮算法偽代碼表示如下：

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解壓縮過(guò)程

壓縮是動(dòng)態(tài)生成碼表，解壓不需要上位機(jī)傳輸碼表，解壓可以和壓縮同步建立數(shù)據(jù)字典，且生成方式一樣。首先是把輸入數(shù)據(jù)流(上位機(jī)中壓縮后的數(shù)據(jù))的前256個(gè)字符初始化為碼表中的字符，再讀入輸入數(shù)據(jù)流，這些輸入數(shù)據(jù)流包含指向字典的指針，用指針從字典中讀取未壓縮的字符并寫入輸出流(下位機(jī)中解壓后的數(shù)據(jù))。算法偽代碼表示如下：

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算法實(shí)現(xiàn)簡(jiǎn)單，算法復(fù)雜度低，代碼空間小，一般下位機(jī)的內(nèi)存空間完全能滿足其算法需求。另外，預(yù)先存入的256個(gè)字符的字典對(duì)于很多單片機(jī)都不成問(wèn)題。

2 LZW壓縮算法優(yōu)化

2.1 變長(zhǎng)編碼和動(dòng)態(tài)存儲(chǔ)

傳統(tǒng)的編碼方式對(duì)不同大小的文件都使用12位的代碼輸出，前256個(gè)編碼作為字典，256-4 096字符以匹配字符串的方式輸出。對(duì)于較大文件的壓縮，堆棧容易溢出，且壓縮時(shí)間長(zhǎng)，壓縮效果差，剛開始?jí)嚎s時(shí)，碼表匹配數(shù)較少；對(duì)于較小文件，壓縮效果也不明顯，甚至出現(xiàn)負(fù)壓縮現(xiàn)象。

本文的編碼方式是采用動(dòng)態(tài)編碼長(zhǎng)度來(lái)實(shí)現(xiàn)的，即一邊建立數(shù)據(jù)字典一邊進(jìn)行數(shù)據(jù)壓縮，碼字是變長(zhǎng)編碼。另外傳統(tǒng)的LZW壓縮算法是直接存儲(chǔ)最大編碼位，這樣浪費(fèi)了存儲(chǔ)空間，使得非編碼位也需要同樣的位數(shù)來(lái)存儲(chǔ)，浪費(fèi)一些高位空間，本文對(duì)此進(jìn)行改進(jìn)，按照編碼長(zhǎng)度的實(shí)際位來(lái)存儲(chǔ)。動(dòng)態(tài)編碼存儲(chǔ)可以保障字典的完整性，又可以作到對(duì)非編碼數(shù)據(jù)的優(yōu)化。為了在下位機(jī)中算法能夠更好地實(shí)現(xiàn)，文本設(shè)置的字典長(zhǎng)度為256字節(jié)。

2.2 Hash表查找建立碼表

本文在算法實(shí)現(xiàn)過(guò)程中使用Hash函數(shù)構(gòu)造字典，因?yàn)樗鼧?gòu)造簡(jiǎn)單，節(jié)省空間[5]，查找速度快，尤其隨機(jī)查找方式也適合紋版數(shù)據(jù)處理。

本文使用拉鏈法解決沖突，用鏈地址法處理沖突[6]。假設(shè)查找表的字符有n個(gè)，算法中設(shè)置的Hash函數(shù)為：

H(k)=k%p

(1)

查找成功時(shí)的平均查找長(zhǎng)度(ASLsucceed)為：

(2)

其中ci為查找第i條字符的比較次數(shù)。傳統(tǒng)的LZW壓縮的順序查找方式查找成功時(shí)的平均查找長(zhǎng)度：

(3)

由公式可以看出Hash表查找方式的平均查找長(zhǎng)度要短很多，查找速度更快，效率更高，對(duì)硬件的要求更低。

3 與其他無(wú)損壓縮算法比較分析

本文在研究LZW的算法同時(shí)，對(duì)比以下的無(wú)損壓縮算法。

(1)動(dòng)態(tài)Huffman壓縮算法。動(dòng)態(tài)Huffman壓縮算法是常用的無(wú)損壓縮算法[7]，代碼實(shí)現(xiàn)簡(jiǎn)單，算法成熟，經(jīng)常被人們改進(jìn)后用在不同的嵌入式系統(tǒng)中。

(2)LZSS壓縮算法。LZSS壓縮算法也是單片機(jī)中常用的無(wú)損壓縮算法，其算法較高的適用性和壓縮效率而被應(yīng)用于很多對(duì)硬件要求比較高和數(shù)據(jù)通信壓縮的場(chǎng)合，如FPGA硬件實(shí)現(xiàn)壓縮[8]和SPI信令壓縮[9]等。

(3)精簡(jiǎn)的WINZIP/WINRAR壓縮算法。WINZIP/WINRAR壓縮是計(jì)算機(jī)中常用的無(wú)損數(shù)據(jù)壓縮方法，具有較好的壓縮效果，但是，如果直接用在單片機(jī)中顯然是不合適的。在嵌入式織造系統(tǒng)中，需要把在PC機(jī)中復(fù)雜的WINZIP/WINRAR壓縮方法精簡(jiǎn)，只保留核心算法。

WINZIP/WINRAR壓縮一般是由兩種無(wú)損壓縮算法疊加而成，但又不是簡(jiǎn)單的疊加，一般先對(duì)數(shù)據(jù)文件進(jìn)行分塊處理，經(jīng)過(guò)LZ77/LZ78壓縮后再經(jīng)過(guò)Huffman壓縮處理[10]，如圖1所示。這種壓縮算法比單一的無(wú)損壓縮算法占用的內(nèi)存空間更大，不適合在內(nèi)存較小的單片機(jī)中使用，但是，經(jīng)過(guò)精簡(jiǎn)后的WINZIP/WINRAR壓縮代碼放在ADS工程中編譯，可以看出其壓縮代碼有21 KB左右，解壓代碼為8 KB左右，解壓程序中間變量空間需求為6 484 B，目前絕大多數(shù)單片機(jī)都滿足這些內(nèi)存要求。

圖1 ZIP壓縮過(guò)程示意圖

4 仿真驗(yàn)證

本文使用型號(hào)M058LBN單片機(jī)，其內(nèi)含有4KB RAM，內(nèi)存大小完全滿足算法實(shí)驗(yàn)需求。改進(jìn)后的LZW壓縮算法實(shí)驗(yàn)結(jié)果如表1所示。

表1 LZW壓縮實(shí)驗(yàn)結(jié)果表

由實(shí)驗(yàn)結(jié)果可知：LZW壓縮算法在嵌入式織造系統(tǒng)中能夠?qū)崿F(xiàn)且取得了不錯(cuò)的壓縮效果。另外使用Hash表查找方式縮短了平均查找長(zhǎng)度，減小壓縮時(shí)間，滿足了嵌入式織造系統(tǒng)較高的實(shí)時(shí)性要求。

本文同時(shí)把另外幾種壓縮算法與改進(jìn)后的LZW壓縮算法進(jìn)行比較，在VS2010上編寫壓縮驗(yàn)證平臺(tái)，如圖2所示。

圖2 壓縮驗(yàn)證平臺(tái)

對(duì)比以上壓縮算法的實(shí)驗(yàn)結(jié)果如表2所示。

本文與常用的無(wú)損壓縮算法進(jìn)行對(duì)比發(fā)現(xiàn)：改進(jìn)后的LZW壓縮率較小，與Huffman壓縮算法、LZSS壓縮算法比較，壓縮效果非常明顯，幾乎可以與WINRAR/WINZIP壓縮效果媲美，但內(nèi)存要求要遠(yuǎn)遠(yuǎn)低于WINRAR/WINZIP壓縮算法，在單片機(jī)上能夠更好地應(yīng)用。經(jīng)過(guò)上述分析得出：改進(jìn)后的LZW壓縮算法簡(jiǎn)單易行、壓縮效果好、能夠很好地在嵌入式織造系統(tǒng)上運(yùn)行。

表2 改進(jìn)的LZW與其他壓縮算法對(duì)比表

5 結(jié)束語(yǔ)

本文主要針對(duì)LZW壓縮算法進(jìn)行三個(gè)方面的改進(jìn)，經(jīng)過(guò)改進(jìn)后的LZW壓縮算法與其他無(wú)損壓縮算法比較，改進(jìn)后LZW壓縮算法具有更好的壓縮效果和較小的內(nèi)存要求，更易應(yīng)用于嵌入式織造系統(tǒng)。這種無(wú)損壓縮方法值得被推廣至其他嵌入式系統(tǒng)中使用。

[1]王海威,倪宏,朱明,等.一種嵌入式系統(tǒng)多媒體文件快速傳輸協(xié)議[J].小型微型計(jì)算機(jī)系統(tǒng),2011,2(2):208-213

[2]向濤,王安.安全的LZW編碼算法及其在GIF圖像加密中的應(yīng)用計(jì)算機(jī)應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2012，32(12):3462-3465

[3]胡平，張金鐘.遠(yuǎn)程故障診斷終端的數(shù)據(jù)壓縮技術(shù)研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2012，48(34):130-135

[4]薩洛蒙.數(shù)據(jù)壓縮原理與應(yīng)用[M].2版.吳樂(lè)南,譯.北京:電子工業(yè)出版社,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]裴小強(qiáng),衛(wèi)宏儒.基于Hash鏈的RFID安全雙向認(rèn)證協(xié)議[J].計(jì)算機(jī)應(yīng)用,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].復(fù)旦學(xué)報(bào):自然科學(xué)版, 2014,53(3):365-370

[9]馬慶,呂玉琴.SIP信令壓縮動(dòng)態(tài)字典方案[J].計(jì)算機(jī)工程,2009,35(24):72-74

[10]李兵兵,王衍波,徐敏.基于ZIP文檔格式的信息隱藏方法[J].計(jì)算機(jī)工程,2011,37(5): 155-160

(責(zé)任編輯：汪材印)

2015-08-30

安徽省教育廳自然科學(xué)研究重點(diǎn)項(xiàng)目“面向腫瘤基因表達(dá)數(shù)據(jù)的特征選擇與集成分類研究”(KJ2014A266)。

盧小杰(1987-)，女，安徽阜陽(yáng)人，碩士，助教，主要研究領(lǐng)域：數(shù)據(jù)處理、嵌入式技術(shù)。

TP311.13

：A

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

10.3969/j.issn.1673-2006.2015.12.026