一、什么是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; } }十四、压缩/解压原理小结
- 压缩：扫描输入，找重复块，编码为offset和长度，没有则输出原数据。
- 解压：按序读Token，输出原始数据，并复制匹配内容，简单高效。
十五、更多资料
- LZ4源码（C）：https://github.com/lz4/lz4
- LZ4 Frame格式全解：LZ4 Frame format
- 官方技术博客：https://fastcompression.blogspot.com
总结
LZ4是一种简单、快速的压缩算法，适合高吞吐/低延迟场景，核心就是用滑动窗口查找重复串并替换为指针，数据序列用Token+Literals+Match格式编码。
)
