王福源，雷成健，任建新

（1.湖南中車時代通信信號有限公司，湖南 長沙 410005；2.湖南鐵路科技職業(yè)技術(shù)學(xué)院，湖南 株洲 412001）

0 引言

區(qū)域控制器（zone controller， ZC）系統(tǒng)是負(fù)責(zé)城軌列車安全運(yùn)行的關(guān)鍵信號設(shè)備之一。在城市軌道交通信號系統(tǒng)的應(yīng)用中，ZC系統(tǒng)根據(jù)列車所匯報的位置信息以及聯(lián)鎖所排列的進(jìn)路和軌旁設(shè)備提供的占用/空閑信息，實(shí)時地為通信列車計算移動授權(quán)，從而確保列車之間的安全追蹤，是基于通信的列車控制（communication based train control，CBTC）系統(tǒng)中列車自動保護(hù)（automatic train protection, ATP）的軌旁部分[1]。ZC系統(tǒng)為全天候連續(xù)工作設(shè)備，工作期間實(shí)時、不間斷地發(fā)送和接收各種數(shù)據(jù)信息并計算存儲，其承擔(dān)的信息量大、數(shù)據(jù)多[2]。在實(shí)際工作中，ZC系統(tǒng)日志最高可產(chǎn)生的數(shù)據(jù)量達(dá)每天10 GB，對存儲和轉(zhuǎn)儲工作帶來較大壓力。此前，針對此類數(shù)據(jù)壓縮處理方法的研究較少，為此，本文提出了一種軟件壓縮算法對其進(jìn)行處理[3]。

1 數(shù)據(jù)壓縮

數(shù)據(jù)壓縮是一個減小數(shù)據(jù)存儲空間的過程，是信息論的最重要成果之一，其利用數(shù)學(xué)工具采用多種方法來管理和處理信息[4]。按照壓縮精度劃分，數(shù)據(jù)壓縮一般有無損壓縮和有損壓縮兩種。在有損壓縮算法中，可以接受一定的損失，用以換取更大的壓縮比。在某些應(yīng)用中，如圖像處理和音頻處理，一定的損失是可以接受的，因?yàn)檫@種損失會受到嚴(yán)格控制，不會影響播放效果。而ZC系統(tǒng)日志數(shù)據(jù)需采用無損壓縮，以保證解壓縮時準(zhǔn)確地還原原始數(shù)據(jù)。無損壓縮數(shù)據(jù)算法，典型的有算術(shù)編碼、RLE算法、LZ算法和Huffman算法。其中算術(shù)編碼運(yùn)算復(fù)雜、速度慢，主要用于圖像處理；LZ系列算法需要構(gòu)建索引字符串字典，字典通常會很大；RLE算法主要是對數(shù)據(jù)塊進(jìn)行壓縮運(yùn)算；而Huffman編碼是通過構(gòu)造Huffman樹來進(jìn)行編碼的，適用于文件處理，特別是對字符數(shù)據(jù)的編碼。ZC日志數(shù)據(jù)具有標(biāo)志位多、狀態(tài)位多及重復(fù)率高[5-6]的特點(diǎn)，故本研究選用針對數(shù)據(jù)文件處理的基于Huffman編碼的無損壓縮算法。

1.1 Huffman編碼

Huffman編碼是基于最小冗余編碼的數(shù)據(jù)壓縮算法。最小冗余編碼指的是，如果能統(tǒng)計出一組數(shù)據(jù)中所有符號的出現(xiàn)頻率，就用一種特定的方法來表示符號，以減少存儲數(shù)據(jù)所需的空間。對出現(xiàn)頻率高的符號，編碼使用盡可能少的位來表示；對出現(xiàn)頻率低的符號，編碼使用盡可能多的位來表示[7]。在數(shù)據(jù)中，所表示的符號不一定要占用一個字節(jié)，經(jīng)過重新編碼，可以是任意大小的數(shù)據(jù)[8]。

1.2 熵和最小冗余

要使用Huffman編碼，需了解熵的概念。熵的作用是量化數(shù)據(jù)信息。信息的概念很抽象，此前人們無法精確指出信息量到底有多少，直到1948年，數(shù)學(xué)家香農(nóng)定義了“信息熵”，信息的量化問題因此得以解決。他首次利用數(shù)學(xué)語言闡明了概率與信息冗余度的關(guān)系：任何數(shù)據(jù)信息都有冗余，冗余的大小與數(shù)據(jù)信息中每個符號出現(xiàn)的概率有關(guān)[9]。

任何數(shù)據(jù)集合的信息量都是一定的，即所謂熵。對于一組數(shù)據(jù)而言，熵就是這組數(shù)據(jù)中每個符號熵的總和。具體而言，熵有如下定義：

式中：PZ——符號z在數(shù)據(jù)集中出現(xiàn)的概率。

如果確切知道z出現(xiàn)了多少次，就知道z出現(xiàn)的頻率[10]。例如，如果一個40個符號的數(shù)據(jù)集合中z出現(xiàn)了10次，即出現(xiàn)的概率為1/4，于是z的熵sz=-lg(1/4)=2位。由此可知，如果在數(shù)據(jù)集中用來表示符號z使用了超過兩位的二進(jìn)制數(shù)，這將是一種浪費(fèi)。目前一般都用一個字節(jié)來表示一個符號，在這種情況下使用合適的數(shù)據(jù)壓縮算法可以很大程度地減小數(shù)據(jù)的容量，即通過重新編碼，可以實(shí)現(xiàn)使用較少的位對出現(xiàn)頻率高的符號編碼，用較多的位對出現(xiàn)頻率低的符號編碼。

2 壓縮算法的實(shí)現(xiàn)

2.1 數(shù)據(jù)壓縮過程解析

數(shù)據(jù)壓縮包括兩個過程：一是壓縮或編碼數(shù)據(jù)，使數(shù)據(jù)容量減??；二是解壓縮或解碼數(shù)據(jù)，使數(shù)據(jù)還原到本身的狀態(tài)[11]。

（1）壓縮部分

壓縮部分采取單輸入單輸出結(jié)構(gòu)，輸入為需要壓縮的數(shù)據(jù)地址，輸出為壓縮后的數(shù)據(jù)地址。壓縮部分按照字節(jié)長度對數(shù)據(jù)進(jìn)行壓縮，壓縮字符數(shù)最大為256個，其按照每包最大1 400個字節(jié)進(jìn)行壓縮，且能持續(xù)壓縮，直至目標(biāo)文件全部執(zhí)行完畢。

（2）解壓縮部分

解壓縮部分采取單輸入單輸出結(jié)構(gòu)，輸入為需要解壓縮的數(shù)據(jù)地址，輸出為解壓縮后的數(shù)據(jù)地址。解壓縮部分按照字節(jié)長度對數(shù)據(jù)進(jìn)行解壓縮，解壓縮字符數(shù)最大為256個，其按照每包最大1 400個字節(jié)進(jìn)行解壓縮，且能持續(xù)解壓縮，直至目標(biāo)文件全部執(zhí)行完畢。

2.2 算法的具體實(shí)現(xiàn)

ZC日志記錄軟件中的Huffman壓縮算法采用分包壓縮和循環(huán)壓縮的方法。將數(shù)據(jù)包按字節(jié)輸入，每包數(shù)據(jù)最大有256個字符；壓縮后重新按字節(jié)組成數(shù)據(jù)包輸出，具體的Huffman數(shù)據(jù)壓縮軟件流程如圖1所示[12-13]。

圖1 Huffman數(shù)據(jù)壓縮軟件流程Fig. 1 Flowchart of Huffman data compression software

解壓縮算法同樣采用分包解壓縮和循環(huán)解壓縮的方法。將需要解壓縮的數(shù)據(jù)包按字節(jié)輸入，組成新的字符串后根據(jù)Huffman編碼解壓縮；解壓縮完成后依然按字節(jié)組成數(shù)據(jù)包輸出[14]。具體的Huffman數(shù)據(jù)解壓縮軟件流程如圖2所示。

圖2 Huffman數(shù)據(jù)解壓縮軟件流程Fig. 2 Flowchart of Huffman data decompression software

ZC日志記錄軟件中的Huffman壓縮算法部分代碼截圖如圖3所示。壓縮過程中，對相關(guān)模塊采用必要的模塊化封裝，以保證該軟件算法的獨(dú)立性。

圖3 部分代碼截圖Fig. 3 Partial code screenshot

3 應(yīng)用結(jié)果及分析

根據(jù)Huffman壓縮算法的特性可知，被壓縮數(shù)據(jù)包內(nèi)字符數(shù)越少，字符重復(fù)率越高，壓縮率越高[15]。軟件編寫完成之后，進(jìn)行了多次調(diào)試與實(shí)驗(yàn)，以驗(yàn)證軟件可用性和實(shí)際的壓縮效果。下面設(shè)定3組實(shí)驗(yàn)進(jìn)行驗(yàn)證。

（1）實(shí)驗(yàn)一

數(shù)據(jù)集中字符的頻率和種類都能對數(shù)據(jù)壓縮效果產(chǎn)生影響。本實(shí)驗(yàn)是為了測試字符頻率的變化對Huffman壓縮算法的影響。首先，設(shè)置一個包含1 400個字節(jié)的數(shù)據(jù)包，設(shè)定其中各字符權(quán)值相等；其次，從2個字符到256個字符依次實(shí)驗(yàn)，將數(shù)據(jù)包壓縮之后再進(jìn)行解壓縮；確認(rèn)壓縮數(shù)據(jù)無誤，將壓縮后數(shù)據(jù)包字節(jié)數(shù)記錄下來并統(tǒng)計壓縮前后數(shù)據(jù)字節(jié)變化。實(shí)驗(yàn)結(jié)果如圖4所示?？梢钥闯?，在各字符權(quán)值相等的情況下，壓縮變比隨著字符數(shù)增多而趨于減小，說明在各字符權(quán)值相同的情況下，Huffman編碼依然能夠?qū)?shù)據(jù)進(jìn)行有效的壓縮。根據(jù)Huffman編碼理論，字符重復(fù)率越高，Huffman編碼壓縮效果越好。

圖4 實(shí)驗(yàn)一壓縮變比圖Fig. 4 Compression transformation diagram of the experiment 1

（2）實(shí)驗(yàn)二

為了測試字符種類的變化對Huffman壓縮算法的影響，設(shè)置一個包含1 400個字節(jié)的數(shù)據(jù)包，其恒定含有256個字符(0x00～0xFF)。設(shè)定每個字符重復(fù)率一樣，進(jìn)行壓縮、解壓縮實(shí)驗(yàn)；然后設(shè)定其重復(fù)率按比例上升，共進(jìn)行5次實(shí)驗(yàn)，分別將數(shù)據(jù)包壓縮之后再進(jìn)行解壓縮；確認(rèn)壓縮數(shù)據(jù)無誤，再次將壓縮后數(shù)據(jù)包字節(jié)數(shù)記錄下來。其壓縮變比如圖5所示?？梢园l(fā)現(xiàn)，隨著數(shù)據(jù)重復(fù)率比例的升高，Huffman算法壓縮后數(shù)據(jù)包越小，壓縮效果越好；而實(shí)際ZC日志記錄數(shù)據(jù)中，按照通信協(xié)議，有大量的重復(fù)數(shù)據(jù)，如0x00/0x01/0xFF/ 0x55/0xAA等，這說明Huffman壓縮算法在本應(yīng)用中壓縮效果是確實(shí)可行的，且數(shù)據(jù)重復(fù)率越高、字符數(shù)越少，壓縮的效果越好。

圖5 實(shí)驗(yàn)二壓縮變比圖Fig. 5 Compression transformation diagram of the experiment 2

（3）實(shí)驗(yàn)三

經(jīng)過多次驗(yàn)證分析之后，按照實(shí)際的ZC日志記錄數(shù)據(jù)來進(jìn)行分析?，F(xiàn)以2019年9月某日長沙地鐵4號線路的ZC日志記錄為例，從中連續(xù)取100組1 400個字節(jié)的數(shù)據(jù)，經(jīng)過Huffman編碼壓縮后，根據(jù)碼表進(jìn)行解壓縮，并驗(yàn)證數(shù)據(jù)無誤。該100組數(shù)據(jù)解壓縮后的效果如圖6所示?？梢钥闯?，每一組1 400個字節(jié)的數(shù)據(jù)經(jīng)過壓縮后的數(shù)據(jù)量在200到600個字節(jié)之間，充分證明了基于Huffman編碼的數(shù)據(jù)壓縮算法對ZC日志記錄數(shù)據(jù)的壓縮是可行的。

圖6 實(shí)驗(yàn)三壓縮變比圖Fig. 6 Compression transformation diagram of the experiment 3

4 結(jié)語

隨著城市軌道交通自動化程度的日益提高，不管是目前普遍運(yùn)行的GOA2等級的線路，還是今后越來越多的GOA3等級或者GOA4級別線路，數(shù)據(jù)交互現(xiàn)象會越來越多，數(shù)據(jù)量會越來越大，數(shù)據(jù)壓縮技術(shù)的研究也勢在必行。本文針對實(shí)際ZC日志的數(shù)據(jù)壓縮問題，提出了一種基于Huffman編碼的數(shù)據(jù)壓縮算法。從實(shí)驗(yàn)結(jié)果來看，其壓縮效果好、效率高。目前該算法已被應(yīng)用于實(shí)際的產(chǎn)品中。

當(dāng)然，信息論領(lǐng)域有很多算法可以充分利用，而Huffman壓縮算法是其中一種。今后將考慮對ZC日志紀(jì)錄進(jìn)行多重壓縮，即在Huffman壓縮算法的基礎(chǔ)上增加其他的壓縮算法，以更大程度地提高壓縮率。另外，軌道交通產(chǎn)品正在向網(wǎng)絡(luò)化、遠(yuǎn)程可視化方向發(fā)展，其數(shù)據(jù)的傳輸受到了網(wǎng)絡(luò)帶寬限制。本文所提供的數(shù)據(jù)壓縮存儲的思路，可以減輕網(wǎng)絡(luò)傳輸?shù)膲毫?，為軌道交通中大?shù)據(jù)的網(wǎng)絡(luò)化應(yīng)用提供參考。