了解更多开源请访问：51CTO开源基础软件社区https://ost.51cto.com【科技DNA】【智能场景】*****************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************场景自动驾驶/AR语音信号流视频GPU渲染科学、云计算内存缩减科学应用医学图像数据库服务器人工智能图像文本传输GAN媒体压缩图像压缩文件同步数据库系统通用数据系统数据读写技术点云压缩稀疏快速傅立叶变换有损视频压缩网格压缩压缩算法框架的动态选择无损压缩分层数据压缩医学图像压缩快速随机存取字符串压缩高吞吐量并行无损压缩增强型只读文件系统开源项目Draco/基于深度学习算法/PCL/OctNetSFFTAV1/H.266编码/H.266解码/VP9MeshOpt/Draco战神LZ4HCompressDICOMBrotliRAISRAIMCSOMGDOpenJPEGrsyncFSSTndzipEROFS简介随着互联网的飞速发展，我们已经进入了“大数据时代”。对于抖音、淘宝等大部分应用来说，庞大的数据量和数据的复杂性无疑会带来很多问题；以淘宝为例，当你打开淘宝APP时，大量的信息会被推送给你，比如文字、图片、视频直播等，会带来巨大的数据开销。如果能尝试压缩这些“数据密集型”应用带来的数据，那么对于手机、电脑等消费类设备，人们就会从昂贵的高端设备转向更便宜的设备。小内存模型。将“数据密集型”应用程序产生的数据“瘦身”并不容易，因为“压缩自古为难”，如果想在不降低性能（压缩速度）的情况下获得高压缩率，很难做到两全其美。但是对于一个应用来说，用户体验应该不会太差，这与内存中的数据压缩有直接关系，因为内存访问的性能会严重影响整个系统的性能。因此，威尔逊等人。提出了WKdm算法，该算法使用从内存数据观察到的规律显示出非常好的压缩速度，但其糟糕的压缩率却成为其成功的“绊脚石”。因此，作者将本文提出的算法与其进行了比较。在这篇论文中，作者提出了一种新的压缩算法，LZ4m；与Wilson提出的WKdm算法一样，通过内存数据中经常观察到的特征，加速LZ4算法输入流的扫描；其次，对于LZ4算法，作者修改了其编码方案，使得压缩后的数据能够以更简洁的形式表达。结果表明，LZ4m的压缩和解压缩速度分别比LZ4算法提高了2.1倍和1.8倍，压缩率的边际损失小于3%。LZ4分析很多压缩延迟低的压缩算法都是基于Lempel-Ziv算法的，但是它们还是有缺点的，因为最长匹配和一些较长的匹配很难减少时间和空间的开销，从而招致高的时间和空间高架。因此，在实践中，我们通常会改变策略来快速识别足够长的子串。LZ4是在Lempel-Ziv算法的基础上发展起来的最成功的压缩算法之一。下面对LZ4的匹配过程进行解释：从算法上看，LZ4主要在其滑动窗口和哈希表。一次扫描输入流4个字节，并检查窗口中的字符串是否以前出现过。为了帮助匹配，LZ4维护一个哈希表并从输入流开始的地方映射4字节字符串。如果哈希表中包含当前滑动窗口中的字符串，则从当前扫描位置继续匹配该字符串。前后两个前缀相同的子串可以匹配到最长的子串，对应的哈希表项??更新到当前的起始扫描位置。滑动窗口继续移动，更新不在哈希表中的子字符串的条目，直到滑动窗口到达末尾。从结构上看，输入流被编码成一个编码单元，一个编码单元（Encodingunit）由两部分组成：头部（Token）和主体（Body）。每个代码单元都以1字节的标头开头。头部的前四位用于指示正??文（Body）字面长度的大小，头部的后四位用于指示匹配长度的大小。如果字符串超过15个字节，即当header字面量长度的4位全为1（1111）时，header字面量长度将减15放在header之后的body中。主体（Body）由文字数据和匹配描述组成，其中匹配描述由向后匹配偏移量和匹配长度组成。正文中的偏移量由2个字节编码，因此LZ4可以回溯至64KB(2^16/1024)以找到匹配项。紧跟在匹配项之后的其他匹配项以类似的方式编码，只是标记中的文字长度字段设置为0000，并且正文省略了文字部分。LZ4m分析由于LZ4是一种通用的压缩算法，并没有针对特定的方面进行专门的优化，其压缩比和解压速度也没有针对某个领域完??全释放。因此，这里我们将利用数据在内存中的特性来修改LZ4。接下来说说内存中的数据。内存中的数据由虚拟内存页面组成，其中包含来自应用程序堆和堆栈的数据。堆和栈包含常量、变量、指针和基本类型的数组，它们通常是结构化的并与系统的字边界对齐。通过笔者的观察，发现以匹配的词粒度扫描数据可以加快数据压缩速度，同时不会明显损失压缩机会??。此外，由于4字节对齐，更大的粒度允许更少的位用于长度和偏移，并且子字符串可以以更紧凑的形式编码。根据以上信息，作者提出了LZ4m算法，使用LZ4来表示内存中的数据。下图是LZ4和LZ4m的区别对比。乍一看，您可能看不出有什么不同。滑动窗口，哈希表，都应该有；但是仔细看会发现LZ4m的header比LZ4多了偏移量（Offset），其他部分（包括header的字面量长度，header的匹配长度，header的字面量偏移量）body)也改变了内存大小。由于4字节对齐，要得到元素在结构体中的偏移量，长度是4字节的倍数，低两位永远为00（如二进制表示的0,4,8,12是0000,0100,1000,1100，最后两位永远为0，我们可以删掉它们以节省空间），这样header的字面量长度（Literallength），匹配长度（Matchlength）和正文（Body）（Token))匹配偏移量（Matchoffset）可以缩短2位。另外，由于LZ4m以4字节粒度压缩4KB页，偏移量最多需要10位，所以偏移量的高2位放在表头（Token）中，其余8位放在表头（Token）中主题。评测将LZ4和LZO1x作为通用算法的代表进行评估，WKdm作为专用算法进行评估。该论文收集的内存数据是通过从主内存中清除的交换数据收集的。压缩比是页面的平均值，压缩比越小，相同数据的压缩体积越小。WKdm压缩比最高，其次是LZ4m、LZ4，最后是LZO1x，速度归一化为LZ4m。与常用算法（即LZ4和LZO1x）相比，LZ4m显示出相当的压缩率，仅降低了3%。LZ4m在压缩和解压缩方面的速度分别比这些算法高2.1倍和1.8倍。LZ4m在压缩比和解压速度上都比WKdm快很多，但代价是压缩速度降低了21%。综上所述，LZ4m在压缩比损失的情况下，大大提高了LZ4的压缩/解压速度。下图显示了页面压缩率的累积分布。LZ4m的压缩比曲线仅次于LZO和LZ4算法，并没有太大的差距。而WKdm显示出清晰的压缩比曲线，远远落后于其他算法。6.8%的页面根本无法使用WKdm压缩，而使用其他页面的这一比例不到1%。这表明WKdm的压缩加速可以被其糟糕的压缩率所抵消。为了进一步比较4字节粒度的匹配偏移量和匹配长度的含义，我们将从跟踪匹配长度开始，如原始LZ4和LZ4m结果所示计算匹配子串的长度并将其与累积匹配计数。放大LZ4和LZ4m匹配长度在0到32之间的原始结果，增加的粒度仅将总长度匹配的发生率降低了2.5%，这意味着4字节粒度方案对找到机会的影响很小一场比赛。长度劣势也可以忽略不计。时间与压缩比的关系，算法的压缩速度可以通过测量每个页面的压缩时间，将具有相同压缩比的页面的时间平均得到。压缩良好压缩页面的时间在算法中是相似的。与LZ4和LZO1x相比，LZ4m显示出出色的压缩速度。由于LZ4m的扫描过程，如果没有找到前缀匹配，扫描窗口将提前4个字节，从而在难以压缩的页面上实现四倍的扫描速度。该算法的解压速度为平均解压速度除以压缩率，其获取方式与平均压缩速度相同。LZ4m在几乎整个压缩比范围内的解压速度都优于其他算法。结论LZ4是目前整体上效率最高的压缩算法，更注重压缩和解压的速度，压缩比不是第一。一种流行的通用压缩算法通过利用内存中数据的固有属性进行了优化。根据资料显示，LZ4m可以大幅提升压缩/解压速度，而压缩率不会有实质损失。LZ4m针对小块大小进行了优化。最大偏移量为270（LZ4中为65535）。LZ4m背后的开发人员计划将这种新的压缩算法用于现实世界的内存压缩系统。但从2017年开始找不到更多代码。了解更多开源信息，请访问：51CTO开源基础软件社区https://ost.51cto.com。
