王福源，雷成健，任建新

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

0 引言

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

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

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

1.1 Huffman編碼

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

1.2 熵和最小冗余

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

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

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

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

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

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

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

（1）壓縮部分

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

（2）解壓縮部分

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

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

ZC日志記錄軟件中的Huffman壓縮算法采用分包壓縮和循環(huán)壓縮的方法。將數(shù)據(jù)包按字節(jié)輸入，每包數(shù)據(jù)最大有256個(gè)字符；壓縮后重新按字節(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ò)程中，對(duì)相關(guān)模塊采用必要的模塊化封裝，以保證該軟件算法的獨(dú)立性。

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

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

根據(jù)Huffman壓縮算法的特性可知，被壓縮數(shù)據(jù)包內(nèi)字符數(shù)越少，字符重復(fù)率越高，壓縮率越高[15]。軟件編寫(xiě)完成之后，進(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ù)集中字符的頻率和種類(lèi)都能對(duì)數(shù)據(jù)壓縮效果產(chǎn)生影響。本實(shí)驗(yàn)是為了測(cè)試字符頻率的變化對(duì)Huffman壓縮算法的影響。首先，設(shè)置一個(gè)包含1 400個(gè)字節(jié)的數(shù)據(jù)包，設(shè)定其中各字符權(quán)值相等；其次，從2個(gè)字符到256個(gè)字符依次實(shí)驗(yàn)，將數(shù)據(jù)包壓縮之后再進(jìn)行解壓縮；確認(rèn)壓縮數(shù)據(jù)無(wú)誤，將壓縮后數(shù)據(jù)包字節(jié)數(shù)記錄下來(lái)并統(tǒng)計(jì)壓縮前后數(shù)據(jù)字節(jié)變化。實(shí)驗(yàn)結(jié)果如圖4所示。可以看出，在各字符權(quán)值相等的情況下，壓縮變比隨著字符數(shù)增多而趨于減小，說(shuō)明在各字符權(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)二

為了測(cè)試字符種類(lèi)的變化對(duì)Huffman壓縮算法的影響，設(shè)置一個(gè)包含1 400個(gè)字節(jié)的數(shù)據(jù)包，其恒定含有256個(gè)字符(0x00～0xFF)。設(shè)定每個(gè)字符重復(fù)率一樣，進(jìn)行壓縮、解壓縮實(shí)驗(yàn)；然后設(shè)定其重復(fù)率按比例上升，共進(jìn)行5次實(shí)驗(yàn)，分別將數(shù)據(jù)包壓縮之后再進(jìn)行解壓縮；確認(rèn)壓縮數(shù)據(jù)無(wú)誤，再次將壓縮后數(shù)據(jù)包字節(jié)數(shù)記錄下來(lái)。其壓縮變比如圖5所示?？梢园l(fā)現(xiàn)，隨著數(shù)據(jù)重復(fù)率比例的升高，Huffman算法壓縮后數(shù)據(jù)包越小，壓縮效果越好；而實(shí)際ZC日志記錄數(shù)據(jù)中，按照通信協(xié)議，有大量的重復(fù)數(shù)據(jù)，如0x00/0x01/0xFF/ 0x55/0xAA等，這說(shuō)明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)過(guò)多次驗(yàn)證分析之后，按照實(shí)際的ZC日志記錄數(shù)據(jù)來(lái)進(jìn)行分析?，F(xiàn)以2019年9月某日長(zhǎng)沙地鐵4號(hào)線(xiàn)路的ZC日志記錄為例，從中連續(xù)取100組1 400個(gè)字節(jié)的數(shù)據(jù)，經(jīng)過(guò)Huffman編碼壓縮后，根據(jù)碼表進(jìn)行解壓縮，并驗(yàn)證數(shù)據(jù)無(wú)誤。該100組數(shù)據(jù)解壓縮后的效果如圖6所示?？梢钥闯觯恳唤M1 400個(gè)字節(jié)的數(shù)據(jù)經(jīng)過(guò)壓縮后的數(shù)據(jù)量在200到600個(gè)字節(jié)之間，充分證明了基于Huffman編碼的數(shù)據(jù)壓縮算法對(duì)ZC日志記錄數(shù)據(jù)的壓縮是可行的。

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

4 結(jié)語(yǔ)

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

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