LZ系列压缩算法编解码速度优化方法转让专利
申请号 : CN202210169115.8
文献号 : CN114244373B
文献日 : 2022-05-20
发明人 : 李唯实 , 谢明 , 魏立峰 , 张铎 , 孙立明 , 刘云
申请人 : 麒麟软件有限公司
摘要 :
权利要求 :
1.一种LZ系列压缩算法编解码速度优化方法,包括对数据编码和数据解码两个过程的优化,其特征在于,在数据编码过程中,
查找重复数据段时,通过一次性读取多个字节的数据切片进行匹配的方式提升重复数据段的匹配速度,具体为:在查找重复数据段时,不再是逐个字节匹配,而是一次性读取长度为计算机字长的数据切片进行匹配,只有数据切片匹配失败时,才对数据切片进行逐个字节匹配,以减少查找重复数据段所需的CPU周期数;
输出未匹配数据时,通过累积未匹配数据并一次性批量输出的方式提升未匹配数据的输出速度,具体为:在输出未匹配数据时,不再是发现未匹配数据就立即输出,而是累积未匹配数据,直至发现下一个重复数据段后,才将累积的未匹配数据批量复制输出,减少复制所需的CPU周期数和额外开销。
2.一种LZ系列压缩算法编解码速度优化方法,包括对数据编码和数据解码两个过程的优化,其特征在于,在数据解码过程中,通过采用直接批量复制和循环批量复制的方式,提升根据历史数据重复复制得到当前数据的速度,具体操作为:在根据历史数据重复复制得到当前数据时,不再是逐个字节复制,而是综合考虑历史数据位置与当前位置的距离以及待复制数据长度,若待复制数据长度小于当前位置跟历史数据位置之间的距离,则直接批量复制;若待复制数据长度大于当前位置跟历史数据位置之间的距离,则采用循环批量复制的方式,历史数据位置保持不变,当前位置随着每次循环而更新,每次循环批量复制的数据长度均等于或小于当前位置跟历史数据位置之间的距离,以减少数据复制时所需的CPU周期数和额外开销。
3.根据权利要求2所述的LZ系列压缩算法编解码速度优化方法,其特征在于,数据解码时的历史数据重复复制得到当前数据,具体方式为:在数据解压过程中,当读取到数据为二元组(distance,length)时,则将按二元组(distance,length)中的信息,通过重复复制历史数据来得到当前数据,二元组(distance,length)中,distance代表历史数据位置与当前位置之间的相对距离,length表示以历史数据位置为起点、需要复制的数据的长度;
若二元组(distance,length)中的distance大于等于length,则直接采用memcpy函数完成数据的批量复制;
若二元组(distance,length)中的distance小于length,将采用循环批量复制的方式:在循环批量复制过程中,历史数据位置保持不变,当前位置随着复制过程不断后移,设d为复制过程中实时计算得到的当前位置和历史数据位置之间的距离,则d的初始值为distance,每次循环均采用memcpy函数复制d个字节长度的数据,并更新当前位置为数据段的尾部,根据新的当前位置重新计算得到d的值,当d的取值大于剩余待复制数据段长度后,结束循环,并采用memcpy函数完成剩余待复制数据段的批量复制。
说明书 :
LZ系列压缩算法编解码速度优化方法
技术领域
背景技术
数据的传输性能,往往需要在数据传输前进行数据压缩,通过有损/无损压缩算法来减少待
传输的数据总量。一般来说,数字、文本、合成图像以及医疗图像等数据往往采用无损压缩,
而自然图像、音频以及视频等数据则往往采用有损压缩。
息找到之前处理过的、与当前输入数据的头部相匹配的数据段,并计算历史数据段与当前
数据段之间数据匹配的长度,当匹配长度大于阈值时,采用(与当前匹配位置的距离,匹配
长度)的二元组来替代当前输入数据,从而达到对输入数据压缩编码的效果。
想,在各自实现上有所不同:如LZMA关注于压缩率的提高,具有最高的压缩比,但编解码时
间最长;LZ4充分利用了cache缓存,采用16k大小、能完全载入L1 cache的哈希表来储存字
典并简化检索,具有最快的编解码速度,但是这种速度的提升是以牺牲部分压缩率为代价
的;LZO则致力于实现压缩速度和压缩率之间的平衡,在确保压缩率的同时尽可能实现快速
压缩解压。
件,Initrd镜像的解压速度对于Linux操作系统启动速度有着重要影响;在虚拟化领域的
spice云桌面协议中,spice需要实时将虚拟机中的桌面发送给客户端进行显示,在发送桌
面时,需要将桌面图像数据通过LZ算法进行数据压缩以便减少带宽压力,压缩算法的编解
码速度也会直接影响客户端的体验效果。若采用LZ4算法进行编解码的话,编解码速度基本
可以得到保证,但数据的压缩率降低也会带来其他方面的问题,因此,有必要在不影响压缩
率的前提下,对LZ系列算法包括LZ4算法的编解码速度进行进一步优化。
括输入缓存模块、输出缓存模块、移位寄存器、回读控制模块、匹配搜索模块、字符长度计算
模块、匹配长度计算模块和输出控制模块。该专利是针对现有无损压缩硬件实现方法的缺
陷,提供一种基于低延时的LZ(Lempel‑Ziv,即Ziv和Lempel算法)无损压缩算法的FPGA实现
系统,是通过硬件实现方式而不是软件方式来加速LZ无损压缩算法的编码速度,需要配置
专门的FPGA芯片,其使用范围受限,与现有系统和软件的集成效果还有待检验。
在传输过程中建立“实时压缩字典”,并与变电站二次在线监测主站映像字典,从而在传输
过程中直接传输字典序列即可。变电站二次在线监测主、子站在通信建立时,先同步“实时
压缩字典”,再进行信息传输,而传输信息时大部分传输的是“实时压缩字典”中的序号,从
而降低所需的网络带宽,提高数据传输效率,保证数据可靠、实时传送。该专利需要预先建
立和同步“实时压缩字典”,适用于专用场景,而不适用于云计算的普遍场景。
最大性能,但该专利需要专用硬件电路的支持,且LZ4压缩算法的压缩率会比其他基于LZ变
体的压缩算法要差一些。
集和霍夫曼树集压缩每一块的方式,可以采用并行方式进行数据压缩,提升了压缩速度,但
也因此可能导致压缩率会比其他基于LZ变体的压缩算法要差一些。同时,该专利在压缩前
需要预先生成初始词典和霍夫曼树,可能导致额外的计算开销。
外的计算开销,增加了压缩时间。
文字的方法和系统,通过对字符的重新MRU/LRU编码排列来对lz编码进行优化。该方法适用
于对文本类型数据的压缩,但并不适用于图像、程序等其他类型数据的压缩。
式变长距离编码的基于Lempel‑Ziv(LZ)的数据压缩。可以减少压缩输出数据中的距离位长
度,以进一步减小数据大小。但这种方式并不会减少压缩时间。
种为LZ数据压缩系统重新排列输入数据流以实现更高数据压缩的技术。它将每个接收到的
数据块与预定数量的先前处理的数据块中的每个进行比较,形成亲和数组,使得亲和数组
中的每个元素包括基于一个或多个匹配位置及其关联的匹配长度的亲和数;然后使用关联
数组重新排列输入数据流中的数据块序列,以形成新的数据流;最后对新数据流进行编码
以实现更高的数据压缩。该专利同样专注于实现更高的压缩率,但比较、重新排列以及重编
码等操作会带来额外的计算开销,需要更长的时间进行压缩操作。
发明内容
的编解码速度,从而减少诸如Linux系统启动和SPICE云桌面等实际应用花费在数据编解码
过程中的系统开销,提升实际应用的性能和执行效率。
算法的压缩率。
和减少读取数据所需的CPU周期数。
配优化成均是一次性读取长度为计算机字长的数据切片进行匹配,匹配失败的情况下,才
会对匹配失败的数据切片进行进一步的逐字节匹配,如此一来,每个CPU周期可以完成多个
字节的数据匹配,大大加快了数据匹配的速度。
配的重复数据段时再采用memcpy函数一次性将累积未匹配数据复制到编码输出缓存区,通
过这种方式,可以充分利用memcpy函数对内存数据复制所做的性能优化,加速未匹配数据
的输出。
(distance,length)中,distance代表历史数据位置与当前位置之间的相对距离,length表
示以历史数据位置为起点、需要复制的数据的长度;
尽可能利用memcpy函数在数据复制效率上的优势,将采用循环批量复制的方式:在循环批
量复制过程中,历史数据位置保持不变,当前位置随着复制过程不断后移;设d为复制过程
中实时计算得到的当前位置和历史数据位置之间的距离,则d的初始值为distance;每次循
环均采用memcpy函数复制d个字节长度的数据,并更新当前位置为数据段的尾部,根据新的
当前位置重新计算得到d的值,当d的取值大于剩余待复制数据段长度后,结束循环,并采用
memcpy函数完成剩余待复制数据段的批量复制。
以可以有效减少编解码时间。
可以有效减少编解码时间,做到了压缩率和编解码的兼顾。
LZ4外的LZ系列压缩算法如LZMA和LZO,本发明可以缩短30%‑50%的编码时间和50%‑60%的解
码时间;对于LZ4算法,本发明也可缩短10%的编码时间和15%的解码时间。
附图说明
具体实施方式
余和存储的空间的一种技术方法。根据压缩过程中是否丢失了信息,数据压缩可以分为无
损压缩和有损压缩两类。
泛用于文本数据,程序和特殊应用场合的图像数据(如指纹图像,医学图像等)的压缩。常用
的无损压缩主要有游程编码、哈夫曼编码、算术编码以及字典编码等类型。
将会很大,并且随着字典的增大,匹配速度也会快速下降。
作为字典,对要压缩的字符串保留一个look‑aheadbuffer(前向缓冲存储器)。压缩后的字
符串采用三元组来表示:<位移,长度,下一个字符>,在滑动窗口中从后往前找,如果在窗口
中有曾经出现过的相同字符,看最多可以匹配多少字节,完了继续往前查找,查找完了取窗
口中最长的匹配串(如果有多个相同长度的串可以匹配,取最后一个),将这个匹配串距当
前位置的位移,长度,及下一个字符构成的三元组写出。如果在滑动窗口找不到匹配串,那
么位移=长度=0,加上不能压缩的字符一起输出。LZ算法最初于1977年由以色列人Jacob
Ziv和Abraham Lempel提出,它可以解决字典匹配中的字典过大的问题,发展至今已经产生
了LZ77、LZ78、LZW、LZO、LZMA、LZSS、LZR、LZB、LZ4等众多变种。这些变种中,有些致力于提升
压缩率,如LZMA;有些致力于快速的压缩解压,如LZ4;也有些致力于平衡压缩率和编解码速
度,如LZO。
始拷贝若干个字节到目标内存地址中,即从源source中拷贝n个字节到目标destin中。如果
source和destin所指的内存区域重叠,那么这个函数并不能够确保source所在重叠区域在
拷贝之前不被覆盖。当前glibc库中的memcpy已经针对各种平台架构进行了优化,可以确保
在x86、arm等平台架构上均能实现内存的快速拷贝。
算法编解码速度的提升,同时不影响算法的压缩率。
入数据起始数据值相同的数据;通过索引,可以找到历史数据在内存中的位置。
并将读取指针跳转到当前数据段的下一个字节。
数据之间的相对距离,length表示历史数据与当前数据的匹配长度,也就是压缩数据段长
度值,并将读取指针跳转到匹配数据段的下一个字节。
开始的、长度为length的数据段复制到解码输出缓存区的当前位置的方式完成压缩数据段
的解压(此处的复制通常是采用逐个字节复制的方式来进行的。采用这种方式的原因在于
当从历史数据位置开始,若有length个字节的数据是重复的情况时,存在历史数据位置与
当前位置之间距离小于length的情况,这种情况下,采用memcpy函数或多个字节复制的方
式,会将当前尚未明确取值的字节也复制到了新的位置,导致解压数据错误)。
未匹配数据并一次性批量输出的方式提升未匹配数据的输出速度。在数据解码过程中,通
过采用直接批量复制和循环批量复制的方式,提升根据历史数据重复复制得到当前数据的
速度。
节匹配,而是每次匹配均是一次性读取多个字节的数据切片进行匹配,一次性读取长度为
计算机字长的数据切片进行匹配,比如一次性读取4个字节(32位计算机)或8个字节(64位
计算机)的数据切片进行匹配,只有在数据切片匹配失败的情况下,才会对匹配失败的数据
切片进行进一步的逐字节匹配,如此一来,每个CPU周期可以完成4个字节(32位计算机)或8
个字节(64位计算机)的数据匹配,大大加快了数据匹配的速度,减少了查找重复数据段所
需的CPU周期数。
配数据就立即输出,而是累积未匹配数据,直到发现下一个匹配的重复数据段时再采用
memcpy函数一次性将累积未匹配数据复制到编码输出缓存区,通过这种方式,可以充分利
用memcpy函数对内存数据复制所做的性能优化,加速未匹配数据的输出,减少复制所需的
CPU周期数和额外开销。
制的方式,提升根据历史数据重复复制得到当前数据的速度,具体操作为:
历史数据位置之间的距离,则直接批量复制;若待复制数据长度大于当前位置跟历史数据
位置之间的距离,则采用循环批量复制的方式,历史数据位置保持不变,当前位置随着每次
循环而更新,每次循环批量复制的数据长度均等于或小于当前位置跟历史数据位置之间的
距离,以减少数据复制时所需的CPU周期数和额外开销。
length)中,distance代表历史数据位置与当前位置之间的相对距离,length表示以历史数
据位置为起点、需要复制的数据的长度;
为了在避免数据错误的同时尽可能利用memcpy函数在数据复制效率上的优势,将采用循环
批量复制的方式:在循环批量复制过程中,历史数据位置保持不变,当前位置随着复制过程
不断后移;设d为复制过程中实时计算得到的当前位置和历史数据位置之间的距离,则d的
初始值为distance;每次循环均采用memcpy函数复制d个字节长度的数据,并更新当前位置
为数据段的尾部,根据新的当前位置重新计算得到d的值,当d的取值大于剩余待复制数据
段长度后,结束循环,并采用memcpy函数完成剩余待复制数据段的批量复制。
距离,是一个变量。也就是循环批量复制时,先从历史数据位置开始采用完成distance个字
节的数据复制,再从历史数据位置开始完成2*distance个字节的复制,逐次增加,直到完成
length个字节的数据复制为止。通过改动,可以加速LZ系列算法解码过程。
以可以有效减少编解码时间。
会对匹配失败的数据切片进行进一步的逐字节匹配;
累积未匹配数据复制到编码输出缓存区。
否则,采用memcpy函数循环复制的方式,在不复制未明确数据的内存区域的前提下,逐次逐
倍增加memcpy函数复制的数据长度,直到整个压缩数据段解压完毕。
图1、图3是优化前,图2、图4是优化后,优化后的最终流程如图2、图4所示。
(64位)/int(32位)类型的数据;
节长度到匹配长度中,结束数据匹配;
置之间的内存数据通过memcpy函数复制到编码输出缓存区,并清空累积未匹配数据段起
点;然后再用(distance,length)二元组作为压缩数据段来替代匹配长度的数据段输出到
编码输出缓存区中;
length之间的关系选择数据复制方式;二元组(distance,length)中,distance代表历史数
据与当前数据之间的相对距离,length表示历史数据与当前数据的匹配长度;
有自主可控性强的特点。
LZO,本发明可以缩短30%‑50%的编码时间和50%‑60%的解码时间;对于LZ4算法,本发明也可
缩短10%的编码时间和15%的解码时间。
数据编解码过程中的系统开销,提升实际应用的性能和执行效率。
于本发明的保护范围。应当指出,对于本技术领域的普通技术人员来说,在不脱离本发明原
理前提下的若干改进和润饰,这些改进和润饰也应视为本发明的保护范围。