劉 林

(中國人民解放軍91202 部隊，遼寧 葫蘆島125004)

0 引 言

雷達在工作過程中，需要將前端雷達探測到的各種信號數(shù)據(jù)傳輸?shù)胶蠖诉M行處理，并且由于雷達探測數(shù)據(jù)的敏感性，一般要求將其探測的全部數(shù)據(jù)傳輸?shù)胶蠖?，這就對雷達數(shù)據(jù)傳輸?shù)男诺缼捥岢隽溯^高要求，然而由于雷達實際工作過程中的各種限制，導(dǎo)致雷達數(shù)據(jù)傳輸信道容量有限，比如建設(shè)在某些高山、海島等地的遠程無人值守雷達，其數(shù)據(jù)傳輸?shù)胶蠖丝赡芤?jīng)過多重?zé)o線、有線信道，由于這些信道帶寬都受到限制，不能保證雷達數(shù)據(jù)傳輸?shù)耐暾院蛯崟r性。針對這種情況，要保證雷達數(shù)據(jù)傳輸?shù)耐暾院蛯崟r性，除了提高信道帶寬以外，還可以采用數(shù)據(jù)壓縮技術(shù)，對雷達數(shù)據(jù)在傳輸之前進行無損壓縮，使之滿足傳輸信道的要求，同時也能保證其完整性和實時性。

目前應(yīng)用較為廣泛的數(shù)據(jù)無損壓縮技術(shù)有LZW編碼、霍夫曼編碼、算術(shù)編碼和游程編碼。其中LZW 編碼是一種字典壓縮算法，其在編、解碼過程中動態(tài)形成字典，適用于各種不同類型的數(shù)據(jù)壓縮領(lǐng)域［1］，因此其得到了廣泛應(yīng)用。在對該算法的實際編程過程中發(fā)現(xiàn)，該算法運行過程中的大量時間花費在對字典的檢索過程。而對于雷達數(shù)據(jù)傳輸來說，數(shù)據(jù)傳輸要具備盡可能高的實時性，基于這點考慮，文中提出一種利用哈希表來優(yōu)化LZW 編碼的數(shù)據(jù)結(jié)構(gòu)，從而有效減少LZW 算法字典檢索時間的新方法，提升壓縮效率，以盡可能提高雷達數(shù)據(jù)傳輸?shù)膶崟r性。最后，通過雷達數(shù)據(jù)壓縮試驗來驗證該優(yōu)化算法的有效性。

1 LZW 算法及改進

1.1 算法概況

1984年，TA Welch 對LZ 編碼中的LZ78 算法改進而成為LZW 壓縮算法。與費諾編碼和霍夫曼編碼相比，LZW 算法在使用過程中不需要對信源進行概率統(tǒng)計，與游程編碼相比，其能夠?qū)崿F(xiàn)對不同但重復(fù)出現(xiàn)字符串的編碼，并且LZW 算法還具有編碼速度快和數(shù)據(jù)壓縮效果更好的優(yōu)點，因此其在實際中應(yīng)用非常廣泛。

LZW 算法通過使用一個串表將輸入字符串映射成一個固定長度的碼字輸出來實現(xiàn)數(shù)據(jù)的壓縮。在編程時，碼字長度一般為12 位，也可以設(shè)置為15 位或者18 位。在壓縮過程中，串表具有“前綴性”，即假若一個字符串由兩部分構(gòu)成，前部分為字符串S，后部分為字符C，若該字符串SC 存在串表中，那么C 就為S的擴展，S為C的前綴。在編碼前首先通過初始化使串表包含所有的單字符串，然后進行壓縮，壓縮過程中串表不斷產(chǎn)生壓縮信息的新字符串，同時必須保存新字符串SC的前綴S 相對應(yīng)的碼字。當(dāng)進行數(shù)據(jù)解壓縮時，解碼器可以根據(jù)編碼字恢復(fù)出同樣的字符串表，從而實現(xiàn)編碼數(shù)據(jù)流的解碼過程［2－5］。

1.2 算法流程

依據(jù)上述對LZW 算法的描述，在實現(xiàn)LZW 算法編程時，按照圖1 進行。

1.3 算法應(yīng)用

下邊通過分析一個簡單的數(shù)據(jù)壓縮實例來說明LZW 算法的具體實施過程。現(xiàn)有一個字母表a，b，c，d和一個輸入字符流:“abacaba”，下面給出該字符流壓縮的實施步驟。

步驟1:對串表進行初始化，有0 = a，1 = b，2 = c，3 = d，前綴S = 空。

步驟2:讀當(dāng)前字符，有C = a，則SC = a，因為字符串a(chǎn) 包含在串表中，則S = a。

圖1 LZW 算法流程圖Fig.1 LZW algorithm float chart

步驟3:讀取第2個字符，有C = b，則SC =ab，該字符串不包含在串表中，則添加SC 到串表中，有4 = ab，且同時輸出S(也就是a)的索引0 到編碼流，然后修改S = b;

步驟4:讀下一個字符，有C = a，則SC = ba，該字符串不包含在串表中，則添加到串表中，有5 = ba，輸出S的索引1 到編碼流，修改S = a;

步驟5:讀下一個字符，有C = c，則SC = ac，該字符串不包含在串表中，則添加到串表中，有6 = ac，輸出S的索引0 到編碼流，修改S = c;

步驟6:讀下一個字符，有C = a，則SC = ca，該字符串不包含在串表中，則添加到串表中，有7 = ca，輸出S的索引2 到編碼流，修改S = a;

步驟7:讀下一個字符，有C = b，則SC = ab，該字符串包含在串表中，且4 = ab，則修改S = ab;

步驟8:讀下一個字符，有C = a，則SC = aba，該字符串不包含在串表中，則添加到串表中，有8 = aba，輸出S的索引4 到編碼流，修改S = a;

步驟9:再一次讀取字符時發(fā)現(xiàn)字符讀取完畢，即沒有需要壓縮的數(shù)據(jù)，則輸出S的值a的索引0到編碼流，

步驟10:編碼結(jié)束，輸出結(jié)果:010240。

表1 中記錄了上述各步驟變量的屬性圖。表中加粗行的項為在串表中找到了相關(guān)表項后的操作。

表1 LZW 編碼實例屬性圖Tab.1 LZW encoding instance attributes

1.4 算法改進

如果設(shè)置碼長為12 位，那么串表個數(shù)為:212=4 096。而在對每一個字節(jié)進行編碼時，都需要對整個串表進行搜索和字符對比，因此LZW 算法的大部分時間用于對串表進行搜索，造成了LZW 算法實時性不強，難以應(yīng)用于高實時性數(shù)據(jù)壓縮場合。而雷達數(shù)據(jù)壓縮就是一個高實時性要求的應(yīng)用場合，為了能夠?qū)ZW 算法用于雷達數(shù)據(jù)壓縮領(lǐng)域，就必須對該算法進行改進，提高其實時性，以滿足雷達數(shù)據(jù)壓縮的要求。LZW 算法的大部分時間用于串表的遍歷，因此可以考慮提高其遍歷效率來提高實時性。在軟件設(shè)計過程中，采用樹型數(shù)據(jù)結(jié)構(gòu)相對串表可以大幅提高遍歷效率，但是樹型結(jié)構(gòu)同樣需要遍歷，并且算法復(fù)雜度和穩(wěn)定性不夠好。提高遍歷效率最好的方式就是不進行遍歷，能夠直接通過位置關(guān)鍵字進行查找，這是最為理想的方式，從這個角度出發(fā)，可以采取將記錄存儲的位置和關(guān)鍵字進行對應(yīng)，從而通過查找關(guān)鍵字來直接尋址到存儲的數(shù)據(jù)。

在軟件編程領(lǐng)域，哈希表就可以實現(xiàn)上述想法。哈希表其實就是一個特殊二維數(shù)組，這里記編碼字符值范圍為0～255，則12 位碼長編碼的哈希表可以記為M［4096］［256］，且矩陣M［i］［j］中行號i表示前綴在串表中的索引號，列號j 表示當(dāng)前字符，則M［i］［j］的值為前綴和當(dāng)前字符組合在串表中的索引，如果串表中不包含該項，則M［i］［j］=－1。該設(shè)計方法具有如下優(yōu)點:

1)通過使用串表中的索引來實現(xiàn)前綴而不再需要另外建立一個數(shù)組。

下面使用3 種不同類型的文件數(shù)據(jù)來進行LZW算法壓縮試驗，文件數(shù)據(jù)類型分別為64 kB圖像文件、30 MB 雷達數(shù)據(jù)文件和800 kB 文本文件，3 種文件均采用原始LZW 算法和改進LZW 算法分別進行10 次試驗，然后求消耗時間平均值。將其數(shù)據(jù)記錄于表2。從表中記錄數(shù)據(jù)可以看出，LZW 算法在經(jīng)過使用哈希表優(yōu)化后，其編碼效率提升80%以上，效果很明顯。因此該算法具有很高的實用性，能夠大幅提高壓縮效率，節(jié)約大量時間，滿足某些高實時性要求場合的數(shù)據(jù)壓縮需求。

表2 LZW 算法優(yōu)化前后效率對比Tab.2 Efficiency comparison of LZW algorithm

2 雷達數(shù)據(jù)壓縮試驗

下面采用實際雷達數(shù)據(jù)對該算法進行測試。這里選取3 種不同的雷達數(shù)據(jù):1 類為雜波較多的256灰度級雷達數(shù)據(jù);2 類為雜波較少的256 灰度級雷達數(shù)據(jù);3 類為二值雷達數(shù)據(jù)。為了更好地檢驗算法提升效率，實測時選取不同長度的編碼單位進行編碼，并且將其結(jié)果和游程編碼進行對比。LZW 算法測試數(shù)據(jù)記錄于表3，游程編碼測試數(shù)據(jù)記錄于表4。為了更加直觀的觀察算法的提升效率，將兩表中數(shù)據(jù)采用壓縮比計算公式:

壓縮比=壓縮前數(shù)據(jù)大小/壓縮后數(shù)據(jù)大小換算成壓縮比數(shù)值，然后將該數(shù)值繪制于同一張坐標(biāo)圖中，如圖2所示。

表4 游程編碼3 種類型雷達數(shù)據(jù)壓縮效果Tab.4 Radar data compression effect of RLC algorithm for three types data

圖2 三種數(shù)據(jù)類型不同壓縮單元LZW和游程壓縮比變化曲線Fig.2 Compression ratio of LZW and RLC for three kinds of different data

分析表3和表4 中的數(shù)據(jù)以及圖2 中2 種編碼方式對照圖，可以得出如下結(jié)論:

1)LZW 算法的壓縮比對編碼單元長度大小十分敏感，其壓縮比大小隨編碼單元長度增加而增加，符合前邊的理論推導(dǎo)，理論上，當(dāng)編碼單元長度無窮大時，LZW 算法可趨于最優(yōu)的編碼效率。而游程編碼對編碼單元長度不敏感，其壓縮比穩(wěn)定在一個范圍內(nèi)。

2)當(dāng)數(shù)據(jù)類型不同時，其壓縮比隨之變動較大，由表中數(shù)據(jù)可得出，1 類型數(shù)據(jù)的壓縮比為2左右，而2 類型數(shù)據(jù)和3 類型數(shù)據(jù)的壓縮比可達到幾十倍左右，并且LZW 算法在具有較大長度編碼單元時具有明顯優(yōu)勢。

綜述以上結(jié)論，LZW 算法在使用過程中有以下注重點:

1)LZW 算法在編碼單元較小時不具有優(yōu)勢，而當(dāng)具有較大的編碼單元時，LZW 算法的壓縮效率提升非常迅速。

2)在LZW 算法中，串表的個數(shù)將直接影響算法的編碼效率，因此，為了獲得更好的編碼效果，可以通過改變串表個數(shù)來協(xié)調(diào)編碼效率和系統(tǒng)內(nèi)存及時間的消耗。如何通過選擇串表個數(shù)來達到編碼效率和系統(tǒng)消耗之間的平衡，這將需要更進一步的研究和總結(jié)。

3 結(jié) 語

LZW 算法是一種性能優(yōu)異的數(shù)據(jù)無損壓縮算法，廣泛應(yīng)用于各種數(shù)據(jù)壓縮領(lǐng)域。本文將該算法用于壓縮雷達信號數(shù)據(jù)，針對雷達數(shù)據(jù)量龐大以及該算法實時性難以滿足要求的問題，通過分析發(fā)現(xiàn)該算法的大部分時間用于串表搜索過程，據(jù)此，提出利用哈希表數(shù)據(jù)結(jié)構(gòu)來簡化其搜索過程，提高算法編碼速度，從而滿足雷達數(shù)據(jù)壓縮的實時性需求。最后通過雷達數(shù)據(jù)壓縮對比試驗，驗證對該算法改進的有效性和提出實際運用該改進算法的幾點參考意見。

［1］柳楠，趙秀梅，張志軍.基于LZW 壓縮的圖像信息隱藏方法［J］.計算機應(yīng)用與軟件，2007，24(8):193－195.

［2］郭曉巖，郝永勝.LZW 無損壓縮算法在計算機取證中的應(yīng)用研究［J］.測控技術(shù)，2006，25(11):64－67.

［3］張鳳林，劉思峰.一個改進的LZW 數(shù)據(jù)壓縮算法［J］.小型微型計算機系統(tǒng)，2006，27(10):1897－1999.

［4］藍波，林小竹，籍俊偉.一種改進的LZW 算法在圖像編碼中的應(yīng)用［J］.計算機工程與科學(xué)，2006，28(6):55－57.

［5］林小竹，籍俊偉.一種改進的LZW 壓縮算法［J］.計算機工程，2005，31(14):199－201.

［6］王泉，齊春，羅新民，梁嵩.LZW 壓縮算法的改進及其參數(shù)優(yōu)化分析［J］.重慶郵電學(xué)院學(xué)報(自然科學(xué)版)，2005，17(3):351－371.

［7］崔業(yè)勤，劉玉貴.基于LZW的多模式自適應(yīng)的無損壓縮算法［J］.微電子學(xué)與計算機，2005，22(3):99－105.

［8］王平.LZW 無損壓縮算法的實現(xiàn)與研究［J］.計算機工程，2002，28(7):98－150.