一種支持嵌入式標(biāo)校系統(tǒng)的數(shù)據(jù)壓縮算法*

劉愛東 李知宇 王 豐 賀林波

（1.海軍航空工程學(xué)院201教研室 煙臺(tái) 264001）（2.海軍航空工程學(xué)院研究生管理大隊(duì) 煙臺(tái) 264001）（3.海軍航空工程學(xué)院訓(xùn)練部數(shù)字化校園辦公室 煙臺(tái) 264001）

1 引言

在著艦引導(dǎo)系統(tǒng)的標(biāo)校方式中，無人機(jī)標(biāo)校作為一種安全有效的方式得到廣泛應(yīng)用。基于無人機(jī)的嵌入式標(biāo)校系統(tǒng)具有功耗低、合作目標(biāo)一體化的優(yōu)點(diǎn)具有廣泛的應(yīng)用前景［1～3］。

嵌入式標(biāo)校系統(tǒng)在完成校飛功能時(shí)需采集大量的數(shù)據(jù)，包括GPS原始測(cè)量數(shù)據(jù)、NMEA0183格式數(shù)據(jù)［4～5］，姿態(tài)傳感器數(shù)據(jù)等。標(biāo)校系統(tǒng)實(shí)時(shí)性高，需在系統(tǒng)分配的時(shí)間片內(nèi)完成數(shù)據(jù)的采集壓縮存儲(chǔ)功能。因此，壓縮算法需要時(shí)間復(fù)雜度低與空間開銷低。因此需要針對(duì)標(biāo)校系統(tǒng)采集的數(shù)據(jù)進(jìn)行分析，采用一種適合嵌入式標(biāo)校系統(tǒng)的算法來壓縮數(shù)據(jù)。

2 LZ77算法基本原理與游程編碼思想

LZ77與游程編碼作為無損壓縮算法中的經(jīng)典壓縮算法在各種壓縮軟件中一直得到廣泛應(yīng)用。

2.1 LZ77算法

LZ77 算法［6～8］是無損壓縮算法，由以色列人Abraham Lempel于1977年提出，核心思想是利用數(shù)據(jù)的重復(fù)結(jié)構(gòu)壓縮數(shù)據(jù)，是典型基于字典的壓縮算法。數(shù)據(jù)壓縮時(shí)，將從待壓縮數(shù)據(jù)中讀入的源數(shù)據(jù)與字典中的數(shù)據(jù)項(xiàng)進(jìn)行匹配，從中找出待壓縮數(shù)據(jù)與字典中的數(shù)據(jù)最長(zhǎng)匹配長(zhǎng)度。

算法用到的結(jié)構(gòu)數(shù)據(jù)主要有：待編碼區(qū)（等待編碼的區(qū)域），搜索緩沖區(qū)（已經(jīng)編碼區(qū)域），滑動(dòng)窗口（搜索緩沖區(qū)+待編碼區(qū)，定義border為二者的邊界）。

輸出結(jié)果為（p，l，c）

p為待編碼區(qū)匹配字典數(shù)據(jù)最大匹配長(zhǎng)度的字符串在字典中開始出現(xiàn)的位置；

l為最長(zhǎng)匹配；

c為待編碼區(qū)被匹配位置下一個(gè)字符串。

LZ77算法的執(zhí)行流程主要有：

Step 1：從搜索緩沖區(qū)字典中尋找與待編碼數(shù)據(jù)的最長(zhǎng)匹配字符串，如果找到執(zhí)行step 2，否則執(zhí)行step 3。

Step 2：輸出結(jié)構(gòu)為（off，len，c）數(shù)據(jù)，off為字典中匹配字符串位置相對(duì)于border的偏移量，len為最長(zhǎng)匹配字符串的長(zhǎng)度。然后將窗口向后滑動(dòng)len+1個(gè)字符，繼續(xù)步驟1。

Step 3：輸出結(jié)構(gòu)為（0，0，c）數(shù)據(jù)，c為待編碼區(qū)被匹配位置下一個(gè)字符串，窗口后移1個(gè)單位長(zhǎng)度。繼續(xù)步驟1。

2.2 游程編碼

游程編碼是無損壓縮編碼，其基本原理是用符號(hào)值或者串長(zhǎng)代替連續(xù)相同值的數(shù)據(jù)，即對(duì)連續(xù)相同 數(shù) 據(jù) 進(jìn) 行 編 碼 的 過 程［9～11］。 例 如 ，數(shù) 據(jù)aaaaabbbbbbb可編碼為a5b7，當(dāng)壓縮數(shù)據(jù)中出現(xiàn)大量連續(xù)相同數(shù)據(jù)情況，采用游程編碼，有很好的壓縮效果。

2.3 經(jīng)典壓縮算法在嵌入式標(biāo)校系統(tǒng)應(yīng)用情況分析

采用基于無人機(jī)的嵌入式標(biāo)校系統(tǒng)對(duì)著艦引導(dǎo)系統(tǒng)進(jìn)行標(biāo)校時(shí)，系統(tǒng)的真值測(cè)量模塊即GPS模塊每秒接收GPS原始測(cè)量數(shù)據(jù)、NMEA0183格式數(shù)據(jù)，同時(shí)系統(tǒng)還需基于著艦引導(dǎo)系統(tǒng)標(biāo)校規(guī)定的頻率在ARM處理器分配的的時(shí)間片內(nèi)完成姿態(tài)傳感器的數(shù)據(jù)采集壓縮存儲(chǔ)功能。嵌入式的標(biāo)校系統(tǒng)實(shí)時(shí)性高、存儲(chǔ)空間有限、處理器任務(wù)繁重，需要壓縮算法必須時(shí)間復(fù)雜度低［12～13］，且壓縮過程中空間開銷小。LZ77算法在壓縮過程中需不斷匹配待編碼數(shù)據(jù)與搜索緩沖區(qū)的最長(zhǎng)匹配字符串，算法復(fù)雜度較高。游程編碼適合待壓縮的數(shù)據(jù)中有大量連續(xù)重復(fù)數(shù)據(jù)的情況，否則效果不佳。

3 算法設(shè)計(jì)

3.1 數(shù)據(jù)分析

本文預(yù)先采集大量GPS原始測(cè)量數(shù)據(jù)、NMEA0183格式數(shù)據(jù)和實(shí)驗(yàn)中使用姿態(tài)傳感器的數(shù)據(jù)進(jìn)行分析，得出：標(biāo)校系統(tǒng)中數(shù)據(jù)具有連續(xù)大量重復(fù)數(shù)據(jù)的情況只在局部數(shù)據(jù)出現(xiàn)，這段數(shù)據(jù)使用游程編碼算法來壓縮的效率最高，某些特定的數(shù)據(jù)結(jié)構(gòu)重復(fù)讀較高適合使用LZ77算法來壓縮數(shù)據(jù)，但需改進(jìn)算法以降低算法復(fù)雜度［14～15］，這些特定的數(shù)據(jù)結(jié)構(gòu)以連續(xù)三個(gè)字節(jié)或者四個(gè)字節(jié)的形式出現(xiàn)在GPS原始測(cè)量數(shù)據(jù)中，NMEA0183格式數(shù)據(jù)和姿態(tài)傳感器幀頭起始位等具有特定語義的數(shù)據(jù)占有較長(zhǎng)數(shù)據(jù)位，適合將較長(zhǎng)數(shù)據(jù)幀頭存儲(chǔ)在字典中重新編碼達(dá)到壓縮數(shù)據(jù)目的。因此，需要針對(duì)標(biāo)校系統(tǒng)數(shù)據(jù)的特殊情況，設(shè)計(jì)一種新的壓縮算法。

3.2 算法描述

標(biāo)校系統(tǒng)的數(shù)據(jù)存儲(chǔ)是基于ASCII編碼形式，8bit為單位統(tǒng)一存儲(chǔ)，筆者預(yù)先對(duì)大量數(shù)據(jù)進(jìn)行統(tǒng)計(jì)后，設(shè)計(jì)一種壓縮算法，采用LZ77壓縮算法和游程編碼的思想對(duì)冗余度較高以及存在關(guān)聯(lián)性的數(shù)據(jù)進(jìn)行統(tǒng)一編碼，同時(shí)克服兩種算法的局限性，達(dá)到在算法復(fù)雜度低的情況下較好地完成數(shù)據(jù)壓縮的目的。

原理主要有：

1）LZ77算法時(shí)間復(fù)雜度為O（n2），壓縮過程中將大量時(shí)間資源用于尋找最長(zhǎng)匹配字符串，本文對(duì)LZ77算法進(jìn)行改進(jìn)，預(yù)先采集大量數(shù)據(jù)統(tǒng)計(jì)中得知，連續(xù)三個(gè)字節(jié)或者四個(gè)字節(jié)的數(shù)據(jù)結(jié)構(gòu)前后重復(fù)度較高，因此，預(yù)先將重復(fù)率較高的四個(gè)或者三個(gè)字節(jié)數(shù)據(jù)結(jié)構(gòu)組成字典，將重復(fù)率高的數(shù)據(jù)結(jié)構(gòu)和具有特定語義字符串采用16bit統(tǒng)一編碼，構(gòu)成基于字典的壓縮數(shù)據(jù)，并且NMEA0183格式幀頭等具有特定語義數(shù)據(jù)壓縮數(shù)據(jù)查找表時(shí)優(yōu)先查找。字典序列一共95條，結(jié)構(gòu)圖1所示。

連續(xù)三個(gè)或者四個(gè)字節(jié)重復(fù)數(shù)據(jù)結(jié)構(gòu)以及較長(zhǎng)字符串且具有特定語義數(shù)據(jù)壓縮為16bit編碼數(shù)據(jù)結(jié)構(gòu)如圖2所示。

在壓縮過程中，將窗口大小初始值設(shè)置為4，不斷將窗口中的數(shù)據(jù)與字典中數(shù)據(jù)比較，如果與字典中的數(shù)據(jù)匹配成功，則將數(shù)據(jù)編碼為字典中的16bit，并按16位整數(shù)類型數(shù)據(jù)存儲(chǔ)。如果窗口中的數(shù)據(jù)$開頭，則是NMEA0183數(shù)據(jù)長(zhǎng)度為6字節(jié)的幀頭標(biāo)志，則將數(shù)據(jù)編為字典中的16bit，并按16位整數(shù)類型數(shù)據(jù)存儲(chǔ)。

圖1 字典結(jié)構(gòu)圖

圖2 壓縮后16bit數(shù)據(jù)編碼結(jié)構(gòu)

2）通過對(duì)大量數(shù)據(jù)統(tǒng)計(jì)得知，GPS原始測(cè)量數(shù)據(jù)中，‘0’字符在有局部大量連續(xù)情況存在，對(duì)局部連續(xù)大量‘0’基于游程編碼的思想，采用16bit統(tǒng)一表示。壓縮后16bit編碼數(shù)據(jù)結(jié)構(gòu)如圖3所示。

圖3 基于游程編碼思想壓縮數(shù)據(jù)編碼圖

在基于游程編碼思想編碼壓縮數(shù)據(jù)時(shí)，當(dāng)數(shù)據(jù)‘0’連續(xù)重復(fù)超過5次時(shí)，將連續(xù)重復(fù)的數(shù)據(jù)‘0’按圖3的情況進(jìn)行編碼后壓縮為16bit的整數(shù)類型數(shù)據(jù)。例如000000，編碼為1000000000000110，將連續(xù)5個(gè)字節(jié)‘0’數(shù)據(jù)編碼為這16個(gè)二進(jìn)制位，并轉(zhuǎn)換為整數(shù)類型數(shù)據(jù)32774，壓縮后只占兩個(gè)字節(jié)。

在壓縮過程中，如果數(shù)據(jù)不需要按上述情況處理，則轉(zhuǎn)換為8位整數(shù)類型存儲(chǔ)。解碼過程中，如果整形數(shù)據(jù)大于32768，則按基于游程編碼壓縮的數(shù)據(jù)結(jié)構(gòu)進(jìn)行解碼，當(dāng)整型數(shù)據(jù)大于256且小于32768時(shí)按照基于字典壓縮的數(shù)據(jù)結(jié)構(gòu)進(jìn)行解碼。

4 算法應(yīng)用測(cè)試

為檢驗(yàn)筆者設(shè)計(jì)算法性能，筆者使用基于U-Blox公司型號(hào)為NEO-M8T的GPS芯片搭建的開發(fā)板采集GPS原始測(cè)量數(shù)據(jù)和NMEA0183格式數(shù)據(jù)，姿態(tài)傳感器采用超核電子公司型號(hào)為HIM219基于陀螺儀的姿態(tài)傳感器，GPS原始測(cè)量數(shù)據(jù)與NMEA0183數(shù)據(jù)每秒接收一次，姿態(tài)傳感器工作的頻率為5Hz，嵌入式標(biāo)校系統(tǒng)將每秒采集的上述數(shù)據(jù)進(jìn)行壓縮，多次實(shí)驗(yàn)結(jié)果如表1所示。

表1 算法應(yīng)用測(cè)試結(jié)果

算法基于數(shù)據(jù)量有限的字典對(duì)重復(fù)率高的數(shù)據(jù)結(jié)構(gòu)進(jìn)行編碼，并局部使用游程編碼壓縮數(shù)據(jù)，時(shí)間復(fù)雜度為O（n），空間開銷較小，經(jīng)實(shí)驗(yàn)得出，本文設(shè)計(jì)的算法壓縮率基本穩(wěn)定，能在算法復(fù)雜度較低和空間開銷較低的情況下完成嵌入式標(biāo)校系統(tǒng)的數(shù)據(jù)壓縮功能。

5 結(jié)語

本文針對(duì)前期搭建的基于無人機(jī)的嵌入式標(biāo)校系統(tǒng)產(chǎn)生的數(shù)據(jù)量較大且ARM處理器工作時(shí)任務(wù)繁重不易處理數(shù)據(jù)的問題，預(yù)先采集大量的數(shù)據(jù)，對(duì)數(shù)據(jù)分片分析研究其中的數(shù)據(jù)結(jié)構(gòu)，綜合了LZ77算法與游程編碼的壓縮思想，設(shè)計(jì)了一種適合嵌入式標(biāo)校系統(tǒng)的數(shù)據(jù)壓縮算法，將需要壓縮的數(shù)據(jù)統(tǒng)一采用16bit數(shù)據(jù)結(jié)構(gòu)進(jìn)行編碼，算法基于字典壓縮數(shù)據(jù)，但改進(jìn)后降低了時(shí)間復(fù)雜度，同時(shí)將局部大量連續(xù)數(shù)據(jù)基于游程編碼算法進(jìn)行編碼，算法性能穩(wěn)定，有很好的實(shí)用價(jià)值。