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

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

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

1 引言

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

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

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

2 LZ77算法的改進

2.1 LZ77算法概述

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

圖1 LZ77算法實現(xiàn)流程圖

2.2 改進方法

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

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

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

2）壞字符規(guī)則，若發(fā)現(xiàn)Pk≠Ti，則按照式（1）將P右移x位：

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

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

對LZ77算法改進的方法不直接計算源數(shù)據(jù)流的滑動距離，而是借鑒BM算法，增加預處理環(huán)節(jié)找到最長匹配值?；舅枷胧窍人阉髯畲笃ヅ渥址绻骋粋€字符比較失敗以后，立即停止依次匹配，轉(zhuǎn)而跳轉(zhuǎn)到開關位置進行匹配從而提高編碼的搜索速度。假設文本窗口為T，待編碼數(shù)據(jù)流為P，最長可匹配字符長度為m，滑動窗口的長度為n，如圖2所示。

圖2 滑動窗口示意圖

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

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

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

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

圖3 算法程序?qū)崿F(xiàn)

3 改進LZ77算法的應用

將改進后的LZ77壓縮算法設計在北斗通信機的嵌入式系統(tǒng)中，主要實現(xiàn)數(shù)據(jù)壓縮傳輸功能。在特種車輛關鍵信息利用短報文傳遞的過程中，北斗通信機主要提供三種服務：與用戶終端進行實時信息交互；實時發(fā)送關鍵狀態(tài)信息到目標北斗通信機或接收信息；利用壓縮算法實現(xiàn)數(shù)據(jù)壓縮在短報文協(xié)議在的打包和解析。其中算法的數(shù)據(jù)壓縮能力決定了信息傳輸?shù)男阅堋?/p>

3.1 硬件環(huán)境

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

圖4 北斗通信機硬件結(jié)構(gòu)圖

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

3.2 算法的實現(xiàn)

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

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

2）Now_Addr

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

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

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

圖6 改進算法的時序?qū)崍D

4 實驗測試

4.1 評價標準和實驗環(huán)境

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

1）壓縮比：壓縮后數(shù)據(jù)容量Nc和原始數(shù)據(jù)容量N的比值

eCR=Nc/N×100%

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

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

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

4.2 實驗結(jié)果與分析

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

表1 測試結(jié)果對比

為更加直觀地對比應用兩種算法下的特種車輛狀態(tài)信息傳輸情況，判斷本文提出的結(jié)合BM單模式匹配算法的LM77算法是否能夠縮短報文傳輸時間，達到實時性傳輸?shù)哪康模謩e計算兩種算法下各項實驗數(shù)據(jù)的算數(shù)平均值。

圖7 算法實時性比較圖

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

5 結(jié)語

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