GPS定位數(shù)據(jù)壓縮算法的設(shè)計與實現(xiàn)

1、GPS定位數(shù)據(jù)壓縮算法的設(shè)計與實現(xiàn)摘要為了解決嵌入式車載系統(tǒng)存儲空間小、定位數(shù)據(jù)量大的矛盾，根 據(jù)定位數(shù)據(jù)的特點，提出了專用于定全數(shù)據(jù)壓縮的改進(jìn)型半字節(jié)壓縮算法。該算法是一種在原半字節(jié)壓縮算法的基礎(chǔ)上改進(jìn)的算法，經(jīng)過實際測 試，壓縮比可達(dá)50。若將壓縮預(yù)處理也折算法在內(nèi)，總壓縮比可達(dá)80以上，為車載系統(tǒng)節(jié)省了大量的存儲資源。除此之外，也縮短了信道的占用時間，大大地緩解了向控制調(diào)度中心 上傳數(shù)據(jù)的壓力。關(guān)鍵詞數(shù)據(jù)壓縮數(shù)據(jù)格式壓縮預(yù)處理半字節(jié)壓縮算法嵌入式車載系 統(tǒng)般體積較小，無存儲量大的硬盤等設(shè)備，系統(tǒng)程序、應(yīng)用程序一般裝在 或中。由于或等存儲介質(zhì)的價格相對臺式機(jī)上廣泛使用的硬盤、光盤等來說 是

2、非常昂貴的，因此，在幵發(fā)嵌入式系統(tǒng)的軟件產(chǎn)品時必須將軟件所占的 存儲空間限制在一定的范圍內(nèi)。在車載系統(tǒng)的研發(fā)過程中，范文先生網(wǎng)收集整理主要需解決的問題是車載系統(tǒng)為了實現(xiàn)自導(dǎo)航，必須存儲大量的定位數(shù)據(jù)每天需要存儲約6；其二是這些數(shù)據(jù)還要通過信道上傳到控制調(diào)度中心若通過短信業(yè)務(wù)發(fā)送， 每次160，則需要每分上傳6次無疑，數(shù)據(jù)壓縮是在不增加硬件成本的前提下，從軟件的角度來充分 發(fā)揮系統(tǒng)現(xiàn)有資源的有效辦法。 數(shù)據(jù)壓縮方法種類繁多，可以分為無損壓縮和有損壓縮兩大類。 無損壓縮利用數(shù)據(jù)的統(tǒng)計冗余進(jìn)行壓縮。 數(shù)據(jù)統(tǒng)計冗余度的理論限制，般為21到51。 這類方法廣泛用于文本數(shù)據(jù)、程序和特殊應(yīng)用場合的圖像數(shù)據(jù)如

3、指紋 圖像、醫(yī)學(xué)圖像等的壓縮。有損壓縮方法利用了人類視覺對圖像中的某些頻率成分不敏感的特 性，允許壓縮過程中的損失一定的信息。雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的部分對理解原始圖像的影 響較小，卻換來了大得多的壓縮比。有損壓縮廣泛應(yīng)用于語音、圖像和視頻數(shù)據(jù)的壓縮。 目前現(xiàn)在的壓縮算法很多，但不能直接用于嵌入式系統(tǒng)當(dāng)中，這完全 由嵌入式系統(tǒng)的特點所決定。首先，用于嵌入式系統(tǒng)的數(shù)據(jù)壓縮方法應(yīng)是無損壓縮方法。 其次，壓縮代碼和解碼所需的信息代碼必須足夠短，否則就會失去壓 縮的意義。還有，嵌入式系統(tǒng)的數(shù)據(jù)壓縮必須結(jié)合具體的數(shù)據(jù)格式的特點，才能 進(jìn)一步提高數(shù)據(jù)的壓縮比。除此之外， 目前的壓縮程序的啟動

4、執(zhí)行必須人為干擾， 不能自動執(zhí)行， 因為它們是為文件系統(tǒng)設(shè)計的，而嵌入式系統(tǒng)的數(shù)據(jù)壓縮必須能夠自動執(zhí) 行。1數(shù)據(jù)格式板由變頻器、信號通道、微處理器和存儲單元等組成。 板的型號甚多，性能各異，但大多采用美國國家海洋電子協(xié)會制定的-0183通信標(biāo)準(zhǔn)格式。本系統(tǒng)選擇的是美國公司的板。板語句的輸入、輸出是通過232串行接口完成的，其通信端口的數(shù)據(jù) 格式應(yīng)該設(shè)置為8個數(shù)據(jù)位、1個起始位和1個停止位，校驗方式選為無 奇偶校驗，波特率設(shè)置為4800波特。-0183通信標(biāo)準(zhǔn)的輸出數(shù)據(jù)采用的是碼，其內(nèi)容包含了緯度、經(jīng)度、 高度、速度、日期、時間、航向以及衛(wèi)星狀況等信息， 語句有六種，包括，、 和。對于不同的用途

5、，選用的語句記錄也不同，例如嵌入式車載系統(tǒng)的使 用者只關(guān)心其日期和時間、 糾度、面速度信息， 因而可以只選用記錄語句。一條$語句包括13個記錄語句標(biāo)識頭、世界時間、定位狀態(tài)、緯度、 緯度方位、經(jīng)度、經(jīng)度方位、地面速度、地面路線、日期、磁偏角、校驗 和和結(jié)束標(biāo)記，它一共占用70個字節(jié)其中還包括用于分隔記錄所使用的11個逗號，例如$,121530998,40000162,116195476,000,24081,160102,*3由此可見， 從板接收下來的數(shù)據(jù)流是文本字符串，根據(jù)數(shù)據(jù)格式的特點， 本設(shè)計中擬采用半字節(jié)法完成壓縮及解壓縮的任務(wù)。該方法屬于無損壓縮技術(shù)，其原理是去除字節(jié)中的冗余位，從而達(dá)

6、到 壓縮目的。然而，這種方法只適用于純數(shù)字文本文件的壓縮，顯然定位數(shù)據(jù)并不 是純數(shù)字的，還必須在壓縮前進(jìn)行一下壓縮預(yù)處理，最后再利用半字節(jié)壓 縮算法完成數(shù)據(jù)的壓縮2壓縮預(yù)處理仔細(xì)觀察以上各段數(shù)據(jù)記錄，可以發(fā)現(xiàn)語句之間的數(shù)據(jù) 段還存在很多冗余。除此之外，這些記錄中所含的信息既有英文字符又有數(shù)字，為了后續(xù) 的壓縮，對語句中的各個記錄應(yīng)做如下的預(yù)處理1語句標(biāo)識頭因為每個語句的標(biāo)識頭都一樣， 所以該記錄段屬地冗余 信息，完全可以去除，在解壓縮時再在每個語句前加上該標(biāo)識頭即可。2世界時間該信息段以時、 分、秒、毫秒的格式指示出當(dāng)時世界時間。 轉(zhuǎn)換為北京時間還需要再加上8小時。由于車載系統(tǒng)的定位數(shù)據(jù)的采集

7、是以秒為單位的，所以毫秒量級的數(shù) 據(jù)對本系統(tǒng)根本無用，是冗余信息，由于世界時間是按秒增1，定位數(shù)據(jù)也是每委員長更新一次，所以世界時間可以在程序的一開始采集記錄一下， 在解壓縮時根據(jù)語句的指針值再加上起始時間便可以復(fù)原，因此該記錄段 在第一次存儲后，以后的語句中的該信息全都是冗余信息。3定位狀態(tài)占用1個字節(jié)，不進(jìn)行預(yù)處理。 由于車載系統(tǒng)處于的地方有可能收不到衛(wèi)星信號如隧道中，致使定位 信息無效， 因此盡管該字段發(fā)生變化的概率較小， 又與其它信息段不相關(guān)， 在此仍不能做預(yù)處理。4緯度占用9個字節(jié)，不進(jìn)行預(yù)處理。5緯度占用10個字節(jié)，不進(jìn)行預(yù)處理。6經(jīng)度指示器占一個字節(jié)，它指示出經(jīng)度是東經(jīng)，還是匹配

8、。由于各個$語句中的該段信息在中國都是東徑，它是冗余信息，因此 也采取程序一開始存儲一次的方法。7緯度指示器占一個字節(jié)，各個$語句中的該段信息完全一樣，是冗 余信息，處理方法與上相同。8地面速度占用4個字節(jié)，不進(jìn)行預(yù)處理。9日期占用6個字節(jié)，以日、月、年的格式顯示，各個$語句中的該 段信息在24小時內(nèi)完全一樣，是冗余信息，采取程序一開始存儲一次的 方法，以后語句中的該段信息全部廢除。10校驗和占用3個字節(jié)， 該數(shù)據(jù)完成校驗后便棄之， 不保留和進(jìn)行壓 縮。結(jié)束符合占用2個字節(jié)，只用來判斷語句的有效數(shù)據(jù)范圍，其它記錄 段與本系統(tǒng)的設(shè)計無關(guān)都不保留和進(jìn)行壓縮。通過以上壓縮預(yù)處理后，保留了四個數(shù)據(jù)記錄

9、，共占用24個字節(jié)， 如圖1所示。3改進(jìn)型半字節(jié)壓縮算法文本數(shù)據(jù)的壓縮的都是無損壓縮技術(shù)，即還 原后的文件應(yīng)該與源文件完全相同。文本文件壓縮的方法有很多種， 如編碼、算術(shù)編碼和字節(jié)壓縮方法等。 它們均是無損壓縮方法，都適用于文本數(shù)據(jù)的壓縮。半字節(jié)壓縮方法是針對文本數(shù)據(jù)的特點所設(shè)計的，主要是去除文本中 的字節(jié)中的冗余位，從而達(dá)到減少數(shù)據(jù)文件所占用的存儲空間的目的。在數(shù)據(jù)壓縮技術(shù)中，除壓縮重復(fù)字符外，還可以根據(jù)數(shù)據(jù)本身的特點 進(jìn)行壓縮。在計算機(jī)中，任何數(shù)據(jù)都是以某種代碼的方式存儲的在些文件中，或許有一些代碼具有某些相似之處，我們可以根據(jù)代碼 的特點進(jìn)行特定的操作，壓縮掉這些數(shù)據(jù)的相似部分，或者說壓

10、縮掉這些 數(shù)據(jù)的特征部分，半字節(jié)壓縮就是這樣一種方法。半字節(jié)方法主要用于純數(shù)字的文本文件的壓縮，因為數(shù)字09的碼的高四位都一樣，是冗余的，因此每一個數(shù)字完全可以用低四位描述，即每個字節(jié)的八位編碼可壓縮為四位編碼，壓縮比理論上可趨近50。從圖1中可以看出，經(jīng)過預(yù)處理后的數(shù)據(jù)中，包含的文本字節(jié)有09十個數(shù)字符號， 、兩個英文大寫字母和一個小數(shù)點符號，共13個字符。、的碼的高四位顯然與數(shù)字字節(jié)的不一樣，半字節(jié)壓縮方法不能簡單套用。然而，我們知道四位二進(jìn)制編碼可區(qū)分16種狀態(tài)，用來表示13種不同的字符是足夠的。壓縮數(shù)據(jù)編碼表如表1的慰，為了充分利用編碼表中的狀態(tài)，在原來13個字節(jié)的基礎(chǔ)上又新增添了兩個

11、字符和，其四位編碼分別為1101和1110。這兩個字符是在壓縮預(yù)處理過程中，用來記錄那些因語句校驗和出錯 而舍棄的語句。因為每條語句的時間信息全部在預(yù)處理階段被舍棄，在解壓縮時要恢 復(fù)時間值。該值在正常情況下是根據(jù)時間的基數(shù)再加上語句的計數(shù)值由于每秒接受到一條語句，所以語句計數(shù)值就是以秒為單位的時間增量確定的。當(dāng)發(fā)生語句校驗和出錯時，若處于定位有效狀態(tài)，則在定位狀態(tài)記錄上不填寫字符，而填寫字符；若處在定位無效狀態(tài)，則不填寫字符，而填 寫字節(jié)。在以后解壓縮時，若檢測到、字節(jié)，時間的還原按正常的算法進(jìn)行； 若檢測到、字符時，進(jìn)行的還原除了按正常的算法進(jìn)行以外還要加上秒鐘， 這樣才能確保時間能夠正確

12、的恢復(fù)，這是因為、字節(jié)表示上一條語句發(fā) 生錯誤已經(jīng)被丟棄，語句的壓縮是非連續(xù)的，有繼句現(xiàn)象發(fā)生。表1壓縮數(shù)據(jù)編碼表預(yù)處理后所含的字符碼四位二制編碼備注012345678900110000001100010011001000110011001101000011010100110110001101110011100000111001001011100100000101000010010101100101011100000001001000110100010101100111100010011010101111011100 1110定位有效定位有效， 秒值1定位無效定位無效， 秒增1通過此編碼表 進(jìn)

13、行轉(zhuǎn)換后，原來經(jīng)過壓縮預(yù)處理后的固定24個字節(jié)第的文本數(shù)據(jù)就可 以減小一半壓縮后為固定的12個字節(jié)長，壓縮比為50，若從未經(jīng)過預(yù)處 理的文本數(shù)據(jù)算起，則壓縮比可達(dá)到80。由圖2可知，實現(xiàn)半字節(jié)壓縮算法需要解決兩上問題首先是壓縮對象 的計數(shù)；其次是如何把兩個數(shù)字的低位合并到一個字節(jié)中。后一個問題只要規(guī)定好壓縮后的字節(jié)中奇數(shù)號字符的四位編碼與偶 數(shù)號字符的四位編碼的存放次序即可，程序的實現(xiàn)非常簡單，在此我們規(guī) 定編號是奇數(shù)的字符放在高四位，編號為偶數(shù)的字符的編碼放在低四位。假設(shè)壓縮前的數(shù)據(jù)流中的前四個字節(jié)分別為1、2、3、4,則壓縮后的數(shù)據(jù)格式如圖3所示半字節(jié)壓縮中需要解決的首要問題是壓縮對象的計

14、數(shù)問題，解決此問 題的方法有兩種一種是半字節(jié)計數(shù)器-，另一種是全字節(jié)計數(shù)器-。 不管那一種方法， 它們都要占用字節(jié)，再加上壓縮標(biāo)識也要占用字節(jié)， 所以要影響數(shù)據(jù)的壓縮比。改進(jìn)后的半字節(jié)壓縮算法完全解決了此問題，因為定位數(shù)據(jù)經(jīng)過壓縮 預(yù)處理后的數(shù)據(jù)長度是固定的24個字節(jié)長，不是動態(tài)可變的，所以不需 要解決壓縮對象的計數(shù)問題。一般來說，任何一種壓縮算法都需要用壓縮指示字符作壓縮數(shù)據(jù)的標(biāo) 識，壓縮標(biāo)識符越短越好，因為過長會影響縮效果。然而，由于定位數(shù)據(jù)中的所有字符都進(jìn)行了編碼處理，不存在原樣字 符不進(jìn)行壓縮的字符， 在解壓縮時原樣輸出， 因此壓縮標(biāo)識完全可以省略， 可進(jìn)一步提高數(shù)據(jù)的壓縮比。壓縮預(yù)處

15、理程序框圖和改進(jìn)后的半字節(jié)壓縮算法框圖如圖4所示。 壓縮文件包括解壓縮所需的重要信息，由釋放參數(shù)信息和依次壓縮了 的定長數(shù)據(jù)塊組成。釋放參照信息包含有解壓縮所要使用的時間基數(shù)信息，它通過語句計 數(shù)器以及錯誤代碼號可以將時間還原。除此之外，釋放參照信息還包括各個定長數(shù)據(jù)塊在解壓縮時所需的共 同信息，如、日期，壓縮文件的格式如圖5所示。嵌入式系統(tǒng)的壓縮是不需要人為干涉、而自動實時完成的，具體的實 現(xiàn)方法是通過駐留內(nèi)存單任務(wù)操作系統(tǒng)中，如或作為一個后臺任務(wù)在多任 務(wù)操作系統(tǒng)中，如中對數(shù)據(jù)完成實時壓縮或解壓縮表2改進(jìn)型半字節(jié)壓縮算法的測試結(jié)果處理文件大小預(yù)處理后改進(jìn)型半字節(jié)壓縮壓縮比1035=69X150001035=69X15001036=69X150360+2336+2336+23180+23