基于LZW優(yōu)化算法的雷達(dá)數(shù)據(jù)壓縮技術(shù)

劉 林

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

0 引 言

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

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

1 LZW 算法及改進(jìn)

1.1 算法概況

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

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

1.2 算法流程

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

1.3 算法應(yīng)用

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

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

步驟2:讀當(dāng)前字符，有C = a，則SC = a，因?yàn)樽址產(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 中記錄了上述各步驟變量的屬性圖。表中加粗行的項(xiàng)為在串表中找到了相關(guān)表項(xiàng)后的操作。

表1 LZW 編碼實(shí)例屬性圖Tab.1 LZW encoding instance attributes

1.4 算法改進(jìn)

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

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

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

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

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

2 雷達(dá)數(shù)據(jù)壓縮試驗(yàn)

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

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

表4 游程編碼3 種類型雷達(dá)數(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ù)的壓縮比可達(dá)到幾十倍左右，并且LZW 算法在具有較大長度編碼單元時具有明顯優(yōu)勢。

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

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

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

3 結(jié) 語

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

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

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

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

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

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

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

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

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