基于數(shù)理統(tǒng)計(jì)的北斗數(shù)據(jù)無損壓縮方法研究

非鵬 武漢理工大學(xué)

錢廷發(fā) 上海普適導(dǎo)航有限公司

殷悅 交通運(yùn)輸部水運(yùn)科學(xué)研究所

目前北斗衛(wèi)星短報(bào)文通信系統(tǒng)中，普通北斗通訊終端，每分鐘可以發(fā)一次通信，每次通訊容量為628 Bit（等于78.5 Byte）；對(duì)于傳輸?shù)闹形恼?一般采用GB2312編碼形式，GB2312采用2個(gè)By te編碼一個(gè)漢字。因此每次北斗報(bào)文僅能傳輸39個(gè)漢字，相對(duì)傳輸信息量較小。對(duì)于稍大的通訊數(shù)據(jù)量都需要拆包分段發(fā)送,使得傳輸時(shí)間加長，用戶體驗(yàn)度差。

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

本文通過對(duì)上海普適導(dǎo)航北斗運(yùn)營系統(tǒng)中，包含的海量的北斗通訊內(nèi)容，進(jìn)行統(tǒng)計(jì)分析，發(fā)現(xiàn)大量的頻繁詞組、短語、短句。如能對(duì)其進(jìn)行一定的編碼，通過一定的格式和現(xiàn)有的編碼進(jìn)行兼容區(qū)分，做到唯一性解析，就能極大提升數(shù)據(jù)傳輸?shù)男剩瑢?shí)現(xiàn)了北斗通訊的無損壓縮傳輸。

1.編碼兼容

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

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

表1 ASCII 編碼方式

2.自定義雙字節(jié)編碼

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

表2 GB2312中文編碼

表3 GB2312未使用的首字節(jié)

表4 自定義額外編碼表

圖1 對(duì)中文短信進(jìn)行雙字解碼流程

圖2 對(duì)中文短信進(jìn)行雙字節(jié)編碼流程

表6 哈夫曼字節(jié)編碼

圖3 哈夫曼編碼樹

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

可見的ASCII碼共79個(gè)，表5中已經(jīng)實(shí)現(xiàn)了28個(gè)編碼，因此對(duì)剩下的51個(gè)編碼進(jìn)行編碼，32768個(gè)編碼組合還剩下32717個(gè)編碼。根據(jù)統(tǒng)計(jì)數(shù)據(jù)取前32717個(gè)使用頻率最高的詞語、短語進(jìn)行編碼。形成編碼字典。整個(gè)北斗通訊編碼中，采用三種編碼方式組合的形式：

33個(gè)額外編碼+雙字節(jié)自定義編碼+GB2312編碼

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

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

3.分組哈夫曼變長編碼

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

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

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

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

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

表6 哈夫曼編碼表

表7 哈夫曼編碼字典

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

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

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

4.實(shí)現(xiàn)效果

首先定義壓縮倍數(shù)，在這里定義為分壓縮傳輸所需的字節(jié)數(shù)除以壓縮傳輸?shù)淖止?jié)數(shù)。隨機(jī)抽取10個(gè)短信，分別進(jìn)行雙字節(jié)自定義編碼和分組哈夫曼編碼，進(jìn)行效果驗(yàn)證分析，傳輸效率如圖6所示。

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

5.結(jié)論

針對(duì)目前北斗衛(wèi)星短報(bào)文通信系統(tǒng)中，普通北斗通訊終端每次北斗報(bào)文僅能傳輸39個(gè)漢字，相對(duì)傳輸信息量較小。對(duì)于稍大的通訊數(shù)據(jù)量都需要拆包分段發(fā)送，使得傳輸時(shí)間加長，用戶體驗(yàn)度差的問題，本文通過對(duì)海量北斗通訊內(nèi)容，進(jìn)行統(tǒng)計(jì)分析，發(fā)現(xiàn)大量的頻繁詞組、短語、短句，對(duì)其進(jìn)行一定的編碼，通過一定的格式和現(xiàn)有的編碼進(jìn)行兼容區(qū)分，做到唯一性解析，極大提升了數(shù)據(jù)傳輸?shù)男剩瑢?shí)現(xiàn)了北斗通訊的無損壓縮傳輸。