LZSS压缩：标志位致比特数非8倍数的处理及编码疑问

一、单个标志位导致的比特非8倍数问题 #

直接在末尾补0确实会让解压器误判，主流解决方式有两种：

• 添加结束标记：用约定的特殊(偏移,长度)对作为EOF信号，比如偏移为0且长度为0。解压器读到这个标记就立即停止解码，后续补位的0直接忽略，不会被当作有效标志位或数据。
• 记录补位长度：在压缩数据末尾（或开头）加1个字节，记录为凑整字节补的0的个数。解压器解码到最后一个字节时，会跳过对应数量的补位比特，避免误处理。

二、标志字节剩余不足8个的处理 #

当最后一组条目不足8个时，标志字节剩余比特补0即可，配合以下方式让解压器识别：

• 前置总条目数：在压缩数据开头用固定长度（比如2字节）记录总条目数（字面量或引用对）。解压器处理完对应数量的条目后，不再处理标志字节的剩余补位0。
• 结合EOF标记：和结束标记方案结合，解压器读到EOF标记时，不管标志字节还有多少剩余比特，直接停止解码。

三、长度超过15的处理方案 #

12比特偏移+4比特长度是基础简化版，实际实现中会通过以下方式扩展长度范围：

• 变长长度编码：当长度>15时，用额外字节存储超出部分。比如4比特长度字段最大值设为15，当该字段为15时，后面跟着1个（或多个）字节存储实际长度的剩余部分。
• 调整比特分配：根据需求重新分配偏移和长度的比特数，比如10比特偏移+6比特长度，长度最大可达63；或8比特偏移+8比特长度，长度上限提升到255。
• 分层标志位：在原有标志位基础上增加子标志位，区分短长度和长长度引用对，比如用0表示短长度（4比特），1表示长长度（8比特），同时调整偏移比特数。

四、LZSS编码理解正确性确认 #

你的核心理解是对的，但有几个细节需要补充修正：

• 标志位定义可变：字面量和引用对的标志位约定可自定义，不同LZSS实现可能反过来（比如用0表示字面量，1表示(偏移,长度)对），具体看实现文档。
• 引用对的编码长度：(偏移,长度)对不一定固定为两个字节，取决于比特分配方案。比如12+4的方案是16比特（2字节），但10+6同样是2字节，变长编码则可能是3字节以上。
• 你的例子验证：以12比特偏移+4比特长度的方案为例，(4,7)的编码是：前置0标志位 + 12比特偏移（000000000100） + 4比特长度（0111），总共1+12+4=17比特，这个计算是正确的。

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