數(shù)據(jù)壓縮快速讀寫算法設計

張超

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

關(guān)鍵詞：數(shù)據(jù)壓縮；查詢碼表；解析模塊；替換模塊

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

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

1引言

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

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

2相關(guān)研究

現(xiàn)有的方法從尋求新的數(shù)據(jù)壓縮算法和開發(fā)適配壓縮算法的硬件加速器兩方面對數(shù)據(jù)壓縮進行優(yōu)化[2，3]。

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

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

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

3算法設計

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

3.1查詢碼表

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

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

記替換的字符串為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解析數(shù)據(jù)流

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

解決方法是，采用KMP匹配。由于KMP匹配在匹配過程中不需要進行對被匹配串指針的回溯，因此在匹配效率上是相對較高的，并且也恰當?shù)姆狭宋覀儭斑吔鈮嚎s邊匹配邊修改”的思想。

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

Algorithm 2獲取OutString的next數(shù)組算法

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

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

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替換寫入存儲介質(zhì)

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

Algorithm 4二進制流寫入存儲介質(zhì)的循環(huán)列表算法

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

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

在壓縮文件的尾部有CRC校驗碼，所以需要根據(jù)文件的內(nèi)容計算出校驗碼，這也是一個難點。當前的方法是設置一個64K的窗口，和解壓縮過程當中的滑動窗口保持一致的向后滑動。當?shù)轿募┪矔r，根據(jù)CRC32的算法計算最后的校驗值，并刷新原來壓縮文件的校驗值即可。

4總結(jié)

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

參考文獻：

[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.

【通聯(lián)編輯：光文玲】