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

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

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

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

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

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

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

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

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

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

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

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

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

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

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