王開鋒，蔣 韻，王祖元，付 嵩

（中國鐵道科學研究院 通信信號研究所，北京 100081）

壓縮算法在GSM-R分組域數(shù)據(jù)傳輸中的應用研究

王開鋒，蔣 韻，王祖元，付 嵩

（中國鐵道科學研究院 通信信號研究所，北京 100081）

大量鐵路應用業(yè)務使用GPRS實現(xiàn)車地之間的數(shù)據(jù)通信，對GPRS資源的競爭問題十分突出。對游程編碼、哈夫曼編碼、算術編碼、LZSS算法、LZW算法等壓縮方法進行研究，通過現(xiàn)場實驗，對無線車次號校核信息、調度命令信息、列控動態(tài)監(jiān)測信息等業(yè)務數(shù)據(jù)的壓縮效果進行對比分析。

GSM-R；GPRS；壓縮算法

我國鐵路GSM-R網(wǎng)絡采用GPRS承載列車無線車次號校核信息傳送、調度命令信息無線傳送、列控動態(tài)監(jiān)測等應用。越來越多的鐵路應用業(yè)務規(guī)劃使用GPRS實現(xiàn)車地之間的數(shù)據(jù)通信，如站車信息交互、列車尾部信息傳送、災害監(jiān)測預警信息等。隨著數(shù)據(jù)量的增大，可能會導致GPRS信道擁塞，影響業(yè)務的正常應用，特別是在大型車站、動車運用所等用戶相對集中的地段，對GPRS資源的競爭問題更加突出。數(shù)據(jù)壓縮技術是緩解GPRS信道擁塞、提供GPRS資源利用效率的有效途徑之一?？梢栽诓粊G失信息的前提下，通過采用無損壓縮算法，縮減數(shù)據(jù)量，進而提高其傳輸、存儲效率。

1 常用壓縮算法

數(shù)據(jù)壓縮算法可以分為無損壓縮和有損壓縮兩種。無損壓縮通過消除統(tǒng)計冗余實現(xiàn)數(shù)據(jù)的縮減，在數(shù)據(jù)解壓時能夠完全還原源數(shù)據(jù)。有損壓縮在允許一定程度信息損失的前提下，移除一些不重要的信息，可以達到更大程度上的數(shù)據(jù)壓縮。在GSM-R網(wǎng)絡中，車地之間必須保證數(shù)據(jù)完整無誤的傳輸，因此只能采用無損壓縮技術。在數(shù)據(jù)壓縮領域，采用數(shù)據(jù)壓縮比來描述壓縮效果，數(shù)據(jù)壓縮比沒有統(tǒng)一的定義，本文采用如下公式[1]：

壓縮比= 壓縮后數(shù)據(jù)長度/未壓縮數(shù)據(jù)長度

根據(jù)上述定義，壓縮比的數(shù)值越大，壓縮的效率越高。無損壓縮的壓縮比和數(shù)據(jù)中統(tǒng)計冗余相關，若壓縮后的數(shù)據(jù)長度和源數(shù)據(jù)長度相同，壓縮比為1；若壓縮后的數(shù)據(jù)長度大于源數(shù)據(jù)長度相同，則壓縮比大于1。無損壓縮又可以分為基于統(tǒng)計的壓縮算法和基于字典的壓縮算法?；诮y(tǒng)計的方法首先統(tǒng)計數(shù)據(jù)中每個字符的出現(xiàn)次數(shù)，根據(jù)字符出現(xiàn)概率確定不同長度的字符編碼，如游程編碼、哈夫曼編碼、算術編碼等?；谧值涞姆椒◤囊粋€空串出發(fā)，動態(tài)構建一個字典，用索引來代替重復出現(xiàn)的字符或字符串，如LZSS算法、LZW算法等[2]。

1.1 游程編碼

游程編碼是一種簡單的統(tǒng)計編碼，它統(tǒng)計連續(xù)出現(xiàn)字符的頻次并使用固定長度的碼來代替，例如：對于“AAAAABCCCC”這個字符串，可以用“5A1B4C”代替?？梢姡纬叹幋a壓縮的效果取決于原始字符串中連續(xù)字符出現(xiàn)的頻次，如果連續(xù)出現(xiàn)的字符數(shù)較少，游程編碼起不到壓縮的效果，甚至編碼后的數(shù)據(jù)會增加。

1.2 哈夫曼編碼

哈夫曼編碼使用變長編碼表對源數(shù)據(jù)進行編碼，其核心思想是首先評估源數(shù)據(jù)中各個字符出現(xiàn)的概率，出現(xiàn)概率高的字符用較短的編碼，出現(xiàn)概率低的字符使用較長的編碼。這樣可以降低編碼后數(shù)據(jù)的長度，從而達到壓縮的效果。要實現(xiàn)哈夫曼編碼首先需要構造一個哈夫曼樹，“chinarailway”可以構造成圖1所示的哈夫曼樹，出現(xiàn)次數(shù)為3的字符“a”用01表示，出現(xiàn)次數(shù)為1的字符“c”用0000表示。哈夫曼編碼的壓縮效率取決于源數(shù)據(jù)中字符出現(xiàn)概率的分布情況，如果源數(shù)據(jù)中某些字符出現(xiàn)的概率遠大于另外一些字符，采用哈夫曼編碼可以得到較好的壓縮效果，極端情況下，如果源數(shù)據(jù)中每個字符出現(xiàn)的概率相同，采用哈夫曼編碼無法起到壓縮的效果。

圖1 哈夫曼樹示例

哈夫曼編碼生成的數(shù)據(jù)實際上是由兩部分組成：（1）存儲的輸入字符概率表（用于構造哈夫曼樹）；（2）是編碼數(shù)據(jù)，這樣解碼器才能夠正常進行解碼。

1.3 算術編碼

算法編碼和哈夫曼編碼類似，也需要預先對源數(shù)據(jù)字符出現(xiàn)的概率進行統(tǒng)計，然后編碼，但與哈夫曼編碼不同，算術編碼并不對每個字符編碼，而是將整個源數(shù)據(jù)編碼為[0.0,1.0)之間的小數(shù)，編碼長度等于各個輸入字符概率的乘積。算術編碼的壓縮效率要高于哈夫曼編碼，但算術編碼的運算較為復雜。

1.4 LZSS算法

LZSS算法是對LZ77算法的改進，這是一種基于字典的算法，其原理是將源數(shù)據(jù)中較長的字符串或經(jīng)常出現(xiàn)的字符構成字典中的數(shù)據(jù)項，并用較短的數(shù)字或字符表示。

1.5 LZW算法

LZW算法是對LZ78算法的改進，編碼程序和解碼程序都是從一個空字典開始，每次輸出一個標記時，創(chuàng)建一個新的短語并加入到字典中。如對于字符串“ABCABD”，將形成如下的字典，如表1所示。

表1 字典表示

2 壓縮算法在GSM-R分組域數(shù)據(jù)壓縮中的性能比較

列車無線車次號校核信息、調度命令信息、列控動態(tài)監(jiān)測信息是目前GSM-R中主要傳送的分組域數(shù)據(jù)，本文選取了某條鐵路中3類數(shù)據(jù)各2.1萬條，采用各種主流壓縮算法對數(shù)據(jù)進行壓縮，圖2為數(shù)據(jù)壓縮后的結果。

圖2 不同算法的壓縮比

從圖2看出，游程編碼、LZSS算法、LZW算法對于列車無線車次號校核信息可以起到一定程度的壓縮效果，游程編碼可將源數(shù)據(jù)壓縮為原來的69%左右，對于調度命令、DMS信息壓縮效果不明顯。這主要是因為調度命令、DMS信息的統(tǒng)計冗余比較小。

哈夫曼編碼、算術編碼對于各類數(shù)據(jù)的壓縮比均大于1，這是因為采用哈夫曼編碼或算術編碼時，需要對源數(shù)據(jù)中字符出現(xiàn)的概率進行統(tǒng)計并保存到壓縮后的數(shù)據(jù)中，而在GSM-R網(wǎng)絡分組域數(shù)據(jù)應用中，每包數(shù)據(jù)的長度很小，一般在200 byte以下，壓縮后數(shù)據(jù)中字符概率表所在比例較高，使得壓縮后的數(shù)據(jù)反而增大。

為了解決上述問題，本文采用外置輸入字符概率表的方法對哈夫曼編碼和算術編碼進行改進，預先對列車無線車次號校核信息、調度命令信息、列控動態(tài)監(jiān)測信息等各類數(shù)據(jù)生成字符概率表，對于每條源數(shù)據(jù)不動態(tài)生成也不保存字符概率表。

為了對改進的算法進行驗證，從每類2.1萬條數(shù)據(jù)中隨機選取0.1萬條作為訓練序列，統(tǒng)計其中每個字符出現(xiàn)的次數(shù)，生成字符概率表，然后對剩余的2萬條數(shù)據(jù)進行壓縮，得到圖3所示的結果。

如果采用固定的外置的字符概率表后,哈夫曼編碼和算術編碼均能獲得較好的壓縮效果，兩種算法的壓縮比相差不大。對于列車無線車次號校核信息，采用哈夫曼壓縮算法可將數(shù)據(jù)壓縮為原來的66%左右。對于調度命令信息、列控動態(tài)監(jiān)測信息，采用哈夫曼壓縮算法可將數(shù)據(jù)壓縮為原來的81%左右。

3 結束語

與GPRS應用業(yè)務的壓縮比和源數(shù)據(jù)統(tǒng)計冗余有關，從現(xiàn)場實驗看，采用游程編碼、LZSS算法、LZW算法對無線車次號校核信息可起到壓縮作用，對調度命令信息、列控動態(tài)監(jiān)測信息無法進行有效的壓縮。采用外置字符概率表的哈夫曼編碼、算術編碼對各類應用業(yè)務數(shù)據(jù)均能得到較為理想的壓縮比。

[1] Salauddin Mahmud. An Improved Data Compression Method for General Data[J]. International Journal of Scientific & Engineering Research, 2012, 3(3):2.

[2] 鄭翠芳.幾種常用無損數(shù)據(jù)壓縮算法研究[J]. 計算機技術與發(fā)展2011, 21（9）：73-76.

責任編輯 徐侃春

Application of compression algorithms in data transmission of GSM-R packet domain

WANG Kaifeng, JIANG Yun, WANG Zuyuan, FU Song
( Signal & Communication Research Institute, China Academy of Railway Sciences, Beijing 100081, China )

Train-ground wireless communication was implemented by GPRS for large number of railway application service, therefor, the problem of competing GPRS resource was very prominent. This paper studied on data compression algorithms such as Run Length Coding, Huffman Coding, Arithmetic Coding, LZSS, LZW. Field experimentation was made to contrast and analyze compression effect for the data service such as train number check information, dispatching order information, dynamic monitoring information of train control.

GSM-R; GPRS; compression algorithms

圖3 采用外置字符概率表后的壓縮比

U285.44∶TP39

A

1005-8451（2015）10-0051-03

2015-02-10

中國鐵路總公司科技研究開發(fā)計劃項目（2014X005-B）。

王開鋒，助理研究員；蔣 韻，助理研究員。