基于Java的大數(shù)據(jù)壓縮研究

宗家冰

遼寧錦州渤海大學(xué)信息科學(xué)與技術(shù)學(xué)院

基于Java的大數(shù)據(jù)壓縮研究

宗家冰

遼寧錦州渤海大學(xué)信息科學(xué)與技術(shù)學(xué)院

本文針對(duì)大數(shù)據(jù)壓縮存儲(chǔ)算法的研究與實(shí)現(xiàn)，隨著數(shù)據(jù)庫(kù)承載的信息量的快速增長(zhǎng)，大數(shù)據(jù)壓縮是一種必然趨勢(shì)，數(shù)據(jù)壓縮包括兩種類(lèi)型：無(wú)損數(shù)據(jù)壓縮和有損數(shù)據(jù)壓縮，在本文中主要介紹使用較為廣泛的無(wú)損數(shù)據(jù)壓縮算法，論文中實(shí)現(xiàn)大數(shù)據(jù)壓縮是按照無(wú)損壓縮技術(shù)的方法，從基于統(tǒng)計(jì)和字典的數(shù)據(jù)壓縮優(yōu)缺點(diǎn)進(jìn)行比較研究，基于Java大數(shù)據(jù)BWT壓縮算法的不足，提出了一種改進(jìn)的NBWT大數(shù)據(jù)壓縮算法。對(duì)大數(shù)據(jù)的三個(gè)構(gòu)成元素：數(shù)據(jù)、時(shí)間標(biāo)簽和壓縮碼采用不同的數(shù)據(jù)編碼策略進(jìn)行壓縮，在數(shù)據(jù)壓縮過(guò)程中，提出了使用矢量方式壓縮數(shù)據(jù)的概念。通過(guò)設(shè)立大數(shù)據(jù)壓縮緩沖池的方法，最后對(duì)本文的改進(jìn)大數(shù)據(jù)壓縮算法進(jìn)行了仿真測(cè)試，測(cè)試結(jié)果表明，一種改進(jìn)大數(shù)據(jù)壓縮算法的壓縮率與壓縮時(shí)間都有所改善。

Java 大數(shù)據(jù) BWT壓縮算法 無(wú)損壓縮

1 引言

目前，隨著大數(shù)據(jù)的發(fā)展，計(jì)算機(jī)用于各行各業(yè)處理信息需求逐漸增多，系統(tǒng)內(nèi)部存儲(chǔ)數(shù)據(jù)量不斷增多，海量數(shù)據(jù)在時(shí)、空上指數(shù)倍增長(zhǎng)，為海量信息存儲(chǔ)帶來(lái)不便，特別是數(shù)據(jù)量巨大、存儲(chǔ)要求較高的系統(tǒng)中需要對(duì)數(shù)據(jù)進(jìn)行加工后才存儲(chǔ)到系統(tǒng)中，必須對(duì)海量數(shù)據(jù)進(jìn)行有效的編碼、壓縮后進(jìn)行存儲(chǔ)，為了能夠解決海量數(shù)據(jù)存儲(chǔ)BTW算法受到程序員的極大關(guān)注。

數(shù)據(jù)的表現(xiàn)形式多種，例如:符號(hào)、文字、字符、音樂(lè)、標(biāo)志、圖片、動(dòng)畫(huà)等多種形式。利用計(jì)算機(jī)來(lái)處理數(shù)據(jù)已經(jīng)面臨的一個(gè)問(wèn)題:海量數(shù)據(jù)的壓縮存儲(chǔ)與數(shù)據(jù)解壓等問(wèn)題。為此我們?cè)噲D采取其他的數(shù)據(jù)表達(dá)方式，目的是減少數(shù)據(jù)總量，這就需要對(duì)海量數(shù)據(jù)進(jìn)行壓縮。

數(shù)據(jù)壓縮算法分為無(wú)損壓縮和有損壓縮兩種數(shù)據(jù)壓縮編碼形式，相對(duì)于有損數(shù)據(jù)壓縮編碼來(lái)說(shuō)，無(wú)損數(shù)據(jù)壓縮編碼的數(shù)據(jù)占用存儲(chǔ)空間較大，數(shù)據(jù)壓縮比并不高，但是，將其還原原始數(shù)據(jù)的同時(shí)，沒(méi)有任何數(shù)據(jù)損壞，隨著無(wú)損壓縮算法逐漸被廣泛應(yīng)用，使得無(wú)損壓縮算法成為各個(gè)系統(tǒng)實(shí)現(xiàn)海量數(shù)據(jù)壓縮存儲(chǔ)的首選工具，由于本文是對(duì)BTW算法的一種改進(jìn)的海量數(shù)據(jù)壓縮存儲(chǔ)的算法，下文將會(huì)詳細(xì)的描述該改進(jìn)算法的主要步驟及其優(yōu)缺點(diǎn)，并對(duì)該改進(jìn)的數(shù)據(jù)壓縮存儲(chǔ)算法進(jìn)行測(cè)試與歸納總結(jié)。

2 數(shù)據(jù)壓縮算法分類(lèi)研究

2.1 數(shù)據(jù)壓縮概念

在計(jì)算機(jī)科學(xué)，數(shù)據(jù)壓縮是按照特定的規(guī)律經(jīng)過(guò)編碼減少的數(shù)據(jù)位數(shù)存儲(chǔ)過(guò)程。數(shù)據(jù)壓縮是指在縮減數(shù)據(jù)量且減少數(shù)據(jù)存儲(chǔ)空間，提高其數(shù)據(jù)存儲(chǔ)空間和數(shù)據(jù)處理效率，或按照一定的算法對(duì)海量數(shù)據(jù)進(jìn)行重新壓縮編碼，減少數(shù)據(jù)的冗余空間和數(shù)據(jù)存儲(chǔ)空間的一種信息編碼技術(shù)。

數(shù)據(jù)壓縮是信息技術(shù)研究中非常重要的分支,在信息技術(shù)中被稱為數(shù)據(jù)編碼。但是近些年來(lái)，數(shù)據(jù)壓縮存儲(chǔ)己不僅是局限于數(shù)據(jù)編碼方法的研究,它已經(jīng)是一種獨(dú)立的研究分支體系,數(shù)據(jù)壓縮算法主要研究數(shù)據(jù)的存儲(chǔ)表示、壓縮編碼和解壓數(shù)據(jù)的方法，目的是減少數(shù)據(jù)在系統(tǒng)占據(jù)的存儲(chǔ)空間。

2.2 大數(shù)據(jù)壓縮分類(lèi)研究

數(shù)據(jù)壓縮包括有損數(shù)據(jù)壓縮存儲(chǔ)和無(wú)損數(shù)據(jù)壓縮存儲(chǔ)。無(wú)損數(shù)據(jù)壓縮存儲(chǔ)技術(shù)通常所說(shuō)的是數(shù)據(jù)壓縮編碼技術(shù)，根據(jù)海量數(shù)據(jù)進(jìn)行壓縮編碼處理以達(dá)到壓縮存儲(chǔ)的過(guò)程，在數(shù)據(jù)壓縮存儲(chǔ)過(guò)程中，被壓縮的數(shù)據(jù)必須經(jīng)過(guò)解碼恢復(fù)原始數(shù)據(jù)，數(shù)據(jù)壓縮分類(lèi)包括：字符、文本文件、數(shù)據(jù)庫(kù)數(shù)據(jù)、程序數(shù)據(jù)、圖像數(shù)據(jù)壓縮過(guò)程，一般為數(shù)據(jù)壓縮存儲(chǔ)是文字或數(shù)字等，而針對(duì)圖像數(shù)據(jù)壓縮、聲音壓縮、視頻圖像壓縮的效率是很低，無(wú)損數(shù)據(jù)壓縮存儲(chǔ)是必然的選擇基于統(tǒng)計(jì)和字典的數(shù)據(jù)壓縮算法，表1為數(shù)據(jù)壓縮存儲(chǔ)的分類(lèi)研究。

表1 數(shù)據(jù)壓縮存儲(chǔ)的分類(lèi)研究

3 一種改進(jìn)的大數(shù)據(jù)壓縮編碼算法

講述本文改進(jìn)的壓縮編碼方法的同時(shí)，先介紹一下關(guān)于詞典方式壓縮編碼，根據(jù)的是大數(shù)據(jù)所本身包含具有重復(fù)性代碼序列的特征。壓縮編碼的常用格式為：zip格式、rar格式、xz格式等等。

在本文中，研究一種改進(jìn)的大數(shù)據(jù)壓縮編碼方式，無(wú)損編碼是大數(shù)據(jù)壓縮編碼的最優(yōu)方式，在實(shí)現(xiàn)大數(shù)據(jù)壓縮編碼的過(guò)程中使得壓縮效率和壓縮比盡可能最快最優(yōu)為最佳。

3.1 一種改進(jìn)的大數(shù)據(jù)壓縮算法的概述

本文改進(jìn)的大數(shù)據(jù)壓縮編碼主要是將壓縮數(shù)據(jù)進(jìn)行字符和整數(shù)進(jìn)行分開(kāi)壓縮編碼，字符壓縮算法使用BWT算法，其應(yīng)用壓縮排序算法對(duì)字符數(shù)據(jù)塊進(jìn)行重組，將原始的數(shù)據(jù)轉(zhuǎn)換成一個(gè)相似的一段數(shù)據(jù)，此過(guò)程并不是進(jìn)行壓縮算法，而是為了提高數(shù)據(jù)壓縮率的輔助工具，在壓縮編碼的過(guò)程中需要存儲(chǔ)一些額外的數(shù)據(jù)用于后續(xù)的解碼操作。BWT算法最重要之處是能夠產(chǎn)生一種轉(zhuǎn)換數(shù)據(jù)比原始數(shù)據(jù)存在更多更長(zhǎng)的連續(xù)編碼數(shù)據(jù)；另一種數(shù)據(jù)壓縮編碼算法主要是針對(duì)整數(shù)進(jìn)行壓縮編碼，較小的整數(shù)用較短的編碼字段，較大的數(shù)據(jù)使用較大的編碼字段表示。假設(shè)有個(gè)整數(shù)x要進(jìn)行整數(shù)壓縮編碼，當(dāng)x的值趨于較小時(shí)，此時(shí)的數(shù)據(jù)壓縮編碼字段較短，可以有效的節(jié)省大數(shù)據(jù)的存儲(chǔ)空間。

3.2 一種改進(jìn)的大數(shù)據(jù)壓縮算法原理

NBWT為改進(jìn)的大數(shù)據(jù)壓縮算法，該算法描述的是給定的待進(jìn)行數(shù)據(jù)壓縮的一段字符，該段字符集合標(biāo)示為X={X1,X2,X3,…,Xn}，使用本文的改進(jìn)的大數(shù)據(jù)壓算法先要判斷給定的大數(shù)據(jù)中是否包含整數(shù)字符，如果包含整數(shù)字符交給Golomb編碼函數(shù)，否則直接交給NBWT編碼函數(shù)，將讀取的數(shù)據(jù)進(jìn)行循環(huán)右移位后旋轉(zhuǎn)，經(jīng)過(guò)一系列的移位旋轉(zhuǎn)獲取到新的數(shù)據(jù)，再將新數(shù)據(jù)按照字典升序進(jìn)行排序操作，BWT壓縮算法對(duì)于由相同符號(hào)開(kāi)頭的大數(shù)據(jù)的壓縮作用非常好。

3.3 一種改進(jìn)的大數(shù)據(jù)壓縮算法實(shí)現(xiàn)步驟

給定的X大數(shù)據(jù)待壓縮編碼序列，其中x表示為整數(shù)編碼部分，Golomb編碼算法的實(shí)現(xiàn)步驟：

①選取一個(gè)參數(shù)m，確定編碼的位數(shù)，b=2^m，m是需要先確認(rèn)的參數(shù)值；

②定義q=[int](x-1)/b，表示一個(gè)取整過(guò)程；

③使用r=x-qb-1，經(jīng)過(guò)式子轉(zhuǎn)化為x=qb+r+1，此種編碼過(guò)程由兩個(gè)部分組成，一是q個(gè)1加上1個(gè)0組成，表示q；另一部分由m個(gè)位組成表示成為r。

接下來(lái)討論針對(duì)上文給定的數(shù)據(jù)序列X，改進(jìn)的NBWT數(shù)據(jù)壓縮編碼算法的實(shí)現(xiàn)步驟為：

①判斷給定的X序列數(shù)據(jù)是否包含整數(shù)，如果包含交給Golomb編碼算法，否則進(jìn)行2；

②將X的序列進(jìn)行循環(huán)右移位，形成一個(gè)新的數(shù)據(jù)數(shù)組X1，X={Xn,Xn-1,Xn-2,…,X1}；

③將X1按照字典的升序進(jìn)行排序；

④計(jì)算X1的長(zhǎng)度，N=size(X1)；

⑤定義i=0（0＜i＜N）,循環(huán)處理X1和X之間的對(duì)應(yīng)關(guān)系，X[N-i-1]=X1[i]；

⑥輸出已經(jīng)編碼的數(shù)據(jù)序列。

實(shí)現(xiàn)大數(shù)據(jù)的解壓算法是根據(jù)大數(shù)據(jù)壓縮算法而實(shí)現(xiàn)的一種可逆算法，這種算法按照壓縮算法的逆過(guò)程進(jìn)行，實(shí)現(xiàn)解壓算法非常簡(jiǎn)單，在這里不再闡述。

4 一種改進(jìn)的大數(shù)據(jù)壓縮算法測(cè)試及其應(yīng)用分析

改進(jìn)的大數(shù)據(jù)壓縮算法性能比較，BWT壓縮編碼算法優(yōu)點(diǎn)是簡(jiǎn)單易懂，但是其缺點(diǎn)是耗費(fèi)更多的內(nèi)存資源，因?yàn)樗紦?jù)更多多字符串存儲(chǔ)循右移的數(shù)組序列。

改進(jìn)的大數(shù)據(jù)壓縮編碼算法應(yīng)用在數(shù)據(jù)庫(kù)需要存儲(chǔ)的大數(shù)據(jù)環(huán)境下，測(cè)試數(shù)據(jù)取于某個(gè)系統(tǒng)內(nèi)的數(shù)據(jù)庫(kù)大數(shù)據(jù)模塊，分別對(duì)給定的大數(shù)據(jù)進(jìn)行壓縮測(cè)試及其分析，包括：壓縮時(shí)間、壓縮比例、解壓時(shí)間、還原質(zhì)量等等。本文給定的大數(shù)據(jù)文件大小為100G，下面從不同的參數(shù)進(jìn)行比較壓縮算法的性能（表2）。

表2 比較不同種壓縮算法的性能

大數(shù)據(jù)壓縮算法測(cè)試及結(jié)果表明，改進(jìn)的NBWT壓縮算法由于其他算法，該算法無(wú)論在壓縮時(shí)間和壓縮比上都具有一定的優(yōu)勢(shì)，提高大數(shù)據(jù)的壓縮比和降低大數(shù)據(jù)的壓縮時(shí)間是改進(jìn)算法的唯一目的。

5 結(jié)論與展望

本文研究的大數(shù)據(jù)壓縮算法，通過(guò)對(duì)BWT算法的改進(jìn)與設(shè)計(jì)，通過(guò)對(duì)NBWT的算法實(shí)現(xiàn)步驟簡(jiǎn)單的描述，最后本文給出本文大數(shù)據(jù)算法的測(cè)試應(yīng)用分析過(guò)程及其及其測(cè)試結(jié)果的性能比較，測(cè)試結(jié)果表明，一種改進(jìn)大數(shù)據(jù)壓縮算法的壓縮率與壓縮時(shí)間都有所改善。

[1]Moghaddam Alborz,Kabir Ehsanollah. Dynamic and memory efficient web page prediction model using LZ78 and LZW algorithms[J]. 14th Information Computer Conference, 2009: 675-680

[2]P.Ferragina,I.Nitto,R .Venturini. On the bitcomplexity of Lempel-Ziv compression[J]. Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009:768-777

[3]R. Grossi, J. S. Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching[J]. SIAM J. Comput. 2005,35(2):378-407

[4]Jacob Ziv. The Universal LZ77 Compression Algorithm Is Essentially Optimal for Individual Finite-Length N-Blocks[J]. IEEE Transactions on Information Theory, 2009,55(5):1941-1944