当前位置：首页 > news >正文

LZ4压缩算法详解

news 2026/8/17 10:04:04

一、什么是LZ4？

LZ4是一种无损数据压缩算法，由 Yann Collet 设计。它的目标是极快的压缩/解压速度，同时保持相对合理的压缩率。LZ4 多用于需要实时或高效数据处理的场景，比如数据库日志压缩、网络数据传输、嵌入式设备等。

二、LZ4的基本思想

LZ4 属于LZ77 系列（如 zlib/Deflate）。它的核心思想：

用指针引用已出现过的数据块来代替重复数据，以减少存储空间。

重点是，高速度优先于压缩率，因此LZ4实现中对结构和查找过程做了很多简化。

三、数据格式与编码流程

LZ4的数据分成一个一个block来处理，每个block内部由多个**sequence（序列）**组成。每个sequence一般分为两部分：

一段Literals（原始未压缩数据）
一个Match（对之前数据的引用）

1）Token 字节

每个sequence以一个Token字节开始：

高四位（4bit）：表示Literals的长度（literals length, 0~15）
低四位（4bit）：表示Match的长度（match length, 0~15）

如果长度超过15，则采用“扩展方式”（用额外的字节表示长度，逐字节累加，直到遇到 <255 的字节，如15+255+255+3=528）。

2）Literals 区

紧接在Token之后，如果有literals，则直接写入这些原始数据字节。

3）Match Offset

如果有match，则写入2字节的offset，表示这一块内容在已经解码的数据中的偏移（最多65535字节，LZ4也有支持更大的版本）。

4）Match长度扩展

match的最短长度为4，如果match length在Token低四位大于15用扩展编码（同Literals的方式）。

match长度实际值 = match_length + 4。

例子：

假如Token字节为0x42:

高4位0x4 (4) → 4字节literals
低4位0x2 (2) → 2字节match (实际match长度=2+4=6)

四、查找与滑动窗口

LZ4压缩时会为窗口里的每个位置建立哈希（通常是4字节块映射），以加快查找重复内容的速度。

当扫描时，查找当前数据块在“已读部分缓冲区”是否有完全一致的匹配（通常长度4字节起）。有则编码为match，否则继续输出 literals。

LZ4通常只编码>=4字节的重复，太短的不编码以加快速度。

五、解压流程

解压时只需按顺序处理：

读Token，拆出literals长度和match长度。
复制literals到输出。
如果有match：
- 读2字节offset
- 从已解码的输出缓冲区，按照offset和match长度复制数据到当前输出位置。
重复以上步骤直到数据块结束。

六、优缺点

优点：

极快：极低的CPU消耗和延迟。
简洁：无复杂表构建或后处理。
可流式处理。
易于实现（算法和格式简单）。

缺点：

压缩率一般，通常低于zlib/gzip等。
不能直接利用远距离相同内容，窗口较小。

七、伪代码简要

# 压缩 (伪代码) i = 0 while i < 数据长度: 找到最大重复块 (长度 >= 4) 输出 Token 输出 Literals 数据 输出 Offset 输出 Match长度扩展字节（如需要） i += literals长度 + match长度

八、核心数据结构与工作流程

1. 哈希查找

LZ4采用哈希表进行窗口查找。

窗口大小：通常为64KB（65536字节），因为offset字段是2字节。
哈希函数：取4字节内容，通过一个快速哈希函数定位到表项。这样可以迅速找到是否有重复的内容。

例如（伪代码）：

uint32_t hash = hash32(*(uint32_t*)&input[pos]); int match_pos = hash_table[hash];

2. 序列划分

每次编码遇到重复内容，就输出一个sequence，否则只输出literals。

Literals部分长度不定。
Match部分要求长度至少4字节。

九、Token扩展编码细节

1. Literals长度扩展

如果Literals长度（n）> 15，则
- Token高4位为15
- 后跟若干字节，每字节最大255，累加直到补全n。

while(literal_len > 255) { write(255); literal_len -= 255; } write(literal_len); // 最后一个字节

2. Match长度扩展

同理，Match长度实际是(Token低4位) + 4，如果Match长度 > 19，要扩展：

match_len -= 15; while(match_len > 255) { write(255); match_len -= 255; } write(match_len);

十、性能与实现优化

1. 快速匹配

通过哈希减少全窗口查找时间。LZ4避免了冗长的最长匹配查找，只要求找到第一个匹配即可。

2. 序列化处理

LZ4能高效分批处理大块数据，适合流式处理。每个block可以独立解码。

3. 多核支持

LZ4的无状态设计，方便多线程并行压缩各个block。

4. SIMD加速

现代LZ4实现（如lz4_fast）用SIMD指令加速字节比较和复制，非常快。

十一、变体和扩展

1. LZ4 Frame 格式

LZ4不仅有block级别（lz4_block），还有frame级（lz4_frame），嵌入了

魔术数
压缩属性（block size、checksum etc）
多block处理
校验和

更适合文件或流式存储。

2. 高压缩模式（LZ4_HC）

LZ4_HC采取更复杂的最长匹配查找，压缩率接近zlib，但速度较慢。用法很类似，优先级不同。

十二、常见应用场景

日志压缩
数据库快照
网络传输（RPC/GRPC数据包）
文件/图片快速压缩
游戏与嵌入式设备

十三、实用示例（C代码片段）

// 伪代码简化版 while (pos < input_end) { match_pos = find_match(input, pos); if (match_pos && match_len >= 4) { // 写入Token: [literals_len][match_len] output_token(literals_len, match_len); output_literals(input[pos-literals_len:pos]); output_offset(pos-match_pos); pos += match_len; literals_len = 0; } else { literals_len += 1; pos += 1; } }