一種改進的LZ77算法及在車載北斗通信機上的應用?

馬 杰 樊輝錦 宋金禹 喬福超 牟俊杰

（1.海軍指揮學院 南京 210018）（2.海軍航空大學 煙臺 264001）（3.92769部隊 青島 266001）（4.92211部隊 海口 570300）

1 引言

我國自主研發的北斗衛星導航系統（BDS）除了能夠提供導航系統的基本服務，還有著特有的短報文通信功能，在通信條件較差或特殊保密要求條件下發揮了重大作用，已在抗震救災、海洋通信和電網建設中得到了廣泛應用［1～3］。根據加快推進軍隊信息化的指示要求，北斗系統在軍用車輛中的應用也日益增多，裝配北斗定位系統的特種車輛也逐漸增多。但是，由于通信量的限制，車輛狀態信息數據量超過最大北斗短報文長度，必須壓縮傳輸。

根據特種車輛關鍵狀態信息的需要必須采用無損壓縮算法，無損壓縮算法可分為兩類——基于字典或統計學。LZ77是基于字典類的典型算法，其主要原理是通過將信息中重復的數據用符號代替來壓縮數據量［4］。對于特種車輛狀態信息傳輸，LZ77的優越性主要體現在對于通用性信息具有較好的壓縮率、復雜度適中、適用于嵌入式系統設計。不少人在此算法的基礎上進行研究改進，LZ78、LZSS、LZW均是以LZ77為核心發展而來［4］。LZSS的一個關鍵改進是構建二叉搜索樹結構，也是目前應用較多的。但該方法以消耗存儲空間為代價提高速度［6］，不適合嵌入式系統應用。2018年，Choi S 提出［7］將 KMP（Knuth-Morris-Pratt Algo?rithm）算法應用到LZ77字符串查找中，但是該方法實現起來較為復雜，同樣不適用于嵌入式系統，對于特種車輛狀態信息傳輸來說不能真正提高信息的壓縮速度。

本文結合特種車輛狀態信息傳輸的實際需求，提出參考BM單模式匹配算法對LZ77算法進行改進，并通過實驗測試證明了這一算法（BM-LZ77）滿足特種車輛狀態信息傳輸要求，具有較高的效率，并通過與LZ77算法對比，證實該算法可以有效提高LZ77的壓縮速度，具有工程實踐意義。在軍用特種車輛北斗短報文通信機的設計項目中應用了該算法。

2 LZ77算法的改進

2.1 LZ77算法概述

LZ77算法廣泛應用于通信傳輸中的無損壓縮，由Abraham和Jacob于1977年提出，是基于字典的無損壓縮算法［8］。在數據壓縮時，將源數據與字典中提前設定好的數據項匹配，查找出相應的數字或字符代碼并輸出。LZ77算法匹配字符串時是利用二叉樹遍歷查找最優結果的，假設用O（n*q）來表示時間復雜度，其中n為滑動窗口編號，q為平均可匹配長度，但當n較大，算法處理速度會下降［9］。其軟件設計流程如圖1。影響LZ77算法壓縮性能的因素主要有四點：Hash函數的計算方法、采用字典的大小、最大匹配算法和匹配計算及輸出格式。

圖1 LZ77算法實現流程圖

2.2 改進方法

考慮到車輛關鍵信息的重要性以及北斗短報文單次信息傳遞的長度限制，必須對傳輸內容進行無損壓縮。本文選用的LZ77算法由于其自身優越性，能夠很好地適用于嵌入式北斗通信機，但其壓縮速度不能很好滿足實時性傳輸的要求。因此，本文提出參考BM單模式匹配算法來對LZ77算法進行改進，縮短壓縮時間，提高信息傳輸實時性，滿足實際應用需求。

BM算法作為精確字符串匹配算法，滿足無損傳輸需求，其運用的兩種規則——壞字符規則以及好后綴規則保證了其匹配速度［10］。設算法內置文本串T，代編碼字符串P，基本運算過程如下：

1）將T、P左對齊，從右向左依次比較。

2）壞字符規則，若發現Pk≠Ti，則按照式（1）將P右移x位：

3）好后綴規則，若發現Pk≠Ti，且有部分字符匹配成功時，則按式（2）將P右移y位：

最后距離為h=max(x，y)。

對LZ77算法改進的方法不直接計算源數據流的滑動距離，而是借鑒BM算法，增加預處理環節找到最長匹配值。基本思想是先搜索最大匹配字符串，如果某一個字符比較失敗以后，立即停止依次匹配，轉而跳轉到開關位置進行匹配從而提高編碼的搜索速度。假設文本窗口為T，待編碼數據流為P，最長可匹配字符長度為m，滑動窗口的長度為n，如圖2所示。

圖2 滑動窗口示意圖

1）在滑動窗口中P區查找搜索區中的最大匹配字符串，P對準匹配位置Ti。

2）匹配固定方向進行，如果在Pk≠Ti匹配未成功，并且Ti不在T中，那么右移P直到Pi位于匹配失敗位Ti+1，若Ti在P中有不止一處出現，則

3）若P后面K位和T中相同的文本有一些在T中其它地方出現，那么將P右移，使相同的文本對齊，且一致文本盡量大。

算法的查找匹配部分用C語言實現描述如圖3。

圖3 算法程序實現

3 改進LZ77算法的應用

將改進后的LZ77壓縮算法設計在北斗通信機的嵌入式系統中，主要實現數據壓縮傳輸功能。在特種車輛關鍵信息利用短報文傳遞的過程中，北斗通信機主要提供三種服務：與用戶終端進行實時信息交互；實時發送關鍵狀態信息到目標北斗通信機或接收信息；利用壓縮算法實現數據壓縮在短報文協議在的打包和解析。其中算法的數據壓縮能力決定了信息傳輸的性能。

3.1 硬件環境

硬件結構框圖如圖4所示，主要包括單片機最小系統、串口通信模塊、CAN通信模塊、SD卡存儲模塊、下載管理模塊、電源電路等。單片機最小系統由STM32F205微處理器、晶體振蕩電路和復位電路等組成［11］。串口通信模塊，其串口1用于與北斗短報文模塊進行數據交互，波特率為19200bit/s，數據位為8位，無校驗位；其串口2用于與車載信息采集終端通信，波特率為256000bit/s，數據位為8位，偶檢驗［12］。CAN通信模塊是針對部分有總線主要車輛進行的預留，提高北斗通信機的擴展和通用性［13］。

圖4 北斗通信機硬件結構圖

SD卡存儲模塊實現發送數據的存儲。車輛狀態信息的數據量相對于北斗短報文的通信能力（78Byte/min）而言是較大的，而且是動態變化的。通信機需將車輛狀態信息數據先存儲到SD卡中，再由單片機陸續從SD卡中讀取數據進行處理和傳輸，或者選擇閑時傳輸［14］。另外，出現丟包時，存儲在SD卡中的數據可以提供數據重傳，提高通信鏈路的可靠性。升級模塊提供北斗通信機的在線升級功能。

3.2 算法的實現

本文提出的BM-LZ77算法，在嵌入式系統中實現時的關鍵步驟是沿鏈表回溯搜索匹配字符串，并逐個對比，匹配成功時擇優輸出匹配長度（LENGTH_P），失敗時輸出未匹配字符（LIT）［15］。匹配計算的過程中，待處理字符地址（Next_Addr）和最近的當前匹配起始地址（Now_Addr）均從Match_FIFO隊列中獲取，根據Now_Addr與Next_Addr的關系分為三種情況分析。

1）Now_Addr＝ Next_Addr：表示待處理字符位置的與匹配字符串位置相同，直接根據指向地址取值匹配比較即可；

2）Now_Addr

3）Now_Addr>Next_Addr：表示待處理字符位置尚未到達當前匹配起始字符串的位置，該情況出現概率較高，此時區間［Next_Addr，Now_Addr］內的字符均為未匹配字符（LIT）。改進后的LZ77在匹配計算的同時輸出LIT，提高算法處理的實時性，又適合嵌入式系統應用，流程圖如圖5所示。

圖5 改進算法在STM32中的溯搜索匹流程圖

由于流程中的匹配計算和輸出未匹配字符均需訪問數據緩沖區以獲取尚未被壓縮的數據，會產生并發，因此設計相應的算法時序來控制并發，如圖6，賦予匹配計算模塊更高的讀請求優先級，在其處理間隙發送讀信號，獲取未匹配字符，待匹配完成，若仍需要處理LIT則發送LIT_RD_DICT，從而提升整個算法處理過程的實時性［16］。

圖6 改進算法的時序實圖

4 實驗測試

4.1 評價標準和實驗環境

對于壓縮效果和實時性的評價本文借鑒的評價標準如下［17］。

1）壓縮比：壓縮后數據容量Nc和原始數據容量N的比值

eCR=Nc/N×100%

2）能量恢復系數：評價壓縮算法恢復能力

3）均方差：誤差評價標準

測試數據集采用實際特種車輛狀態信息數據集，使用兩臺BNTRE-320B北斗車載一體機進行試驗，為確保試驗可靠有效，采用的北斗設備滿足指標要求：BD2/BD3上行為L頻段下行為S頻段，BD3全球短報文下行為L頻段，一次報文長度BD2為120漢字，BD3在RDSS服務區域不大于1000個漢字，在僅具有全球短報文服務區域不大于40個漢字，誤碼率不大于10-5等其他需求［18］。在實驗中，兩臺北斗一體機的SIM卡報文權限相同，通信服務頻率為60s/次。

4.2 實驗結果與分析

為驗證BM-LZ77算法的優越性，在其他實驗條件相同的情況下，本文分別對運用LZ77算法以及改進LZ77算法下的北斗短報文傳輸情況進行了三組測試，并記錄評價傳輸效果優劣的延遲以及壓縮效果的相關數據，以達到對比目的。結果如表1。

表1 測試結果對比

為更加直觀地對比應用兩種算法下的特種車輛狀態信息傳輸情況，判斷本文提出的結合BM單模式匹配算法的LM77算法是否能夠縮短報文傳輸時間，達到實時性傳輸的目的，分別計算兩種算法下各項實驗數據的算數平均值。

圖7 算法實時性比較圖

對比兩種算法的壓縮比、能量恢復系數以及平均延遲時間，可以發現改進后的LZ77算法三項數據均低于原算法，且運用改進后LZ77算法的報文傳輸延遲時間均明顯低于原LZ77算法最短延遲時間，另外壓縮比、能量恢復系數沒有明顯的大小差別，證明兩者在壓縮效果方面相同。

5 結語

本文提出的BM-LZ77算法，提高了數據壓縮的速度，并在嵌入式車載北斗通信機的設計中進行了工程實踐。實踐結果表明，算法的復雜度降低，實時性提高，壓縮比也有一定提高但不明顯，應用范圍較廣，可移植性好。