返回资讯中心
外部精选
软件工程
#开发者实时流

LZ0:解码器零内存分配的非对称LZ压缩器

来源标题:Show HN: LZ0 -An asymmetric LZ compressor with ultra minimal, 0-alloc decoder

开发者发布实验性无损压缩格式LZ0,通过把复杂度集中到编码端,实现了一个无需动态内存分配、状态极简的超轻量解码器。该解码器处理显式LZ token的速度可达每秒数百MB,主要面向几百KB到几MB的中小型二进制数据和结构化数据集。其设计定位介于ZX0等复古LZ格式与现代自适应熵编码LZ压缩器之间。

Hacker News 最新seb37732026/11/19 · 今天30 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

一个轻量级、非对称的 LZ 压缩器,围绕一个极其简单、无需内存的解码器设计。

LZ0 是一种实验性的无损压缩格式及 C 实现,围绕一条核心原则设计:

把复杂度从解码器转移到编码器。

LZ0 不追求在压缩与解压之间平均分摊计算成本,而是刻意在编码阶段投入更多精力,生成紧凑、结构化的码流,使解压可以由一个极其精简的例程完成。解码器不需要任何动态内存分配(malloc),维持的状态极少,能以每秒数百 MB 的速度处理显式的 LZ token。

LZ0 主要面向中小型二进制数据块和结构化数据集,典型大小从几百 KB 到几 MB。

压缩算法天生要在压缩率、编码速度、解码速度和实现复杂度之间做多维权衡。

LZ0 完全从解码器的角度来解决这一权衡:

LZ0 占据了一个独特的设计生态位,介于简单的复古 LZ 格式(如 ZX0)与现代自适应熵编码 LZ 压缩器(如 UPKR)之间。

ZX0 树立了极简解码器 LZ 压缩的黄金标准,将逐字节重叠复制的解码器与最优码率的动态规划解析器结合在一起。然而,ZX0 的穷举搜索在超过 1 MiB 的输入上可能要花好几分钟。

LZ0 继承了 ZX0 追求解码器简洁的理念,以及基于 Elias 的变长整数编码,但采用了从根本上更快的编码器架构(结合哈希链、$O(N)$ 的 SA-IS 后缀数组和稀疏动态规划解析器)以及自己的码流语法。因此它能在数秒而非数分钟内得到相当的压缩率。

UPKR 通过把 LZ 匹配与自适应熵编码(rANS / rABS)结合来获得高压缩率。这要求解码器维护概率分布,并对每个 token 执行熵状态更新。

LZ0 刻意避开了自适应熵编码。它的解码器直接处理原始比特和 Elias gamma 整数,用一小部分压缩率换取极大的简洁性和更高的解码吞吐量。

特性 ZX0 LZ0 (H2C8) UPKR 压缩模型 LZ77 / LZSS LZ 风格的显式 token LZ + 自适应熵编码 熵编码 Elias gamma Elias gamma(混合) 自适应 rANS / rABS 编码器复杂度 中等 / 穷举 高(SA-IS + 稀疏 DP) 高 编码速度 非常慢($> 1$ MiB) 快(5 MiB 数秒) 快 解码器复杂度 极简 极简(约 150 行 C) 复杂 解码器 RAM 无(0 字节 malloc) 无(0 字节 malloc) 需要状态/表 码流兼容性 ZX0 独立格式 独立格式 3. 压缩模型与 Token 流 LZ0 解码器解释四种语义操作的序列: 匹配按字节逐个复制(out[out_pos + i] = out[src + i])。由于 src = out_pos - offset,当 length > offset 时,复制会自动重复更早的字节。例如,offset 为 1、length 为 8 时,会把单个字节扩展成 8 字节的连续重复。不得使用标准的非重叠 memcpy。 LZ0 区分原始压缩码流和磁盘容器格式。 存储在磁盘上或由 lz0 CLI 处理的文件,会在原始负载外包裹一个最小的 8 字节头部: +-------------------+-----------------------------+-------------------------+ | Magic (4 bytes) | Uncompressed Size (4 bytes) | Raw Payload (N bytes) | | 'L' 'Z' '0' '1' | uint32 little-endian | Raw LZ0 bitstream | +-------------------+-----------------------------+-------------------------+ 如果 uncompressed_size == 0,负载长度为 0 字节。 原始解码器拒绝空输入;空文件严格在容器层面处理。 4.2 原始码流布局 原始码流没有 magic 字节、头部或长度元数据。其规范见 docs/LZ0_FORMAT.md。 隐含的首个决策位:每个码流都以一个 LiteralRun 开始。开头的决策位 0 被省略。解码器直接开始解码字面量游程的长度。 状态转换: LiteralRun 之后:Bit 0 $\to$ MatchLast。Bit 1 $\to$ 进入 new_loop。 MatchLast 之后:Bit 0 $\to$ 下一个 LiteralRun。Bit 1 $\to$ 进入 new_loop。 在 new_loop 内部: Bit 0 $\to$ EOF(码流结束)。 Bit 1 $\to$ MatchNew(读取 offset 和 length)。 MatchNew 之后:Bit 0 $\to$ 下一个 LiteralRun。Bit 1 $\to$ 继续留在 new_loop。 4.4 Elias Gamma 编码 用于变长整数($v \ge 1$): 合法的 offset 满足 $1 \le \text{offset} \le \text{out_pos}$。 offset 被拆分为一个 MSB 和一个 8 位余数: $$\text{msb} = \lfloor (\text{offset} - 1) / 256 \rfloor + 1 = ((\text{offset} - 1) \gg 8) + 1$$ $$\text{rem} = (\text{offset} - 1) \ & \ 255$$ 使用新 offset 的匹配要求 $L \ge 2$。令 $v = L - 1$: 生产环境的编码器配置是 H2C8(Hash 3 + Chain 8 + SA-IS + 稀疏 DP $K=2$)。它分三个不同阶段处理数据: 输入数据 │ ├──► 1. 哈希链查找器(Hash3,max_chain=8,2 的幂跳步) │ ├──► 2. 后缀数组查找器(SA-IS O(N) + rank 查找,自适应探测 ±4 → ±8 → ±16) │ ├──► 3. 稀疏 DP 解析器(K=2 个活跃状态,Elias 平台剪枝) │ └──► 4. 码流输出器(MSB 优先码流,LSB=8,LEN=3) 5.1 匹配查找 哈希链查找器:快速识别附近的匹配。使用 $2^{17}$ 个条目(128K 桶)的 3 字节哈希表,遍历限制为 8 个候选的历史链,并采用 2 的幂跳步。 SA-IS 后缀数组查找器:以线性 $O(N)$ 时间在整个缓冲区中识别远距离和长匹配。 基于优化的 SA-IS 算法(lz0_sa_algo=1)构建。 与确定性的 $O(N \log^2 N)$ 前缀倍增参考基准(lz0_sa_algo=0)进行比对验证,确保后缀数组逐字节一致。 自适应探测:执行 rank 局部性搜索,从 $\pm 4$ 开始,扩大到 $\pm 8$,仅当当前最佳匹配长度 $< 16$ 时才扩展到 $\pm 16$。 5.2 稀疏 DP 解析器($K=2$)与平台跳步

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →