數據壓縮快速讀寫算法設計

張超

摘要：在當今大數據迅速發展的時代，因為壓縮文件的體積小、易于傳輸等特征，壓縮文件被廣泛使用。但是壓縮文件一旦被壓縮，如果需要修改壓縮文件當中的小部分內容，將會十分耗時。對于大文件進行小部分的修改，傳統方法所消耗的時間是不可接受的。由于傳統方法對于大文件進行小幅修改所消耗的時間主要在壓縮部分，因此，本文提出并實現了一種新的修改方式，在數據流解壓縮的同時，進行匹配和修改，在一次解壓縮的時間下可以將壓縮文件當中的內容修改完成。

關鍵詞：數據壓縮；查詢碼表；解析模塊；替換模塊

中圖分類號：TP393 文獻標識碼：A

文章編號：1009-3044（2019）11-0021-02

1引言

數據壓縮是指通過降低數據冗余并減少存儲的空間，來達到提高數據傳輸效率和減少數據冗余的一種方式。數據壓縮分為無損壓縮和有損壓縮[1]：無損壓縮，如gzip、rar、snappy、lz4等壓縮算法，主要用于壓縮文本；也有有損壓縮，如傅里葉變換等，主要用于音頻、視頻。

數據壓縮總的來說就是一個數據重新編碼的過程，能夠理解為用不同的語言來表達相同的意思。不過一般來說，經過數據壓縮的表達方式總是更加簡練。數據壓縮的目標就是通過數據重新編碼用最簡潔的方式表達數據所蘊含的信息，更準確地說是用最少的空間存儲最多的內容。

2相關研究

現有的方法從尋求新的數據壓縮算法和開發適配壓縮算法的硬件加速器兩方面對數據壓縮進行優化[2，3]。

尋求新的壓縮算法是現在普遍的方式，因此現在也誕生了各種各樣的壓縮算法。新的壓縮算法一般都必須在壓縮率和速度上做取舍，很難達到兩者都最優。并且，新的壓縮算法大多基于已有的算法，或是在匹配過程中應用不同的匹配規則，或是之后使用不同的編碼規則。

開發適配的硬件加速器對于某個特定的壓縮算法可以達到十分優秀的加速效果，但硬件成本較高，數據傳輸需要消耗大量的帶寬，即使速度確實很快，實際中也難以使用。

本文提出的算法思想適用于很多現有的壓縮算法，可在現有的壓縮算法基礎上進行修改得到新的壓縮文件讀寫與更新的技術。

3算法設計

整個算法分為三部分，分別處理不同的內容：接收輸入的待修改字符串和修改后的字符串，根據解壓縮過程中得到的霍夫曼樹，獲取輸入的串對應的二進制碼；解析壓縮文件，并且在解析的過程中進行匹配；替換二進制碼，并將二進制數據流寫入文件當中。

3.1查詢碼表

獲取用戶輸入，輸入包括想要修改的字符串，以及將要把這個字符串修改成什么字符串，并且在輸出的壓縮文件中寫入關于gzip、snappy的magic number。根據解壓縮時維護的數據字典，獲得替換的字符串的二進制碼和被替換的字符串的二進制碼。

由于gzip的碼表是一種特殊的鏈式Huffman樹，因此在碼表當中快速查找也是一個難點。目前的解決方案是，對整個huffman樹進行遞歸查找，沿著這個特殊的鏈逐個查找下去，并且檢驗標志位。當標志位為1時，認為當前節點是有效節點，查找對應的值；而標志位為0時，遞歸查找此節點指向的下一個鏈表，直到找到所需要的所有碼字對應的二進制節點。

記替換的字符串為InString，被替換的字符串為OutString，鏈式huffman樹的頭部為head，查找二進制碼的偽代碼是：

Algorithm 1查找huffman碼表算法

Input： InString， OutString， head

Output： InString code， OutString code

1： for i in {0：len（Instring）} do

2： j=0

3： while head+j≠null

4： if （head+j）→data=InString[i] then

5： mask[i]=j

6： j=j+1

7： end if

8： end while

9： end for

3.2解析數據流

解析模塊，用于解析指定的壓縮文件，獲取壓縮數據流對應的二進制碼。本文希望通過這種新的方法使得對壓縮數據小部分修改的性能有大的提升，但是再字符匹配過程中需要進行大量的匹配，所以對整個性能有相當的損傷。如何將匹配的時間減到最小，選擇合適的匹配算法是一個難點。

解決方法是，采用KMP匹配。由于KMP匹配在匹配過程中不需要進行對被匹配串指針的回溯，因此在匹配效率上是相對較高的，并且也恰當的符合了我們“邊解壓縮邊匹配邊修改”的思想。

對于kmp算法，首先需要獲取OutString的next數組，獲取next數組的偽代碼：

Algorithm 2獲取OutString的next數組算法

Input： OutString array

Output： next array

1： j=0

2： k=-1

3： next[0]=-1

4： while j < len（OutString）-1

5： if k=-1 or OutString[j]=OutString[k]

6： j=j+1

7： k=k+1

8： next[j]=k

9： else

10： k=next[k]

11： end if

12： end while

然后，根據一邊解碼一邊匹配一邊替換的思想，寫出偽代碼，其中str2repnum為當前已經匹配上OutString字符的個數：

Algorithm 3解碼匹配算法

Input： buffer derived from ram， InString， OutString

Output： output String

1： str2replacenum=0

2： while true

3： c=getfrombuffer（buffer）

4： if c is a literal then

5：while OutString[str2repnum]≠c and str2repnum≠-1 /*not match*/

6： if str2repnum=0 then

7： str2repnum=next[str2repnum]

8： end if

9： end while

10： str2repnum=str2repnum+1

11： if str2repnum=len（OutString） then

12： replace（InString，OutString）

13： end if

14： end while

3.3替換寫入存儲介質

替換模塊，用于將二進制形式的待修改字符替換為修改字符的二進制碼，并以二進制流的形式寫入硬盤。這里我4個bit為一組進行輸入的，并且用了循環寫入的方式，b為要寫入的二進制流，以char字符串的類型存儲，inputn為標志位記錄二進制流寫到了那里，length代表本次寫入操作需要寫入的二進位數，偽代碼如下：

Algorithm 4二進制流寫入存儲介質的循環列表算法

Input： binary stream b， mark bit bn， mask array mask， input size inputn

Output： write to outfile

1： bn=0

2： while length+input≥32

3：bn=bn|（（（unsigned）b&mask[32-inputn]）?inputn）

4： fwrite（bn，outfile）

5： length=length-（32-inputn）

6： b=b?（32-inputn）

7： inputn=0

8： bn=0

9： end while

10：bn=bn|（（（unsigned）b&mask[length]）?inputn）

11： inputn=inputn+length

替換字符之后數據流頭部需要根據替換字符代表的bit位數進行確定，并且由于碼表當中存在對應的標志位，標志位也需要進行更改。

在壓縮文件的尾部有CRC校驗碼，所以需要根據文件的內容計算出校驗碼，這也是一個難點。當前的方法是設置一個64K的窗口，和解壓縮過程當中的滑動窗口保持一致的向后滑動。當到文件末尾時，根據CRC32的算法計算最后的校驗值，并刷新原來壓縮文件的校驗值即可。

4總結

本文針對壓縮數據進行小部分修改時更新緩慢的問題，設計了一種對壓縮文件的快速讀寫與更新的新算法。在理論上不增加過多的計算量，也不需要特別大的帶寬，因此在硬件成本上沒有明顯的增加；同時，可以較好地解決了壓縮數據更新緩慢的問題，由于算法在I/O上的優勢，使得其在讀寫性能上也有明顯提升。

參考文獻：

[1] Cleary J，Witten I. Data Compression Using Adaptive Coding and Partial String Matching[J].IEEE Transactions on Communications， 1984， 32（4）：396-402.

[2] Nie H， Rong X， Yu X. Optimization of LIS and LIP Encoding for SPIHT-Based Image Compression[A].Data Compression Conference. IEEE[C]， 2017：453-453.

[3] Mahjoubfar A， Chen C L， Jalali B. Optical Data Compression in Time Stretch Imaging[J]. Plos One， 2015， 10（4）：e0125106.

【通聯編輯：光文玲】