一種基于嵌入式實時操作系統Vxworks下的數據壓縮技術

王江泉++張小研

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

關鍵詞：Vxworks；數據壓縮技術；壓縮算法

中圖分類號：TP316 文獻標識碼：A 文章編號：1007-9416（2017）03-0070-02

1 引言

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

Vxworks是美國風河公司研制的一種具備發展能力強、性能極其優越及人機交互友好的嵌入式實時操作系統（RTOS），在RTOS領域中起到重要的引導作用，Vxworks以高可靠性、高精度計時和優良的實時性在載人航天、衛星通訊、軍事工業等高精端領域得到廣泛的應用及推廣。

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

2 數據壓縮原理

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

數據壓縮技術是以信息論作為基礎理論發展起來的一種技術。如果以信息論的觀點看數據壓縮技術，壓縮把信息中冗余的部分信息去除，即去除掉可以確定的信息或者可推算得到的信息，而保留信息中非常不確定的信息，即用一種非常靠近信息本質的描述來代替原有信息中的冗余描述，這個實質的描述就是信息論中的信息量，而整個過程就是數據壓縮技術。

數據壓縮技術的核心思想就是利用數據的重復結構信息來進行數據壓縮[2]。舉個簡單的例子，比如一段字符串“取之以仁義，守之以仁義者，周也。取之以詐力，守之以詐力者，秦也。”，如果不使用壓縮，采用Unicode編碼共計32個字符64個字節。如果使用數據壓縮，其中字符“取之以”、“仁義”、“，”，、“者”、“守之以”、“也”、“詐力”、“。”均重復出現過，只需指出其之前出現的位置，便可表示整段字符串。

3 數據壓縮算法

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

碼表作為壓縮使用的字典，采用最優二叉樹進行編碼，動態窗口是個歷史緩沖器，它被用來存放輸入流前字節的有關信息，與動態窗口相匹配的是預讀緩沖器，它被用來存儲當前輸入流的字節信息。

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

數據壓縮算法流程為：

（1）從當前需要壓縮的起點位置開始，匹配未進行編碼的數據，并盡量在當前的滑動窗口中查找最長的字符匹配數據，如果能夠找到，則執行步驟 2 ，否則執行步驟 3。

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

（3）針對不匹配的數據，輸出三元參數數組（ 0，0，c ）。其中 c 為不能夠匹配字符。然后對滑動窗口進行一個字符的滑動，繼續執行步驟 1。

4 算法實現

4.1 三元參數數組設計

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

為了盡量對數據進行壓縮，可以對窗口內的偏移（off） 采用可變字長編碼方式，本算法采用哈夫曼編碼（Huffman Coding）對off重新編碼，統計每個符號的出現次數。依據每種符號所統計的出現次數，建立標準的Huffman 樹，獲得每種符號根據Huffman樹所得到的編碼，形成碼表字典。對于字符出現次數較多的情況，可以用較少的編碼實現，對于字符出現次數很少的，用較多的編碼進行實現。

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

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

a = 2p；

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

y = x - ja – 1；

通過計算可知長度x的編碼由兩部分組成，其中前部分是由 j 個 1 和 1 個 0 組成，后半部分為p位的字節組成，其值等于 y，當參數p 為0、1、2、3時的 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 編碼不僅僅符合前綴編碼的要求，而且數值比較小的x值可以用較少的位編碼，數值較大的x值用較長的位編碼。如果x的取值范圍為比較小的數時，Golomb 編碼就能夠對空間進行有效的節省，編碼參數 p 的值，根據經驗一般為3或者4。

針對三元參數數組的第三個參數——不能夠匹配的字節c，因為該字符的概率為隨機數，只能采用標準的8位進行編碼，可以直接輸出該字符。

4.2 查找匹配串

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

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

4.3 數據的解壓縮

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

5 結語

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

參考文獻

[1]閆陽，張正炳.淺談數據壓縮技術[J].長江大學學報（自科版），2004，1（4）：120-121.

[2]于翔.數據壓縮技術分析[J].青海大學學報（自然科學版），2002，20（5）：52-54.

[3]SalomonD.數據壓縮原理與應用[M].吳樂南，譯.北京：電子工業出版社，2003.