王江泉++張小研

摘要：嵌入式實(shí)時(shí)操作系統(tǒng)Vxworks本身的數(shù)據(jù)壓縮技術(shù)與其它主流操作系統(tǒng)不能夠相互兼容，本文針對Vxworks提出了一種新的數(shù)據(jù)壓縮技術(shù)，并且詳細(xì)描述了數(shù)據(jù)壓縮技術(shù)算法的數(shù)據(jù)模型及其實(shí)現(xiàn)方法，對研究其他壓縮技術(shù)提供了思路和研究方法。

關(guān)鍵詞：Vxworks；數(shù)據(jù)壓縮技術(shù)；壓縮算法

中圖分類號：TP316 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2017）03-0070-02

1 引言

隨著現(xiàn)代信息技術(shù)的快速進(jìn)步，特別是計(jì)算機(jī)技術(shù)的高速發(fā)展，計(jì)算機(jī)存儲技術(shù)面對諸多困難和挑戰(zhàn)。數(shù)據(jù)壓縮技術(shù)是在保證信息完整性的前提下，通過數(shù)據(jù)量的縮減達(dá)到存儲空間減少的或按照某種算法重新組織原始數(shù)據(jù)，減少數(shù)據(jù)冗余、提高其傳輸存儲和處理效率的一種技術(shù)方法。

Vxworks是美國風(fēng)河公司研制的一種具備發(fā)展能力強(qiáng)、性能極其優(yōu)越及人機(jī)交互友好的嵌入式實(shí)時(shí)操作系統(tǒng)（RTOS），在RTOS領(lǐng)域中起到重要的引導(dǎo)作用，Vxworks以高可靠性、高精度計(jì)時(shí)和優(yōu)良的實(shí)時(shí)性在載人航天、衛(wèi)星通訊、軍事工業(yè)等高精端領(lǐng)域得到廣泛的應(yīng)用及推廣。

Vworks本身自帶的數(shù)據(jù)壓縮技術(shù)只能在Vxworks自身操作系統(tǒng)使用，與其他平臺不能夠相互兼容，存在局限性，而主流平臺的常用壓縮軟件在Vxworks下因平臺屬性不同又不能兼容。本文所描述的數(shù)據(jù)壓縮技術(shù)為無損壓縮，主要用于存儲數(shù)據(jù)庫記錄或處理文本文件，且能夠跨平臺使用，支持Vxworks與其他主流操作系統(tǒng)之間相互應(yīng)用。

2 數(shù)據(jù)壓縮原理

數(shù)據(jù)壓縮技術(shù)作為一種非常重要的的計(jì)算機(jī)技術(shù)[1]，會在很多場景下得到應(yīng)用，比如計(jì)算機(jī)文件系統(tǒng)、數(shù)據(jù)庫的應(yīng)用、大數(shù)據(jù)量信息的傳輸、多媒體移動通信系統(tǒng)等。壓縮可以分為無損壓縮和有損壓縮，有損，指的是壓縮之后就無法完整還原原始信息，但是壓縮率可以很高，主要應(yīng)用于視頻、話音等數(shù)據(jù)的壓縮，因?yàn)閾p失了一點(diǎn)信息，人是很難察覺的；無損壓縮則用于文件或者信息等重要信息必須完整復(fù)原的場合。

數(shù)據(jù)壓縮技術(shù)是以信息論作為基礎(chǔ)理論發(fā)展起來的一種技術(shù)。如果以信息論的觀點(diǎn)看數(shù)據(jù)壓縮技術(shù)，壓縮把信息中冗余的部分信息去除，即去除掉可以確定的信息或者可推算得到的信息，而保留信息中非常不確定的信息，即用一種非?？拷畔⒈举|(zhì)的描述來代替原有信息中的冗余描述，這個(gè)實(shí)質(zhì)的描述就是信息論中的信息量，而整個(gè)過程就是數(shù)據(jù)壓縮技術(shù)。

數(shù)據(jù)壓縮技術(shù)的核心思想就是利用數(shù)據(jù)的重復(fù)結(jié)構(gòu)信息來進(jìn)行數(shù)據(jù)壓縮[2]。舉個(gè)簡單的例子，比如一段字符串“取之以仁義，守之以仁義者，周也。取之以詐力，守之以詐力者，秦也?！?，如果不使用壓縮，采用Unicode編碼共計(jì)32個(gè)字符64個(gè)字節(jié)。如果使用數(shù)據(jù)壓縮，其中字符“取之以”、“仁義”、“，”，、“者”、“守之以”、“也”、“詐力”、“?！本貜?fù)出現(xiàn)過，只需指出其之前出現(xiàn)的位置，便可表示整段字符串。

3 數(shù)據(jù)壓縮算法

本壓縮技術(shù)所采取的的壓縮算法是一種基于字典、“滑動窗口”的無損壓縮模型算法，包含一個(gè)碼表字典、一個(gè)動態(tài)滑動窗口和一個(gè)預(yù)讀緩沖器。

碼表作為壓縮使用的字典，采用最優(yōu)二叉樹進(jìn)行編碼，動態(tài)窗口是個(gè)歷史緩沖器，它被用來存放輸入流前字節(jié)的有關(guān)信息，與動態(tài)窗口相匹配的是預(yù)讀緩沖器，它被用來存儲當(dāng)前輸入流的字節(jié)信息。

數(shù)據(jù)信息首先存儲于預(yù)讀緩沖器，通過之前的滑動窗口與當(dāng)前預(yù)讀緩沖器中的信息進(jìn)行匹配，查找兩者最匹配的數(shù)據(jù)。如果匹配上的數(shù)據(jù)中，數(shù)據(jù)匹配長度大于最小預(yù)定匹配長度，就會輸出一對數(shù)組數(shù)據(jù)，含距離 （distance），長度（length）等信息。其中距離（distance）表示在當(dāng)前的輸入流中重復(fù)的字符在之前滑動窗口中能夠相匹配的字節(jié)數(shù)據(jù)位置，而長度（length）是指能夠匹配的數(shù)據(jù)長度。如果匹配的信息數(shù)據(jù)長度小于最小預(yù)定匹配長度，輸出當(dāng)前字節(jié)，對數(shù)據(jù)信息不做改動。滑動窗口示意圖如圖1所示。

數(shù)據(jù)壓縮算法流程為：

（1）從當(dāng)前需要壓縮的起點(diǎn)位置開始，匹配未進(jìn)行編碼的數(shù)據(jù)，并盡量在當(dāng)前的滑動窗口中查找最長的字符匹配數(shù)據(jù)，如果能夠找到，則執(zhí)行步驟 2 ，否則執(zhí)行步驟 3。

（2）輸出三元參數(shù)數(shù)組（ off，len，c ）。其中 off 為當(dāng)前預(yù)讀緩沖器中匹配的數(shù)據(jù)相對滑動窗口邊界的偏移量，len為兩者所能夠匹配的長度，c 為下一個(gè)即將匹配的字符，即不匹配數(shù)據(jù)的第一個(gè)字符。然后滑動窗口向后移動 len+1 個(gè)字節(jié)，繼續(xù)執(zhí)行步驟 1。

（3）針對不匹配的數(shù)據(jù)，輸出三元參數(shù)數(shù)組（ 0，0，c ）。其中 c 為不能夠匹配字符。然后對滑動窗口進(jìn)行一個(gè)字符的滑動，繼續(xù)執(zhí)行步驟 1。

4 算法實(shí)現(xiàn)

4.1 三元參數(shù)數(shù)組設(shè)計(jì)

針對三元參數(shù)數(shù)組的第一個(gè)參數(shù)——相對滑動窗口的偏移（off），依據(jù)概率理論計(jì)算，匹配數(shù)據(jù)接近滑動窗口尾部的概率要大于接近滑動窗口頭部的概率，所以字符串在滑動窗口的邊界位置比較容易找到相同的匹配串，但對于通常情況下大小固定的的窗口（例如 4096 字節(jié)大小的窗口），偏移值一般情況下為均勻分布，可以通過固定的字節(jié)位數(shù)進(jìn)行描述。編碼 off的位數(shù)計(jì)算為MaxNum = upper_bound（ log2（ MAX_NumCount））。因此，用 12 位字節(jié)數(shù)就可以對大小為 4096的滑動窗口進(jìn)行偏移編碼。在數(shù)據(jù)進(jìn)行壓縮前，滑動窗口字節(jié)數(shù)并沒有達(dá)到 最大值，而是隨著壓縮過程的不斷進(jìn)行而增長， 因此偏移字節(jié)計(jì)算所需要的位數(shù)可以通過窗口的當(dāng)前大小動態(tài)進(jìn)行編碼。

為了盡量對數(shù)據(jù)進(jìn)行壓縮，可以對窗口內(nèi)的偏移（off） 采用可變字長編碼方式，本算法采用哈夫曼編碼（Huffman Coding）對off重新編碼，統(tǒng)計(jì)每個(gè)符號的出現(xiàn)次數(shù)。依據(jù)每種符號所統(tǒng)計(jì)的出現(xiàn)次數(shù)，建立標(biāo)準(zhǔn)的Huffman 樹，獲得每種符號根據(jù)Huffman樹所得到的編碼，形成碼表字典。對于字符出現(xiàn)次數(shù)較多的情況，可以用較少的編碼實(shí)現(xiàn)，對于字符出現(xiàn)次數(shù)很少的，用較多的編碼進(jìn)行實(shí)現(xiàn)。

針對三元參數(shù)數(shù)組的第二個(gè)參數(shù)——所匹配字符串得長度（len），它在一般情況下不會太大，只有在極少數(shù)情況下才會出現(xiàn)較大的長度，因此，應(yīng)該采用一種變長的編碼技術(shù)對長度值進(jìn)行編碼，此編碼還必須為前綴編碼[3]。

本算法中編碼為Golomb 編碼，比如對整數(shù)長度x采用 Golomb 編碼，參數(shù)變量選擇為 p，則：

a = 2p；

j = （（x - 1）/a）；

y = x - ja – 1；

通過計(jì)算可知長度x的編碼由兩部分組成，其中前部分是由 j 個(gè) 1 和 1 個(gè) 0 組成，后半部分為p位的字節(jié)組成，其值等于 y，當(dāng)參數(shù)p 為0、1、2、3時(shí)的 Golomb 編碼表如下：

值 x p = 0 p = 1 p = 2 p = 3

------------------------------------------------------------------------------------------------------------

1 0 0 0 0 00 0 000

2 10 0 1 0 01 0 001

3 110 10 0 0 10 0 010

4 1110 10 1 0 11 0 011

5 11110 110 0 10 00 0 100

6 111110 110 1 10 01 0 101

7 1111110 1110 0 10 10 0 110

8 11111110 1110 1 10 11 0 111

9 111111110 11110 0 110 00 10 000

算法中所采用的Golomb 編碼不僅僅符合前綴編碼的要求，而且數(shù)值比較小的x值可以用較少的位編碼，數(shù)值較大的x值用較長的位編碼。如果x的取值范圍為比較小的數(shù)時(shí)，Golomb 編碼就能夠?qū)臻g進(jìn)行有效的節(jié)省，編碼參數(shù) p 的值，根據(jù)經(jīng)驗(yàn)一般為3或者4。

針對三元參數(shù)數(shù)組的第三個(gè)參數(shù)——不能夠匹配的字節(jié)c，因?yàn)樵撟址母怕蕿殡S機(jī)數(shù)，只能采用標(biāo)準(zhǔn)的8位進(jìn)行編碼，可以直接輸出該字符。

4.2 查找匹配串

本壓縮算法的核心內(nèi)容是在滑動窗口中尋找最長的匹配字節(jié)串，每一次滑動窗口移動之后，都要在滑動窗口中查找下一個(gè)匹配串，如果匹配算法的時(shí)間效率高于O（n2），那么總的算法效率將高達(dá) O（n3），這在實(shí)際應(yīng)用中是無法接受的。

本壓縮算法主要通過在滑動窗口中控制能夠匹配字符串的最大長度（比如24個(gè)字節(jié)）方法，將滑動窗口中每個(gè)24字節(jié)串單獨(dú)抽取出來，按照一定的大小順序形成二叉有序樹，在組織的二叉有序樹中對字符串進(jìn)行匹配，可以有效提高效率。

4.3 數(shù)據(jù)的解壓縮

因?yàn)閿?shù)據(jù)壓縮時(shí)需要做大量的字符匹配工作，而解壓縮時(shí)所需要做很少的工作。因此數(shù)據(jù)解壓縮的整個(gè)過程很簡單，只要對滑動窗口進(jìn)行維護(hù)即可，同時(shí)查詢存儲于壓縮文件的碼表字典，隨著三元數(shù)組的不斷輸入，算法會在滑動窗口中找到滿足要求的匹配串，在輸出流文件中對符合字符串進(jìn)行輸出（如果off和len 數(shù)值都為0，只需要輸出后繼字符c ）。

5 結(jié)語

本文中所論述的數(shù)據(jù)壓縮技術(shù)在嵌入式實(shí)時(shí)操作系統(tǒng)Vxworks和主流操作系統(tǒng)之間能夠相互兼容，使得對Vxworks的應(yīng)用做了進(jìn)一步的擴(kuò)展，且在工程實(shí)踐中得到良好的應(yīng)用。本文詳細(xì)描述了數(shù)據(jù)壓縮技術(shù)算法的數(shù)據(jù)模型及其實(shí)現(xiàn)方法，對研究其他壓縮技術(shù)提供了思路和研究方法。

參考文獻(xiàn)

[1]閆陽，張正炳.淺談數(shù)據(jù)壓縮技術(shù)[J].長江大學(xué)學(xué)報(bào)（自科版），2004，1（4）：120-121.

[2]于翔.數(shù)據(jù)壓縮技術(shù)分析[J].青海大學(xué)學(xué)報(bào)（自然科學(xué)版），2002，20（5）：52-54.

[3]SalomonD.數(shù)據(jù)壓縮原理與應(yīng)用[M].吳樂南，譯.北京：電子工業(yè)出版社，2003.