Java实现LZ77算法后如何存储标签以得到小于原文件的压缩结果

存储后文件更大的核心原因 #

你大概率是给pos、len、next三个字段分配了固定长度的比特位进行存储，比如常见的12位pos+4位len+8位next的组合总长度为24位（3字节）。当数据冗余度低、大量标签为<0,0,原字符>的无匹配场景时，本来只需要1字节存储的单字符，现在需要3字节存储，自然会出现压缩后文件比原文件更大的情况。

优化存储的核心方案 #

• 加入标识位实现可变长字段存储
  给每个标签加1位前缀标识：
  • 标识位为0：代表当前是无匹配标签，仅需存储8位next原字符，总长度9位，比固定长度存储节省15位空间
  • 标识位为1：代表当前是有匹配标签，再按规则存储pos、len、next字段
• 对pos、len字段做二次压缩
  不要用固定长度存储pos和len：
  • 先统计所有输出标签中pos、len的出现频率，生成对应的霍夫曼编码表，出现频率越高的值分配越短的比特编码
  • 将霍夫曼编码表存储在压缩文件的头部，解码时先读取编码表再解析后续的标签比特流
• 冗余字段省略
  当匹配长度等于前向缓冲区大小时，不存在next字符，可以省略该字段的存储，进一步节省空间

Java实现注意事项 #

可以自己实现一个BitOutputStream工具类来处理比特级别的写入操作，避免每次都按整字节写入浪费空间：核心逻辑是维护一个当前缓存字节和已写入比特计数，每凑够8比特就将缓存字节写入文件流，所有标签写完后将剩余不足8位的部分补0对齐后写入。
另外滑动窗口大小建议设置为32KB~64KB，窗口过小会导致匹配率低、无匹配标签占比过高，拉高存储成本。

内容的提问来源于stack exchange，提问作者Mohamed Salah