CN104156990A - 一种支持特大型数据窗口的无损压缩编码方法及系统 - Google Patents

Abstract

本发明公开了一种支持特大型数据窗口的无损压缩编码方法，包含以下步骤：字符串匹配编码器对未压缩数据进行字符串匹配，生成包含了单字符编码和控制指令编码的多级长度编码、多级索引编码；分段切割器将多级长度编码、多级索引编码分割成二进制8位或者其他固定长度的编码分段，且从多级长度编码、多级索引编码中提取出编码分类信息；分类统计表对固定长度的编码分段进行动态统计，且根据统计表的数值计算概率预测表；根据概率预测表，熵编码器使用基于概率统计的压缩编码算法，对固定长度编码分段进行压缩编码，输出二进制的已压缩数据。本发明的方法及系统，能够支持GB级以至EB级的特大型数据窗口，并且不会因为索引编码长度变大而降低压缩率。

Description

一种支持特大型数据窗口的无损压缩编码方法及系统

技术领域

本发明涉及数据无损压缩的信息编码技术领域，特别涉及一种支持特大型数据窗口的无损压缩编码方法及系统。

背景技术

随着云计算的迅速发展，数据量正在以惊人的速度增长。作为信息产业的发展趋势，大数据正变得越来越重要。与此同时也出现了问题：如何能够高效地处理这些TB级、PB级甚至更多的大数据？我们需要在网络环境中存储和传输这些大数据，这对存储空间、网络带宽和计算资源都是一种挑战。

数据压缩是节省数据存储和传输成本的一种明智的方法，然而面对大数据，传统的压缩和加密技术显得能力不足。例如软件WinRAR只有一个4MB的小数据窗口，这会限制压缩率，并且其压缩速度并不足够快。

大的数据窗口有可能提高压缩率。但是扩大数据窗口很难，因为索引长度会增长，导致压缩率降低。

无损压缩又称为无失真压缩，是数据压缩技术之中的一类，特点是解压缩时能够把数据一模一样地还原出来。例如WinZip、WinRAR、7-zip等软件采用的就是无损压缩技术。数据压缩技术的另一类称为有损压缩，通常压缩的对象是声音、图片、视频等多媒体数据，其特点是解压缩得到的数据与原始数据有差异，但是给人的感觉差距不明显。例如JPG图片、DVD视频就用到了有损压缩技术。所有的有损压缩编码方法，都需要在压缩系统末端采用一个无损压缩的编码部件来完成压缩，因此本专利对于有损压缩的情况同样适用。

熵编码器是无损压缩技术中的重要部件，其原理是根据字符出现的概率来确定字符编码的长短，概率大的字符采用短编码，概率小的字符采用长编码，从而使输出的数据编码尽可能短，达到数据压缩的效果。熵编码器采用的常见算法有算术编码、区间编码、Huffman编码等，例如WinZip用了Huffman编码，7-zip用了区间编码的算法。本专利对于采用了其他熵编码算法的情况同样适用。

从理论分类的角度看，当前的无损压缩数学模型和方法可以分为如下3种类型：

1)基于概率统计的压缩，例如哈夫曼编码、算术编码等。这一类型中，基于马可夫链模型的PPM(Partial Prediction Match，部分预测匹配)算法具有良好的压缩率。

2)基于字典索引的压缩，例如LZ77/LZSS算法、LZ78/LZW算法等。LZ系列的压缩模型具有速度上的优势。

3)基于符号的顺序和重复情况的压缩，例如游程编码、BWT(Burrows-Wheeler转换)编码等。

当前流行的压缩软件是以上基础压缩理论的复合应用。每种软件通常整合不同的压缩模型和方法来达到更好的效果。下面列举了一些流行压缩软件的特点：

1)软件名称：WinZip

压缩格式：Deflat；

基本算法：LZSS&Huffman编码；

数据窗口大小上限：512KB；

不足之处：数据窗口小；压缩率低；大数据支持能力弱。

2)软件名称：WinRAR

压缩格式：RAR；

基本算法：LZSS&Huffman编码；

数据窗口大小上限：4MB；

不足之处：数据窗口小；压缩率低；大数据支持能力弱。

3)软件名称：Bzip2

压缩格式：BZ2；

基本算法：BWT&Huffman编码；

数据窗口(数据块)大小上限：900KB；

不足之处：BWT数据块小；压缩率低；大数据支持能力弱。

4)软件名称：7-zip

压缩格式：7z；

基本算法：LZSS&算术编码(区间编码与算术编码本质相同)；

数据窗口大小上限：4GB；

不足之处：数据窗口较小；有限的大数据支持能力。

还有其他压缩软件，例如PAQ、WinUDA等。它们可能有较高的压缩率，但速度较慢，不适合大数据压缩。

综上所述，现有的数据无损压缩技术要么速度慢，不适合进行GB级、TB级甚至更多的大数据压缩，要么数据窗口较小，导致压缩率偏低。但是直接增大数据窗口并不能有效提高压缩率，因为大的数据窗口需要用更长的索引，而索引长度的增加会降低压缩率，得不偿失，除非能找到有效的压缩编码方法和压缩格式。

发明内容

本发明的目的在于克服现有技术的缺点与不足，提供一种支持特大型数据窗口的无损压缩编码方法。

本发明的另一目的在于提供一种支持特大型数据窗口的无损压缩编码系统。

本发明的目的通过以下的技术方案实现：

一种支持特大型数据窗口的无损压缩编码方法，包含以下顺序的步骤：

S1.字符串匹配编码器对未压缩数据进行字符串匹配，生成包含了单字符编码和控制指令编码的多级长度编码、多级索引编码；

S2.分段切割器将多级长度编码、多级索引编码分割成二进制8位或者其他固定长度的编码分段，提供给分类统计表和熵编码器；同时，从多级长度编码、多级索引编码中提取出编码分类信息，提供给分类统计表；

S3.根据编码分类信息，分类统计表首先将固定长度的编码分段放到不同的统计表中进行动态统计，然后根据统计表的数值，向熵编码器提供概率预测表；

S4.根据概率预测表，熵编码器使用基于概率统计的压缩编码算法，对固定长度编码分段进行压缩编码，输出二进制的已压缩数据。

步骤S1中，所述的多级长度编码，根据待编码的字符串长度来分级，并遵循特定的长度编码格式。

所述的根据带编码的字符串长度来分级，具体包括：采用至少3级的长度编码，同一级别的编码长度相同；较低级别的长度编码，比较高级别的长度编码短；较短的字符串采用较低级别的长度编码，较长的字符串采用较高级别的长度编码，具体的级别划分与特定的长度编码格式相关；

所述的多级长度编码格式，具体包括：L0长度编码，代表单个字符；L1长度编码，代表字符串长度2至11；L2长度编码，代表字符串长度12至75；可选的L3长度编码，代表字符串长度76至325；可选的L4长度编码，包括L4线性长度编码和L4指数长度编码，能够支持最大16EB的字符串长度，并且遵循特定的线性长度编码与指数长度编码相结合的格式。

步骤S1中，所述的多级索引编码，根据待编码的字符串与匹配字符串的距离来分级，并遵循特定的索引编码格式。

所述的根据待编码的字符串与匹配字符串的距离来分级，具体包括：采用至少3级的索引编码，同一级别的编码长度相同；较低级别的索引编码，比较高级别的索引编码短；索引值等于待编码的字符串与匹配字符串的距离值；较小的索引值采用较低级别的索引编码，较大的索引值采用较高级别的索引编码，具体的级别划分与特定的索引编码格式相关；

所述的多级索引编码格式，具体包括：L1索引编码，代表索引值X1至X1+Y1-1，其中X1＝1，Y1等于2的8次方；L2索引编码，代表索引值X2至X2+Y2-1，其中X2＝X1+Y1，Y2等于2的16次方；L3索引编码，代表索引值X3至X3+Y3-1，其中X3＝X2+Y2，Y3等于2的24次方；可选的L4索引编码，代表索引值X4至X4+Y4-1，其中X4＝X3+Y3，Y4等于2的32次方；可选的L5索引编码，代表索引值X5至X5+Y5-1，其中X5＝X4+Y4，Y5等于2的40次方；可选的L6索引编码，代表索引值X6至X6+Y6-1，其中X6＝X5+Y5，Y6等于2的48次方；可选的L7索引编码，代表索引值X7至X7+Y7-1，其中X7＝X6+Y6，Y7等于2的56次方；可选的L8索引编码，代表索引值X8至X8+Y8-1，其中X8＝X7+Y7，Y8等于2的64次方；L1、L2、L3、L4、L5、L6、L7、L8索引编码能够支持的数据窗口大小依次为256B、64KB、16MB、4GB、1TB、256TB、64PB、16EB。

步骤S2中，所述的分类统计表中的分类为一种以上级别的编码。

步骤S3中，所述的统计表按照0阶、1阶或2阶PPM概率统计模型来设计。

步骤S4中，所述的基于概率统计的压缩编码算法为算术编码、区间编码或Huffman编码中的一种。

本发明的另一目的通过以下的技术方案来实现：

一种支持特大型数据窗口的无损压缩编码系统，包括顺序相连的字符串匹配编码器、分段切割器、分类统计表、熵编码器，其中

字符串匹配编码器，用于对未压缩数据进行字符串匹配，生成包含了单字符编码和控制指令编码的多级长度编码、多级索引编码，提供给分段切割器；

分段切割器，用于把多级长度编码、多级索引编码分割成二进制8位或者其他固定长度的编码分段，提供给分类统计表和熵编码器，与此同时，从多级长度编码、多级索引编码中提取出编码分类信息，提供给分类统计表，一个分类可以是一种级别的编码，也可以是一种以上级别的编码；

分类统计表，用于根据编码分类信息，把固定长度的编码分段放到不同的统计表中进行动态统计，所用的各个统计表可以是按照0阶、1阶或2阶PPM概率统计模型来设计，与此同时，根据统计表的数值，向熵编码器提供概率预测表；

熵编码器，用于根据概率预测表，使用算术编码、区间编码、Huffman编码或其他基于概率统计的压缩编码算法，对固定长度编码分段进行压缩编码，输出二进制的已压缩数据。

本发明与现有技术相比，具有如下优点和有益效果：

本发明的方法，索引编码能够支持特大型的数据窗口，可达到PB、EB级，远远大于当前常见压缩软件WinRAR和7-zip的MB、GB级数据窗口，并且不会因为数据窗口的增大、索引长度的增加而降低压缩率；能够同时支持线性长度编码和指数长度编码，可以编码长达16EB的字符串长度；以上索引、长度的编码优势，使本发明在压缩GB、TB级或以上的海量数据时，能够获得高于当前常见压缩软件的压缩率。

附图说明

图1为本发明所述的一种支持大型数据窗口的无损压缩编码方法的流程图；

图2为本发明所述的一种支持大型数据窗口的无损压缩编码系统的结构示意图；

图3为图2所述系统的字符串匹配编码器输出的多级长度编码、多级引索编码格式示意图。

具体实施方式

下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方式不限于此。

一种支持特大型数据窗口的无损压缩编码方法，包含以下顺序的步骤：

S1.字符串匹配编码器对未压缩数据进行字符串匹配，生成包含了单字符编码和控制指令编码的多级长度编码、多级索引编码；

所述的多级长度编码，根据待编码的字符串长度来分级，并遵循特定的长度编码格式。

所述的根据带编码的字符串长度来分级，具体包括：采用至少3级的长度编码，同一级别的编码长度相同；较低级别的长度编码，比较高级别的长度编码短；较短的字符串采用较低级别的长度编码，较长的字符串采用较高级别的长度编码，具体的级别划分与特定的长度编码格式相关。

所述的多级长度编码格式，具体包括：L0长度编码，代表单个字符；L1长度编码，代表字符串长度2至11；L2长度编码，代表字符串长度12至75；可选的L3长度编码，代表字符串长度76至325；可选的L4长度编码，包括L4线性长度编码和L4指数长度编码，能够支持最大16EB的字符串长度，并且遵循特定的线性长度编码与指数长度编码相结合的格式；

步骤S1中，所述的多级索引编码，根据待编码的字符串与匹配字符串的距离来分级，并遵循特定的索引编码格式。

所述的根据待编码的字符串与匹配字符串的距离来分级，具体包括：采用至少3级的索引编码，同一级别的编码长度相同；较低级别的索引编码，比较高级别的索引编码短；索引值等于待编码的字符串与匹配字符串的距离值；较小的索引值采用较低级别的索引编码，较大的索引值采用较高级别的索引编码，具体的级别划分与特定的索引编码格式相关。

所述的多级索引编码格式，具体包括：L1索引编码，代表索引值X1至X1+Y1-1，其中X1＝1，Y1等于2的8次方；L2索引编码，代表索引值X2至X2+Y2-1，其中X2＝X1+Y1，Y2等于2的16次方；L3索引编码，代表索引值X3至X3+Y3-1，其中X3＝X2+Y2，Y3等于2的24次方；可选的L4索引编码，代表索引值X4至X4+Y4-1，其中X4＝X3+Y3，Y4等于2的32次方；可选的L5索引编码，代表索引值X5至X5+Y5-1，其中X5＝X4+Y4，Y5等于2的40次方；可选的L6索引编码，代表索引值X6至X6+Y6-1，其中X6＝X5+Y5，Y6等于2的48次方；可选的L7索引编码，代表索引值X7至X7+Y7-1，其中X7＝X6+Y6，Y7等于2的56次方；可选的L8索引编码，代表索引值X8至X8+Y8-1，其中X8＝X7+Y7，Y8等于2的64次方；L1、L2、L3、L4、L5、L6、L7、L8索引编码能够支持的数据窗口大小依次为256B、64KB、16MB、4GB、1TB、256TB、64PB、16EB；

S2.分段切割器将多级长度编码、多级索引编码分割成二进制8位或者其他固定长度的编码分段，提供给分类统计表和熵编码器；同时，从多级长度编码、多级索引编码中提取出编码分类信息，提供给分类统计表；

所述的分类统计表中的分类为一种以上级别的编码；

S3.根据编码分类信息，分类统计表首先将固定长度的编码分段放到不同的统计表中进行动态统计，然后根据统计表的数值，向熵编码器提供概率预测表；

所述的统计表按照0阶、1阶或2阶PPM概率统计模型来设计；

S4.根据概率预测表，熵编码器使用基于概率统计的压缩编码算法，对固定长度编码分段进行压缩编码，输出二进制的已压缩数据；

所述的基于概率统计的压缩编码算法为算术编码、区间编码或Huffman编码中的一种。

下面对该方法，做更进一步地介绍：

如图1所示，一种支持特大型数据窗口的无损压缩编码方法，包含以下顺序的步骤：

S301：初始化索引分段统计表tabI[i]，其中i从1至8，共有8组索引分段统计表；

S302：初始化长度分段统计表tabL[i]，其中i从0至4，共有5组长度分段统计表；

S303：判断是否已经没有尚未压缩的数据，是则流程结束，否则继续步骤S304；

S304：判断是否进行特别功能，是则转步骤S305，否则转步骤S306；

S305：设置变量C为控制类，I为控制指令代码，L为控制操作数，转步骤S311；

S306：读取新的未压缩数据；

S307：在数据窗口中进行字符串匹配；

S308：判断字符串匹配是否成功，是则转步骤S309，否则转步骤S310；

S309：设置变量C为字典类，I为匹配的索引值，L为匹配的字符串长度值，转步骤S311；

S310：设置变量C为单字符类，I为字符ASCII码，转步骤S311；

S311：把C代表的三类代码整合成统一编码，根据I作分级索引编码，根据L作分级长度编码；

S312：设置变量Idx为分级索引编码，S1为索引级别，Len为分级长度编码，S2为长度级别；

S313：对索引编码Idx进行分段切割，成为固定长度的编码分段Idx1，Idx2，Idx3等，编码分段的个数取决于索引编码Idx的位数；

S314：对索引编码Len进行分段切割，成为固定长度的编码分段Len1，Len2，Len3等，编码分段的个数取决于长度编码Len的位数；

S315：采用0阶、1阶或2阶PPM概率统计表tabL[S2]对编码分段Len1，Len2，Len3等进行熵编码；

S316：采用0阶、1阶或2阶PPM概率统计表tabI[S1]对编码分段Idx1，Idx2，Idx3等进行熵编码；

S317：把熵编码得到的已压缩数据输出；

S318：根据编码分段Idx1，Idx2，Idx3等，更新统计表tabI[S1]，根据编码分段Len1，Len2，Len3等，更新统计表tabL[S2]，并跳转到步骤S303。

如图2，一种支持特大型数据窗口的无损压缩编码系统，包括顺序相连的字符串匹配编码器、分段切割器、分类统计表、熵编码器，其中

字符串匹配编码器101，用于对未压缩数据进行字符串匹配，生成包含了单字符编码和控制指令编码的多级长度编码、多级索引编码，提供给分段切割器102；

分段切割器102，用于把多级长度编码、多级索引编码分割成二进制8位或者其他固定长度的编码分段，提供给分类统计表103和熵编码器104，与此同时，从多级长度编码、多级索引编码中提取出编码分类信息，提供给分类统计表103，一个分类可以是一种级别的编码，也可以是一种以上级别的编码；

分类统计表103，用于根据编码分类信息，把固定长度的编码分段放到不同的统计表中进行动态统计，所用的各个统计表可以是按照0阶、1阶或2阶PPM概率统计模型来设计，与此同时，根据统计表的数值，向熵编码器104提供概率预测表；

熵编码器104，用于根据概率预测表，使用算术编码、区间编码、Huffman编码或其他基于概率统计的压缩编码算法，对固定长度编码分段进行压缩编码，输出二进制的已压缩数据。

如图3，字符串匹配编码器输出的多级长度编码、多级索引编码格式包括：

对于每一段未压缩数据进行字符串匹配编码，得到的结果是一个分级长度编码，后面紧跟着一个分级索引编码，其中分级长度编码格式来自长度编码分离201，分级索引编码格式来自索引编码分离212；

长度编码分离201：根据不同情况，对单个字符可编码为L0长度编码202，对长度2至11可编码为L1长度编码203，对长度12至75可编码为L2长度编码204，其他情况的编码则来自L3长度分离205；

L3长度分离205：根据不同情况，对控制字可编码为控制指令编码210，对长度76至325可编码为L3线性长度编码206，对长度326及以上的情况，编码则来自L4长度分离207；

L4长度分离207：根据不同情况，对长度326至65535可编码为L4线性长度编码208，对长度2的16次方至2的64次方可编码为L4指数长度编码209；

控制指令编码210：后面紧跟着控制操作数编码211；

索引编码分离212：根据不同情况，对匹配位置在256字节的数据窗口1范围内可编码为L1索引编码213，对匹配位置在64KB的数据窗口2范围内可编码为L2索引编码214，对匹配位置在16MB的数据窗口3范围内可编码为L3索引编码215，对匹配位置在4GB的数据窗口4范围内可编码为L4索引编码216，对匹配位置在1TB的数据窗口5范围内可编码为L5索引编码217，对匹配位置在256TB的数据窗口6范围内可编码为L6索引编码218，对匹配位置在64PB的数据窗口7范围内可编码为L7索引编码219，对匹配位置在16EB的数据窗口8范围内可编码为L8索引编码220。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。

Claims (9)

1.一种支持特大型数据窗口的无损压缩编码方法，其特征在于，包含以下顺序的步骤：

S1.字符串匹配编码器对未压缩数据进行字符串匹配，生成包含了单字符编码和控制指令编码的多级长度编码、多级索引编码；

S2.分段切割器将多级长度编码、多级索引编码分割成二进制8位或者其他固定长度的编码分段，提供给分类统计表和熵编码器；同时，从多级长度编码、多级索引编码中提取出编码分类信息，提供给分类统计表；

S3.根据编码分类信息，分类统计表首先将固定长度的编码分段放到不同的统计表中进行动态统计，然后根据统计表的数值，向熵编码器提供概率预测表；

S4.根据概率预测表，熵编码器使用基于概率统计的压缩编码算法，对固定长度编码分段进行压缩编码，输出二进制的已压缩数据。

2.根据权利要求1所述的支持特大型数据窗口的无损压缩编码方法，其特征在于：步骤S1中，所述的多级长度编码，根据待编码的字符串长度来分级，并遵循特定的长度编码格式。

3.根据权利要求2所述的支持特大型数据窗口的无损压缩编码方法，其特征在于，所述的根据带编码的字符串长度来分级，具体包括：采用至少3级的长度编码，同一级别的编码长度相同；较低级别的长度编码，比较高级别的长度编码短；较短的字符串采用较低级别的长度编码，较长的字符串采用较高级别的长度编码，具体的级别划分与特定的长度编码格式相关；

所述的多级长度编码格式，具体包括：L0长度编码，代表单个字符；L1长度编码，代表字符串长度2至11；L2长度编码，代表字符串长度12至75；可选的L3长度编码，代表字符串长度76至325；可选的L4长度编码，包括L4线性长度编码和L4指数长度编码，能够支持最大16EB的字符串长度，并且遵循特定的线性长度编码与指数长度编码相结合的格式。

4.根据权利要求1所述的支持特大型数据窗口的无损压缩编码方法，其特征在于：步骤S1中，所述的多级索引编码，根据待编码的字符串与匹配字符串的距离来分级，并遵循特定的索引编码格式。

5.根据权利要求4所述的支持特大型数据窗口的无损压缩编码方法，其特征在于，所述的根据待编码的字符串与匹配字符串的距离来分级，具体包括：采用至少3级的索引编码，同一级别的编码长度相同；较低级别的索引编码，比较高级别的索引编码短；索引值等于待编码的字符串与匹配字符串的距离值；较小的索引值采用较低级别的索引编码，较大的索引值采用较高级别的索引编码，具体的级别划分与特定的索引编码格式相关；

所述的多级索引编码格式，具体包括：L1索引编码，代表索引值X1至X1+Y1-1，其中X1＝1，Y1等于2的8次方；L2索引编码，代表索引值X2至X2+Y2-1，其中X2＝X1+Y1，Y2等于2的16次方；L3索引编码，代表索引值X3至X3+Y3-1，其中X3＝X2+Y2，Y3等于2的24次方；可选的L4索引编码，代表索引值X4至X4+Y4-1，其中X4＝X3+Y3，Y4等于2的32次方；可选的L5索引编码，代表索引值X5至X5+Y5-1，其中X5＝X4+Y4，Y5等于2的40次方；可选的L6索引编码，代表索引值X6至X6+Y6-1，其中X6＝X5+Y5，Y6等于2的48次方；可选的L7索引编码，代表索引值X7至X7+Y7-1，其中X7＝X6+Y6，Y7等于2的56次方；可选的L8索引编码，代表索引值X8至X8+Y8-1，其中X8＝X7+Y7，Y8等于2的64次方；L1、L2、L3、L4、L5、L6、L7、L8索引编码能够支持的数据窗口大小依次为256B、64KB、16MB、4GB、1TB、256TB、64PB、16EB。

6.根据权利要求1所述的支持特大型数据窗口的无损压缩编码方法，其特征在于：步骤S2中，所述的分类统计表中的分类为一种以上级别的编码。

7.根据权利要求1所述的支持特大型数据窗口的无损压缩编码方法，其特征在于：步骤S3中，所述的统计表按照0阶、1阶或2阶PPM概率统计模型来设计。

8.根据权利要求1所述的支持特大型数据窗口的无损压缩编码方法，其特征在于：步骤S4中，所述的基于概率统计的压缩编码算法为算术编码、区间编码或Huffman编码中的一种。

9.一种支持特大型数据窗口的无损压缩编码系统，其特征在于：包括顺序相连的字符串匹配编码器、分段切割器、分类统计表、熵编码器，其中

字符串匹配编码器，用于对未压缩数据进行字符串匹配，生成包含了单字符编码和控制指令编码的多级长度编码、多级索引编码，提供给分段切割器；

分段切割器，用于把多级长度编码、多级索引编码分割成二进制8位或者其他固定长度的编码分段，提供给分类统计表和熵编码器，与此同时，从多级长度编码、多级索引编码中提取出编码分类信息，提供给分类统计表，一个分类可以是一种级别的编码，也可以是一种以上级别的编码；

分类统计表，用于根据编码分类信息，把固定长度的编码分段放到不同的统计表中进行动态统计，所用的各个统计表可以是按照0阶、1阶或2阶PPM概率统计模型来设计，与此同时，根据统计表的数值，向熵编码器提供概率预测表；

熵编码器，用于根据概率预测表，使用算术编码、区间编码、Huffman编码或其他基于概率统计的压缩编码算法，对固定长度编码分段进行压缩编码，输出二进制的已压缩数据。