王福源，雷成健，任建新

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

0 引言

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

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

數(shù)據(jù)壓縮是一個減小數(shù)據(jù)存儲空間的過程，是信息論的最重要成果之一，其利用數(shù)學工具采用多種方法來管理和處理信息[4]。按照壓縮精度劃分，數(shù)據(jù)壓縮一般有無損壓縮和有損壓縮兩種。在有損壓縮算法中，可以接受一定的損失，用以換取更大的壓縮比。在某些應用中，如圖像處理和音頻處理，一定的損失是可以接受的，因為這種損失會受到嚴格控制，不會影響播放效果。而ZC系統(tǒng)日志數(shù)據(jù)需采用無損壓縮，以保證解壓縮時準確地還原原始數(shù)據(jù)。無損壓縮數(shù)據(jù)算法，典型的有算術編碼、RLE算法、LZ算法和Huffman算法。其中算術編碼運算復雜、速度慢，主要用于圖像處理；LZ系列算法需要構建索引字符串字典，字典通常會很大；RLE算法主要是對數(shù)據(jù)塊進行壓縮運算；而Huffman編碼是通過構造Huffman樹來進行編碼的，適用于文件處理，特別是對字符數(shù)據(jù)的編碼。ZC日志數(shù)據(jù)具有標志位多、狀態(tài)位多及重復率高[5-6]的特點，故本研究選用針對數(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ù)學家香農(nóng)定義了“信息熵”，信息的量化問題因此得以解決。他首次利用數(shù)學語言闡明了概率與信息冗余度的關系：任何數(shù)據(jù)信息都有冗余，冗余的大小與數(shù)據(jù)信息中每個符號出現(xià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使用了超過兩位的二進制數(shù)，這將是一種浪費。目前一般都用一個字節(jié)來表示一個符號，在這種情況下使用合適的數(shù)據(jù)壓縮算法可以很大程度地減小數(shù)據(jù)的容量，即通過重新編碼，可以實現(xiàn)使用較少的位對出現(xiàn)頻率高的符號編碼，用較多的位對出現(xiàn)頻率低的符號編碼。

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

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

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

（1）壓縮部分

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

（2）解壓縮部分

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

2.2 算法的具體實現(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所示。壓縮過程中，對相關模塊采用必要的模塊化封裝，以保證該軟件算法的獨立性。

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

3 應用結果及分析

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

（1）實驗一

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

圖4 實驗一壓縮變比圖Fig. 4 Compression transformation diagram of the experiment 1

（2）實驗二

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

圖5 實驗二壓縮變比圖Fig. 5 Compression transformation diagram of the experiment 2

（3）實驗三

經(jīng)過多次驗證分析之后，按照實際的ZC日志記錄數(shù)據(jù)來進行分析。現(xiàn)以2019年9月某日長沙地鐵4號線路的ZC日志記錄為例，從中連續(xù)取100組1 400個字節(jié)的數(shù)據(jù)，經(jīng)過Huffman編碼壓縮后，根據(jù)碼表進行解壓縮，并驗證數(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 實驗三壓縮變比圖Fig. 6 Compression transformation diagram of the experiment 3

4 結語

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

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