基于LZW優化算法的雷達數據壓縮技術

劉 林

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

0 引 言

雷達在工作過程中，需要將前端雷達探測到的各種信號數據傳輸到后端進行處理，并且由于雷達探測數據的敏感性，一般要求將其探測的全部數據傳輸到后端，這就對雷達數據傳輸的信道帶寬提出了較高要求，然而由于雷達實際工作過程中的各種限制，導致雷達數據傳輸信道容量有限，比如建設在某些高山、海島等地的遠程無人值守雷達，其數據傳輸到后端可能要經過多重無線、有線信道，由于這些信道帶寬都受到限制，不能保證雷達數據傳輸的完整性和實時性。針對這種情況，要保證雷達數據傳輸的完整性和實時性，除了提高信道帶寬以外，還可以采用數據壓縮技術，對雷達數據在傳輸之前進行無損壓縮，使之滿足傳輸信道的要求，同時也能保證其完整性和實時性。

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

1 LZW 算法及改進

1.1 算法概況

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

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

1.2 算法流程

依據上述對LZW 算法的描述，在實現LZW 算法編程時，按照圖1 進行。

1.3 算法應用

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

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

步驟2:讀當前字符，有C = a，則SC = a，因為字符串a 包含在串表中，則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:再一次讀取字符時發現字符讀取完畢，即沒有需要壓縮的數據，則輸出S的值a的索引0到編碼流，

步驟10:編碼結束，輸出結果:010240。

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

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

1.4 算法改進

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

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

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

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

表2 LZW 算法優化前后效率對比Tab.2 Efficiency comparison of LZW algorithm

2 雷達數據壓縮試驗

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

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

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

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

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

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

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

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

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

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

3 結 語

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

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

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

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

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

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

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

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

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