基于Java的大数据压缩研究

宗家冰

辽宁锦州渤海大学信息科学与技术学院

基于Java的大数据压缩研究

宗家冰

辽宁锦州渤海大学信息科学与技术学院

本文针对大数据压缩存储算法的研究与实现，随着数据库承载的信息量的快速增长，大数据压缩是一种必然趋势，数据压缩包括两种类型：无损数据压缩和有损数据压缩，在本文中主要介绍使用较为广泛的无损数据压缩算法，论文中实现大数据压缩是按照无损压缩技术的方法，从基于统计和字典的数据压缩优缺点进行比较研究，基于Java大数据BWT压缩算法的不足，提出了一种改进的NBWT大数据压缩算法。对大数据的三个构成元素：数据、时间标签和压缩码采用不同的数据编码策略进行压缩，在数据压缩过程中，提出了使用矢量方式压缩数据的概念。通过设立大数据压缩缓冲池的方法，最后对本文的改进大数据压缩算法进行了仿真测试，测试结果表明，一种改进大数据压缩算法的压缩率与压缩时间都有所改善。

Java 大数据 BWT压缩算法 无损压缩

1 引言

目前，随着大数据的发展，计算机用于各行各业处理信息需求逐渐增多，系统内部存储数据量不断增多，海量数据在时、空上指数倍增长，为海量信息存储带来不便，特别是数据量巨大、存储要求较高的系统中需要对数据进行加工后才存储到系统中，必须对海量数据进行有效的编码、压缩后进行存储，为了能够解决海量数据存储BTW算法受到程序员的极大关注。

数据的表现形式多种，例如:符号、文字、字符、音乐、标志、图片、动画等多种形式。利用计算机来处理数据已经面临的一个问题:海量数据的压缩存储与数据解压等问题。为此我们试图采取其他的数据表达方式，目的是减少数据总量，这就需要对海量数据进行压缩。

数据压缩算法分为无损压缩和有损压缩两种数据压缩编码形式，相对于有损数据压缩编码来说，无损数据压缩编码的数据占用存储空间较大，数据压缩比并不高，但是，将其还原原始数据的同时，没有任何数据损坏，随着无损压缩算法逐渐被广泛应用，使得无损压缩算法成为各个系统实现海量数据压缩存储的首选工具，由于本文是对BTW算法的一种改进的海量数据压缩存储的算法，下文将会详细的描述该改进算法的主要步骤及其优缺点，并对该改进的数据压缩存储算法进行测试与归纳总结。

2 数据压缩算法分类研究

2.1 数据压缩概念

在计算机科学，数据压缩是按照特定的规律经过编码减少的数据位数存储过程。数据压缩是指在缩减数据量且减少数据存储空间，提高其数据存储空间和数据处理效率，或按照一定的算法对海量数据进行重新压缩编码，减少数据的冗余空间和数据存储空间的一种信息编码技术。

数据压缩是信息技术研究中非常重要的分支,在信息技术中被称为数据编码。但是近些年来，数据压缩存储己不仅是局限于数据编码方法的研究,它已经是一种独立的研究分支体系,数据压缩算法主要研究数据的存储表示、压缩编码和解压数据的方法，目的是减少数据在系统占据的存储空间。

2.2 大数据压缩分类研究

数据压缩包括有损数据压缩存储和无损数据压缩存储。无损数据压缩存储技术通常所说的是数据压缩编码技术，根据海量数据进行压缩编码处理以达到压缩存储的过程，在数据压缩存储过程中，被压缩的数据必须经过解码恢复原始数据，数据压缩分类包括：字符、文本文件、数据库数据、程序数据、图像数据压缩过程，一般为数据压缩存储是文字或数字等，而针对图像数据压缩、声音压缩、视频图像压缩的效率是很低，无损数据压缩存储是必然的选择基于统计和字典的数据压缩算法，表1为数据压缩存储的分类研究。

表1 数据压缩存储的分类研究

3 一种改进的大数据压缩编码算法

讲述本文改进的压缩编码方法的同时，先介绍一下关于词典方式压缩编码，根据的是大数据所本身包含具有重复性代码序列的特征。压缩编码的常用格式为：zip格式、rar格式、xz格式等等。

在本文中，研究一种改进的大数据压缩编码方式，无损编码是大数据压缩编码的最优方式，在实现大数据压缩编码的过程中使得压缩效率和压缩比尽可能最快最优为最佳。

3.1 一种改进的大数据压缩算法的概述

本文改进的大数据压缩编码主要是将压缩数据进行字符和整数进行分开压缩编码，字符压缩算法使用BWT算法，其应用压缩排序算法对字符数据块进行重组，将原始的数据转换成一个相似的一段数据，此过程并不是进行压缩算法，而是为了提高数据压缩率的辅助工具，在压缩编码的过程中需要存储一些额外的数据用于后续的解码操作。BWT算法最重要之处是能够产生一种转换数据比原始数据存在更多更长的连续编码数据；另一种数据压缩编码算法主要是针对整数进行压缩编码，较小的整数用较短的编码字段，较大的数据使用较大的编码字段表示。假设有个整数x要进行整数压缩编码，当x的值趋于较小时，此时的数据压缩编码字段较短，可以有效的节省大数据的存储空间。

3.2 一种改进的大数据压缩算法原理

NBWT为改进的大数据压缩算法，该算法描述的是给定的待进行数据压缩的一段字符，该段字符集合标示为X={X1,X2,X3,…,Xn}，使用本文的改进的大数据压算法先要判断给定的大数据中是否包含整数字符，如果包含整数字符交给Golomb编码函数，否则直接交给NBWT编码函数，将读取的数据进行循环右移位后旋转，经过一系列的移位旋转获取到新的数据，再将新数据按照字典升序进行排序操作，BWT压缩算法对于由相同符号开头的大数据的压缩作用非常好。

3.3 一种改进的大数据压缩算法实现步骤

给定的X大数据待压缩编码序列，其中x表示为整数编码部分，Golomb编码算法的实现步骤：

①选取一个参数m，确定编码的位数，b=2^m，m是需要先确认的参数值；

②定义q=[int](x-1)/b，表示一个取整过程；

③使用r=x-qb-1，经过式子转化为x=qb+r+1，此种编码过程由两个部分组成，一是q个1加上1个0组成，表示q；另一部分由m个位组成表示成为r。

接下来讨论针对上文给定的数据序列X，改进的NBWT数据压缩编码算法的实现步骤为：

①判断给定的X序列数据是否包含整数，如果包含交给Golomb编码算法，否则进行2；

②将X的序列进行循环右移位，形成一个新的数据数组X1，X={Xn,Xn-1,Xn-2,…,X1}；

③将X1按照字典的升序进行排序；

④计算X1的长度，N=size(X1)；

⑤定义i=0（0＜i＜N）,循环处理X1和X之间的对应关系，X[N-i-1]=X1[i]；

⑥输出已经编码的数据序列。

实现大数据的解压算法是根据大数据压缩算法而实现的一种可逆算法，这种算法按照压缩算法的逆过程进行，实现解压算法非常简单，在这里不再阐述。

4 一种改进的大数据压缩算法测试及其应用分析

改进的大数据压缩算法性能比较，BWT压缩编码算法优点是简单易懂，但是其缺点是耗费更多的内存资源，因为它占据更多多字符串存储循右移的数组序列。

改进的大数据压缩编码算法应用在数据库需要存储的大数据环境下，测试数据取于某个系统内的数据库大数据模块，分别对给定的大数据进行压缩测试及其分析，包括：压缩时间、压缩比例、解压时间、还原质量等等。本文给定的大数据文件大小为100G，下面从不同的参数进行比较压缩算法的性能（表2）。

表2 比较不同种压缩算法的性能

大数据压缩算法测试及结果表明，改进的NBWT压缩算法由于其他算法，该算法无论在压缩时间和压缩比上都具有一定的优势，提高大数据的压缩比和降低大数据的压缩时间是改进算法的唯一目的。

5 结论与展望

本文研究的大数据压缩算法，通过对BWT算法的改进与设计，通过对NBWT的算法实现步骤简单的描述，最后本文给出本文大数据算法的测试应用分析过程及其及其测试结果的性能比较，测试结果表明，一种改进大数据压缩算法的压缩率与压缩时间都有所改善。

[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