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

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

（中國(guó)鐵道科學(xué)研究院 通信信號(hào)研究所，北京 100081）

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

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

（中國(guó)鐵道科學(xué)研究院 通信信號(hào)研究所，北京 100081）

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

GSM-R；GPRS；壓縮算法

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

1 常用壓縮算法

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

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

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

1.1 游程編碼

游程編碼是一種簡(jiǎn)單的統(tǒng)計(jì)編碼，它統(tǒng)計(jì)連續(xù)出現(xiàn)字符的頻次并使用固定長(zhǎng)度的碼來(lái)代替，例如：對(duì)于“AAAAABCCCC”這個(gè)字符串，可以用“5A1B4C”代替。可見，游程編碼壓縮的效果取決于原始字符串中連續(xù)字符出現(xiàn)的頻次，如果連續(xù)出現(xiàn)的字符數(shù)較少，游程編碼起不到壓縮的效果，甚至編碼后的數(shù)據(jù)會(huì)增加。

1.2 哈夫曼編碼

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

圖1 哈夫曼樹示例

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

1.3 算術(shù)編碼

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

1.4 LZSS算法

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

1.5 LZW算法

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

表1 字典表示

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

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

圖2 不同算法的壓縮比

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

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

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

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

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

3 結(jié)束語(yǔ)

與GPRS應(yīng)用業(yè)務(wù)的壓縮比和源數(shù)據(jù)統(tǒng)計(jì)冗余有關(guān)，從現(xiàn)場(chǎng)實(shí)驗(yàn)看，采用游程編碼、LZSS算法、LZW算法對(duì)無(wú)線車次號(hào)校核信息可起到壓縮作用，對(duì)調(diào)度命令信息、列控動(dòng)態(tài)監(jiān)測(cè)信息無(wú)法進(jìn)行有效的壓縮。采用外置字符概率表的哈夫曼編碼、算術(shù)編碼對(duì)各類應(yīng)用業(yè)務(wù)數(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] 鄭翠芳.幾種常用無(wú)損數(shù)據(jù)壓縮算法研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展2011, 21（9）：73-76.

責(zé)任編輯 徐侃春

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

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

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