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

摘要：為了解決嵌入式GPS車載系統(tǒng)存儲空間小、GPS定位數(shù)據(jù)量大的矛盾，根據(jù)GPS定位數(shù)據(jù)的特點，提出了專用于GPS定全數(shù)據(jù)壓縮的改進型半字節(jié)壓縮算法。該算法是一種在原半字節(jié)壓縮算法的基礎上改進的算法，經(jīng)過實際測試，壓縮比可達50%。若將壓縮預處理也折算法在內(nèi)，總壓縮比可達80%以上，為車載系統(tǒng)節(jié)省了大量的存儲資源。除此之外，也縮短了GSM信道的占用時間，大大地緩解了向控制調度中心上傳數(shù)據(jù)的壓力。

嵌入式GPS車載系統(tǒng)般體積較小，無存儲量大的硬盤等設備，系統(tǒng)程序、應用程序一般裝在FLASH或ROM中。由于FLASH或ROM等存儲介質的價格相對臺式機上廣泛使用的硬盤、光盤等來說是非常昂貴的，因此，在開發(fā)嵌入式系統(tǒng)的軟件產(chǎn)品時必須將軟件所占的存儲空間限制在一定的范圍內(nèi)。

在GPS車載系統(tǒng)的研發(fā)過程中，主要需解決的問題是：車載系統(tǒng)為了實現(xiàn)自導航，必須存儲大量的GPS定位數(shù)據(jù)（每天需要存儲約6MB）；其二是這些數(shù)據(jù)還要通過GSM信道上傳到控制調度中心（若通過短信業(yè)務發(fā)送，每次160B，則需要每分上傳6次）。無疑，數(shù)據(jù)壓縮是在不增加硬件成本的前提下，從軟件的角度來充分發(fā)揮系統(tǒng)現(xiàn)有資源的有效辦法。

數(shù)據(jù)壓縮方法種類繁多，可以分為無損壓縮和有損壓縮兩大類。無損壓縮利用數(shù)據(jù)的統(tǒng)計冗余進行壓縮。數(shù)據(jù)統(tǒng)計冗余度的理論限制，般為2：1到5：1。這類方法廣泛用于文本數(shù)據(jù)、程序和特殊應用場合的圖像數(shù)據(jù)（如指紋圖像、醫(yī)學圖像等）的壓縮。有損壓縮方法利用了人類視覺對圖像中的某些頻率成分不敏感的特性，允許壓縮過程中的損失一定的信息。雖然不能完全恢復原始數(shù)據(jù)，但是所損失的部分對理解原始圖像的影響較小，卻換來了大得多的壓縮比。有損壓縮廣泛應用于語音、圖像和視頻數(shù)據(jù)的壓縮。

目前現(xiàn)在的壓縮算法很多，但不能直接用于嵌入式系統(tǒng)當中，這完全由嵌入式系統(tǒng)的特點所決定。首先，用于嵌入式系統(tǒng)的數(shù)據(jù)壓縮方法應是無損壓縮方法。其次，壓縮代碼和解碼所需的信息代碼必須足夠短，否則就會失去壓縮的意義。還有，嵌入式系統(tǒng)的數(shù)據(jù)壓縮必須結合具體的數(shù)據(jù)格式的特點，才能進一步提高數(shù)據(jù)的壓縮比。除此之外，目前的壓縮程序的啟動執(zhí)行必須人為干擾，不能自動執(zhí)行，因為它們是為文件系統(tǒng)設計的，而嵌入式系統(tǒng)的數(shù)據(jù)壓縮必須能夠自動執(zhí)行。

1 GPS數(shù)據(jù)格式

GPS OEM板由變頻器、信號通道、微處理器和存儲單元等組成。GPS OEM板的型號甚多，性能各異，但大多采用美國國家海洋電子協(xié)會制定的NMEA-0183通信標準格式。本系統(tǒng)選擇的是美國SiRF公司的SiRFstarII OEM板。SiRFstarII OEM板語句的輸入、輸出是通過RS232串行接口完成的，其通信端口的數(shù)據(jù)格式應該設置為8個數(shù)據(jù)位、1個起始位和1個停止位，校驗方式選為無奇偶校驗，波特率設置為4800波特。NMEA-0183通信標準的輸出數(shù)據(jù)采用的是ASCII碼，其內(nèi)容包含了緯度、經(jīng)度、高度、速度、日期、時間、航向以及衛(wèi)星狀況等信息，語句有六種，包括GGA，GLL、GSA、GSV、RMC和VTG。對于不同的用途，選用的語句記錄也不同，例如嵌入式GPS車載系統(tǒng)的使用者只關心其日期和時間、糾度、面速度信息，因而可以只選用RMC記錄語句。一條$GPRMC語句包括13個記錄：語句標識頭、世界時間、定位狀態(tài)、緯度、緯度方位、經(jīng)度、經(jīng)度方位、地面速度、地面路線、日期、磁偏角、校驗和和結束標記，它一共占用70個字節(jié)（其中還包括用于分隔記錄所使用的11個逗號），例如：

$GPRMC,121530.998,A,4000.0162,N,11619.5476,E,0.00,240.81,160102,,*3B

由此可見，從SiRFstarII OEM板接收下來的數(shù)據(jù)流是文本字符串，根據(jù)GPS數(shù)據(jù)格式的特點，本設計中擬采用半字節(jié)法完成壓縮及解壓縮的任務。該方法屬于無損壓縮技術，其原理是去除字節(jié)中的冗余位，從而達到壓縮目的。然而，這種方法只適用于純數(shù)字文本文件的壓縮，顯然GPS定位數(shù)據(jù)并不是純數(shù)字的，還必須在壓縮前進行一下壓縮預處理，最后再利用半字節(jié)壓縮算法完成數(shù)據(jù)的壓縮。

2 壓縮預處理

仔細觀察以上各段數(shù)據(jù)記錄，可以發(fā)現(xiàn)語句之間的數(shù)據(jù)段還存在很多冗余。除此之外，這些記錄中所含的信息既有英文字符又有數(shù)字，為了后續(xù)的壓縮，對語句中的各個記錄應做如下的預處理：

①語句標識頭（ID）：因為每個語句的標識頭都一樣，所以該記錄段屬地冗余信息，完全可以去除，在解壓縮時再在每個語句前加上該標識頭即可。

    ②世界時間（UTC）：該信息段以時、分、秒、毫秒的格式指示出當時世界時間。轉換為北京時間還需要再加上8小時。由于車載系統(tǒng)的定位數(shù)據(jù)的采集是以秒為單位的，所以毫秒量級的數(shù)據(jù)對本系統(tǒng)根本無用，是冗余信息，由于世界時間是按秒增1，定位數(shù)據(jù)也是每委員長更新一次，所以世界時間可以在程序的一開始采集記錄一下，在解壓縮時根據(jù)語句的指針值再加上起始時間便可以復原，因此該記錄段在第一次存儲后，以后的語句中的該信息全都是冗余信息。

③定位狀態(tài)（A/V）：占用1個字節(jié)，不進行預處理。由于車載系統(tǒng)處于的地方有可能收不到衛(wèi)星信號（如隧道中），致使定位信息無效，因此盡管該字段發(fā)生變化的概率較小，又與其它信息段不相關，在此仍不能做預處理。

④緯度：占用9個字節(jié)，不進行預處理。

⑤緯度：占用10個字節(jié)，不進行預處理。

⑥經(jīng)度指示器（E/W）：占一個字節(jié)，它指示出經(jīng)度是東經(jīng)，還是匹配。由于各個$GPRMC語句中的該段信息在中國都是東徑，它是冗余信息，因此也采取程序一開始存儲一次的方法。

⑦緯度指示器（N/S）：占一個字節(jié)，各個$GPRMC語句中的該段信息完全一樣，是冗余信息，處理方法與上相同。

⑧地面速度：占用4個字節(jié)，不進行預處理。

⑨日期：占用6個字節(jié)，以日、月、年的格式顯示，各個$GPRMC語句中的該段信息在24小時內(nèi)完全一樣，是冗余信息，采取程序一開始存儲一次的方法，以后語句中的該段信息全部廢除。

⑩校驗和：占用3個字節(jié)，該數(shù)據(jù)完成校驗后便棄之，不保留和進行壓縮。

結束符合占用2個字節(jié)，只用來判斷語句的有效數(shù)據(jù)范圍，其它記錄段與本系統(tǒng)的設計無關都不保留和進行壓縮。

通過以上壓縮預處理后，保留了四個數(shù)據(jù)記錄，共占用24個字節(jié)，如圖1所示。

3 改進型半字節(jié)壓縮算法

文本數(shù)據(jù)的壓縮的都是無損壓縮技術，即還原后的文件應該與源文件完全相同。文本文件壓縮的方法有很多種，如HUFFMAN編碼、算術編碼和字節(jié)壓縮方法等。它們均是無損壓縮方法，都適用于文本數(shù)據(jù)的壓縮。半字節(jié)壓縮方法是針對文本數(shù)據(jù)的特點所設計的，主要是去除文本中的字節(jié)中的冗余位，從而達到減少數(shù)據(jù)文件所占用的存儲空間的目的。在數(shù)據(jù)壓縮技術中，除壓縮重復字符外，還可以根據(jù)數(shù)據(jù)本身的特點進行壓縮。在計算機中，任何數(shù)據(jù)都是以某種代碼的方式存儲的。在些文件中，或許有一些代碼具有某些相似之處，我們可以根據(jù)代碼的特點進行特定的操作，壓縮掉這些數(shù)據(jù)的相似部分，或者說壓縮掉這些數(shù)據(jù)的特征部分，半字節(jié)壓縮就是這樣一種方法。半字節(jié)方法主要用于純數(shù)字的文本文件的壓縮，因為數(shù)字0～9的ASCII碼的高四位都一樣，是冗余的，因此每一個數(shù)字完全可以用低四位描述，即每個字節(jié)的八位編碼可壓縮為四位編碼，壓縮比理論上可趨近50%。

從圖1中可以看出，經(jīng)過預處理后的數(shù)據(jù)中，包含的文本字節(jié)有：“0～9”十個數(shù)字符號，“A”、“V”兩個英文大寫字母和一個小數(shù)點“.”符號，共13個字符。“A”、“V”、“.”的ASCII碼的高四位顯然與數(shù)字字節(jié)的不一樣，半字節(jié)壓縮方法不能簡單套用。然而，我們知道四位二進制編碼可區(qū)分16種狀態(tài)，用來表示13種不同的字符是足夠的。

壓縮數(shù)據(jù)編碼表如表1的慰，為了充分利用編碼表中的狀態(tài)，在原來13個字節(jié)的基礎上又新增添了兩個字符“B”和“W”，其四位編碼分別為1101和1110。這兩個字符是在壓縮預處理過程中，用來記錄那些因語句校驗和出錯而舍棄的語句。因為每條語句的時間信息全部在預處理階段被舍棄，在解壓縮時要恢復時間值。該值在正常情況下是根據(jù)時間的基數(shù)再加上語句的計數(shù)值（由于每秒接受到一條語句，所以語句計數(shù)值就是以秒為單位的時間增量）確定的。當發(fā)生語句校驗和出錯時，若處于定位有效狀態(tài)，則在定位狀態(tài)記錄上不填寫“A”字符，而填寫“B”字符；若處在定位無效狀態(tài)，則不填寫“V”字符，而填寫“W”字節(jié)。在以后解壓縮時，若檢測到“A”、“V”字節(jié)，時間的還原按正常的算法進行；若檢測到“B”、“W”字符時，進行的還原除了按正常的算法進行以外還要加上秒鐘，這樣才能確保時間能夠正確的恢復，這是因為“B”、"W"字節(jié)表示上一條語句發(fā)生錯誤已經(jīng)被丟棄，語句的壓縮是非連續(xù)的，有繼句現(xiàn)象發(fā)生。

表1 壓縮數(shù)據(jù)編碼表

通過此編碼表進行轉換后，原來經(jīng)過壓縮預處理后的固定24個字節(jié)第的文本數(shù)據(jù)就可以減小一半（壓縮后為固定的12個字節(jié)長），壓縮比為50%，若從未經(jīng)過預處理的文本數(shù)據(jù)算起，則壓縮比可達到80%。

由圖2可知，實現(xiàn)半字節(jié)壓縮算法需要解決兩上問題：首先是壓縮對象的計數(shù)；其次是如何把兩個數(shù)字的低位合并到一個字節(jié)中。后一個問題只要規(guī)定好壓縮后的字節(jié)中奇數(shù)號字符的四位編碼與偶數(shù)號字符的四位編碼的存放次序即可，程序的實現(xiàn)非常簡單，在此我們規(guī)定編號是奇數(shù)的字符放在高四位，編號為偶數(shù)的字符的編碼放在低四位。假設壓縮前的數(shù)據(jù)流中的前四個字節(jié)分別為“1、2、3、4”,則壓縮后的數(shù)據(jù)格式如圖3所示。

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

    壓縮文件包括解壓縮所需的重要信息，由釋放參數(shù)信息和依次壓縮了的定長數(shù)據(jù)塊組成。釋放參照信息包含有解壓縮所要使用的時間基數(shù)信息，它通過語句計數(shù)器以及錯誤代碼號可以將時間還原。除此之外，釋放參照信息還包括各個定長數(shù)據(jù)塊在解壓縮時所需的共同信息，如E/W、N/S、日期，壓縮文件的格式如圖5所示。

嵌入式系統(tǒng)的壓縮是不需要人為干涉、而自動實時完成的，具體的實現(xiàn)方法是通過駐留內(nèi)存（單任務操作系統(tǒng)中，如DSP）或作為一個后臺任務（在多任務操作系統(tǒng)中，如Windows中）對數(shù)據(jù)完成實時壓縮或解壓縮。

表2 改進型半字節(jié)壓縮算法的測試結果

GPS定位數(shù)據(jù)的壓縮算法經(jīng)過實際的驗證，壓縮比隨著壓縮數(shù)據(jù)的減小而略有減少，這是因為參照信息隨著壓縮數(shù)據(jù)的減小其所占的比例在逐漸增加的原故。但示，該壓縮方法在車載系統(tǒng)中使用不僅能節(jié)省存儲空間，而且能減少信道占有時間及提高數(shù)據(jù)的安全性。由于壓縮程序是針對GPS數(shù)據(jù)格式編寫的的，因此其壓縮比大但通用性不強。盡管如此，該程序略做修改可移植到其它系統(tǒng)中，因為各個GPS廠家所執(zhí)行的規(guī)范標準都是GPS廠家所執(zhí)行的規(guī)范標準都是NMEA-0183，其數(shù)據(jù)的輸出格式略有差別。