基于數理統計的北斗數據無損壓縮方法研究

非鵬 武漢理工大學

錢廷發 上海普適導航有限公司

殷悅 交通運輸部水運科學研究所

目前北斗衛星短報文通信系統中，普通北斗通訊終端，每分鐘可以發一次通信，每次通訊容量為628 Bit（等于78.5 Byte）；對于傳輸的中文正文,一般采用GB2312編碼形式，GB2312采用2個By te編碼一個漢字。因此每次北斗報文僅能傳輸39個漢字，相對傳輸信息量較小。對于稍大的通訊數據量都需要拆包分段發送,使得傳輸時間加長，用戶體驗度差。

《現代漢語詞典》是目前較權威的大型現代漢語詞典，最新版的收詞56000多條。其中包括了字、詞、短語、熟語、成語等。在日常的語言交流中，常用的詞組、短語、短句在1000個左右。

本文通過對上海普適導航北斗運營系統中，包含的海量的北斗通訊內容，進行統計分析，發現大量的頻繁詞組、短語、短句。如能對其進行一定的編碼，通過一定的格式和現有的編碼進行兼容區分，做到唯一性解析，就能極大提升數據傳輸的效率，實現了北斗通訊的無損壓縮傳輸。

1.編碼兼容

GB2312中文編碼采用2字節編碼，從A1A0開始，到FEFF結束。為兼容ACSII編碼，可以看到GB2312編碼的第一字節的第一位都是1，ASCII編碼的1字節表示，其第一位為0，如表1、表2。

由于GB2312中文編碼第一字節從A1到FE,因此在兼容A SCII的情況下，GB2312首字節共有33個編碼未使用（下文又稱額外編碼），對應的十進制范圍為128～159（0X80～0X98）及255(0XFF)。如表3所示。

表1 ASCII 編碼方式

2.自定義雙字節編碼

由于額外編碼僅用1個字節表示，為了使編碼效率最高，因此把最常用的可見ASCII碼及部分常見的中文全角符放到額外編碼表中。通過數據分析，33個常用的自定義額外編碼，形成編碼字典。編碼形式如表4。

表2 GB2312中文編碼

表3 GB2312未使用的首字節

表4 自定義額外編碼表

圖1 對中文短信進行雙字解碼流程

圖2 對中文短信進行雙字節編碼流程

表6 哈夫曼字節編碼

圖3 哈夫曼編碼樹

采用2字節表示自定義編碼，為解析兼容，其中第一字節第一位固定為0，有15位編碼可以定義，因此可表示32768個編碼組合，編碼格式如表5所示。

可見的ASCII碼共79個，表5中已經實現了28個編碼，因此對剩下的51個編碼進行編碼，32768個編碼組合還剩下32717個編碼。根據統計數據取前32717個使用頻率最高的詞語、短語進行編碼。形成編碼字典。整個北斗通訊編碼中，采用三種編碼方式組合的形式：

33個額外編碼+雙字節自定義編碼+GB2312編碼

對于沒有在編碼字典中出現的中文字符使用GB2312編碼，三類編碼沒有先后順序，任意搭配，都能唯一解析。三種編碼識別方法如下：

首先判斷第1字節的第1 位是否為0，為0 說明是自定義編碼，取走2字節到自定義編碼字典中匹配還原；為1時候，再看該字節是否為128～159及255這33個數字，如是說明是額外編碼，取走1字節到額外編碼字典中匹配還原，如不是，說明是GB2312編碼，取走2字節，并不需要到編碼字典中還原，如圖1所示。編碼流程逆向處理，流程類似，如圖2所示。

3.分組哈夫曼變長編碼

哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。通過構建哈夫曼樹進行編碼的特殊之處在于，它是根據每一個源字符出現的估算概率而建立起來的，出現概率高的字符使用較短的編碼，反之出現概率低的則使用較長的編碼。這便使編碼之后的字符串的平均期望長度降低。

自定義哈夫曼編碼采用動態長度編碼實現，自定義編碼長度由10～16Bit組成，第1Bit為0，用于區分GB2312編碼，第2～8Bit用來表示0000000～1111111共128個分組。哈夫曼編碼動態由2～8Bits組成(其中第一bit表示左右子樹)，組成情況見表6。

對每分組中的哈夫曼樹，如圖3所示。

每棵哈夫曼樹可以形成如下編碼，哈夫曼編碼的特殊性，可以確保編碼、解碼的唯一性，根據定義的規則產生如編碼表6。

每棵哈夫曼樹上可以形成16個編碼，對應到128個分組上，就可以有2048個編碼。哈夫曼編碼由2～8Bits組成，優先編碼51個ASCII可見字符（另外28個已經在拓展編碼表中實現）和出現次數多的詞語、詞組、短語，使它們的編碼長度盡可能小，出現次數少的，編碼長度大。

表6 哈夫曼編碼表

表7 哈夫曼編碼字典

編碼設定完成后，形成自定義哈夫曼編碼字典，如表7所示。

哈夫曼編碼解碼過程，通過判斷剩余下的解碼緩存中的第1 bit,如是1Bit，再判斷第一字節是否是128～159及255，如是說明是額外編碼，取走1字節,把對應的額外編碼詞，放入解碼串中，如不是128～159及255，說明接下來的16 Bits 是GB2312編碼，表示一個漢字，解碼緩存中移走16Bits，解碼串中添加該16Bits；如是0 bit，說明接下來的是拓展編碼，需要嘗試匹配10到16Bit，有無該拓展編碼，如是N Bit匹配到，從解碼緩存中移走相應的N Bits，并把相應的詞典詞加到解碼結果字符串中；重復上面的解碼過程直到解碼緩存小于8Bits。

編碼流程逆向處理，流程類似，如圖5所示。

4.實現效果

首先定義壓縮倍數，在這里定義為分壓縮傳輸所需的字節數除以壓縮傳輸的字節數。隨機抽取10個短信，分別進行雙字節自定義編碼和分組哈夫曼編碼，進行效果驗證分析，傳輸效率如圖6所示。

針對10 個樣本，不同的傳輸內容，壓縮效率會不同。分組哈夫曼編碼的平均壓縮效率為 1.96，自定義雙字節編碼平均壓縮效率為1.84。通過以上的研究分析，可以看出本文的研究具有較好的壓縮效率和可行性。

5.結論

針對目前北斗衛星短報文通信系統中，普通北斗通訊終端每次北斗報文僅能傳輸39個漢字，相對傳輸信息量較小。對于稍大的通訊數據量都需要拆包分段發送，使得傳輸時間加長，用戶體驗度差的問題，本文通過對海量北斗通訊內容，進行統計分析，發現大量的頻繁詞組、短語、短句，對其進行一定的編碼，通過一定的格式和現有的編碼進行兼容區分，做到唯一性解析，極大提升了數據傳輸的效率，實現了北斗通訊的無損壓縮傳輸。