数据压缩快速读写算法设计
来源:用户上传
作者:
摘要：在当今大数据迅速发展的时代，因为压缩文件的体积小、易于传输等特征，压缩文件被广泛使用。但是压缩文件一旦被压缩，如果需要修改压缩文件当中的小部分内容，将会十分耗时。对于大文件进行小部分的修改，传统方法所消耗的时间是不可接受的。由于傳统方法对于大文件进行小幅修改所消耗的时间主要在压缩部分，因此，本文提出并实现了一种新的修改方式，在数据流解压缩的同时，进行匹配和修改，在一次解压缩的时间下可以将压缩文件当中的内容修改完成。
关键词：数据压缩；查询码表；解析模块；替换模块
中图分类号：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.
【通聯编辑：光文玲】
转载注明来源:https://www.xzbu.com/8/view-14769896.htm
