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

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

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

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

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

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

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

GSM-R；GPRS；壓縮算法

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

1 常用壓縮算法

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

壓縮比= 壓縮后數據長度/未壓縮數據長度

根據上述定義，壓縮比的數值越大，壓縮的效率越高。無損壓縮的壓縮比和數據中統計冗余相關，若壓縮后的數據長度和源數據長度相同，壓縮比為1；若壓縮后的數據長度大于源數據長度相同，則壓縮比大于1。無損壓縮又可以分為基于統計的壓縮算法和基于字典的壓縮算法。基于統計的方法首先統計數據中每個字符的出現次數，根據字符出現概率確定不同長度的字符編碼，如游程編碼、哈夫曼編碼、算術編碼等。基于字典的方法從一個空串出發，動態構建一個字典，用索引來代替重復出現的字符或字符串，如LZSS算法、LZW算法等[2]。

1.1 游程編碼

游程編碼是一種簡單的統計編碼，它統計連續出現字符的頻次并使用固定長度的碼來代替，例如：對于“AAAAABCCCC”這個字符串，可以用“5A1B4C”代替。可見，游程編碼壓縮的效果取決于原始字符串中連續字符出現的頻次，如果連續出現的字符數較少，游程編碼起不到壓縮的效果，甚至編碼后的數據會增加。

1.2 哈夫曼編碼

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

圖1 哈夫曼樹示例

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

1.3 算術編碼

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

1.4 LZSS算法

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

1.5 LZW算法

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

表1 字典表示

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

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

圖2 不同算法的壓縮比

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

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

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

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

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

3 結束語

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

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

[2] 鄭翠芳.幾種常用無損數據壓縮算法研究[J]. 計算機技術與發展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

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

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