Quicklz压缩算法

简介: 以前对压缩算法一无所知,只是知道哈弗曼编码能做这种事情,但是感觉这样的方法奇慢无比。昨天下午看了下号称世界上最快的压缩算法Quicklz,对压缩的基本思路有了一定的了解。一般的压缩程序的要求读入文件之后以便压缩一边输出,而不是去先分析整个文件中的情况之后才做决定采取哪种算法。

以前对压缩算法一无所知,只是知道哈弗曼编码能做这种事情,但是感觉这样的方法奇慢无比。昨天下午看了下号称世界上最快的压缩算法Quicklz,对压缩的基本思路有了一定的了解。一般的压缩程序的要求读入文件之后以便压缩一边输出,而不是去先分析整个文件中的情况之后才做决定采取哪种算法。

  Quicklz也不例外也是争取利用文件中重复出现的字节来进行压缩,管理结构如下:

在压缩的过程中不断地读入3个字节,然后根据这3个字节得到一个hash值,根据这个hash值就可以找到offset,这个offset就是上次这个hash值出现的位置,而通过cache可以判断出这次出现的和最近一次出现相同hash值的时候的3个字节是不是相同(可能hash相同而实际的值不同)。

  如果相同的长度在3到18之间,那么这些情况可以用4个位来表示。而大于18小于255的情况则需要8位来表示,刚才用于表示长度的低4为则全部变为0,以区别两种情况。在Level=1的时候就只有这两种情况了。在压缩的过程中用4个字节来记录压缩操作,如果有压缩则为1,否则为0。下面是level=1时候的情况:

  level=1的时候有个很明显的问题是只记录了一个hash相同时候的cache,这样的话只能等到与上次的值相同才能压缩,而与以前的值相同也不行。在level=2和level=3的时候弥补了这个缺陷,但是代价就是压缩的时间变长。在level=2的时候保存了4个offset(相同hash的位置),然后在这四个中取到重复字节长度最长的一个作为压缩选项(这个值保存在最低的2位中),而重复的长度信息保存在接下来的3个位中(如果够的话,不然初始化这3个位为0,在hash值后面的一个字节中保存),其他的地方就和level=1的时候相同了。压缩后文件的格式如下:

  在上面的情况中我们发现如果是3个字节相同的话只能把它压缩成2个字节。而在level=3的时候弥补了这个缺陷,在level=3的时候与前两个的不同之处是最低的两位统一作为标志,记录进行了什么操作,具体的代码如下:

复制代码
if(matchlen == 3 && offset <= 63)
{
*dst = (unsigned char)(offset << 2);
dst++;
}
else if (matchlen == 3 && offset <= 16383)
{
ui32 f = (ui32)((offset << 2) | 1);
fast_write(f, dst, 2);
dst += 2;
}
else if (matchlen <= 18 && offset <= 1023)
{
ui32 f = ((matchlen - 3) << 2) | ((ui32)offset << 6) | 2;
fast_write(f, dst, 2);
dst += 2;
}
else if(matchlen <= 33)
{
ui32 f = ((matchlen - 2) << 2) | ((ui32)offset << 7) | 3;
fast_write(f, dst, 3);
dst += 3;
}
else
{
ui32 f = ((matchlen - 3) << 7) | ((ui32)offset << 15) | 3;
fast_write(f, dst, 4);
dst += 4;
}
复制代码

虽然最后的两种情况的最低两位都是11,但是从下面的格式图中一眼就能看出区别(对应上面的代码看):

  这里知道了文件被压缩后保存的存储格式,下面考虑一下怎么解压。在level=3的时候解压方法还是很好理解的。但是在level=1和level=2的时候怎么解压呢?毕竟压缩文件中只是存储了hash值,而没有指出重复的字节串,甚至连offset都没有给出。这里其实很好理解,因为第一次遇到一个hash的时候当然是不会去压缩它的,那么在解压程序中我们就得到了offset的值,并且随着解压的进行,hash和offset的值与压缩时候的变化是相同的,所有不必保存这些值也能保证正确的解压。

目录
相关文章
|
Linux
Win或Linux系统下用conda安装Open Babel
Win或Linux系统下用conda安装Open Babel
2109 0
Win或Linux系统下用conda安装Open Babel
|
存储 算法
嵌入式系统中的数据压缩技术
嵌入式系统中的数据压缩技术
671 0
|
11月前
|
API
万年历[取当日信息]免费API接口教程
此API提供万年历当天的详细信息,包括农历、星期、宜忌、生肖、星座、节日、五行、星宿等。支持POST和GET请求,需提供用户ID和KEY。返回数据包含阳历、农历、干支、节日列表等多项内容。示例URL:https://cn.apihz.cn/api/time/getday.php?id=88888888&key=88888888。
2951 10
|
11月前
|
人工智能 自动驾驶 芯片
【AI系统】NPU 基础
近年来,AI技术迅猛发展,催生了NPU和TPU等AI专用处理器,这些处理器专为加速深度学习任务设计,相比传统CPU和GPU,展现出更高效率和性能。本文将介绍AI芯片的概念、技术发展、部署方式及应用场景,涵盖从数据中心到边缘设备的广泛领域,探讨其如何成为AI技术落地的关键推手。
1361 4
|
数据安全/隐私保护 图形学
基于 LVGL 使用 SquareLine Studio 快速设计 UI 界面
基于 LVGL 使用 SquareLine Studio 快速设计 UI 界面
705 0
【冷门快捷键】设置VSCode终端大小最小化快捷键Alt+PageUp/PageDown、编辑代码窗口切换大小快捷键Alt+数字键盘“+”、Alt+数字键盘“-”、Alt+数字键盘“0”
【冷门快捷键】设置VSCode终端大小最小化快捷键Alt+PageUp/PageDown、编辑代码窗口切换大小快捷键Alt+数字键盘“+”、Alt+数字键盘“-”、Alt+数字键盘“0”
|
消息中间件 存储 容器
RT-Thread快速入门-消息队列
RT-Thread快速入门-消息队列
409 0
|
算法
几款主流的压缩算法对比Zlib,snappy,lz4
几款主流的压缩算法对比Zlib,snappy,lz4
1373 0
|
Java Spring
Spring在多线程中bean的注入问题
Spring在多线程中bean的注入问题
356 0
|
Shell
Ubuntu的shell之bash和dash
Ubuntu的 shell 默认安装的是 dash,而不是 bash。<br> 运行以下命令查看 sh 的详细信息,确认 shell 对应的程序是哪个:<br> $ls -al /bin/sh<br><br> dash 比 bash 更轻,更快。但 bash 却更常用。<br> 如果一些命令、脚本等总不能正常执行,有可能是 dash 的原因。<br> 比如编译 Android 源
2562 0