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

張超

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）11-0021-02

1引言

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

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

2相關(guān)研究

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

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

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

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

3算法設(shè)計(jì)

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

3.1查詢碼表

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

由于gzip的碼表是一種特殊的鏈?zhǔn)紿uffman樹(shù)，因此在碼表當(dāng)中快速查找也是一個(gè)難點(diǎn)。目前的解決方案是，對(duì)整個(gè)huffman樹(shù)進(jìn)行遞歸查找，沿著這個(gè)特殊的鏈逐個(gè)查找下去，并且檢驗(yàn)標(biāo)志位。當(dāng)標(biāo)志位為1時(shí)，認(rèn)為當(dāng)前節(jié)點(diǎn)是有效節(jié)點(diǎn)，查找對(duì)應(yīng)的值；而標(biāo)志位為0時(shí)，遞歸查找此節(jié)點(diǎn)指向的下一個(gè)鏈表，直到找到所需要的所有碼字對(duì)應(yīng)的二進(jìn)制節(jié)點(diǎn)。

記替換的字符串為InString，被替換的字符串為OutString，鏈?zhǔn)絟uffman樹(shù)的頭部為head，查找二進(jìn)制碼的偽代碼是：

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ù)流對(duì)應(yīng)的二進(jìn)制碼。本文希望通過(guò)這種新的方法使得對(duì)壓縮數(shù)據(jù)小部分修改的性能有大的提升，但是再字符匹配過(guò)程中需要進(jìn)行大量的匹配，所以對(duì)整個(gè)性能有相當(dāng)?shù)膿p傷。如何將匹配的時(shí)間減到最小，選擇合適的匹配算法是一個(gè)難點(diǎn)。

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

對(duì)于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ù)一邊解碼一邊匹配一邊替換的思想，寫(xiě)出偽代碼，其中str2repnum為當(dāng)前已經(jīng)匹配上OutString字符的個(gè)數(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替換寫(xiě)入存儲(chǔ)介質(zhì)

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

Algorithm 4二進(jìn)制流寫(xiě)入存儲(chǔ)介質(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ù)進(jìn)行確定，并且由于碼表當(dāng)中存在對(duì)應(yīng)的標(biāo)志位，標(biāo)志位也需要進(jìn)行更改。

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

4總結(jié)

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

參考文獻(xiàn)：

[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)編輯：光文玲】