做这个项目的起因其实挺有意思。有一次我在处理一批数据库导出的文本字段中间层要求把每条记录的长度压到某个阈值以下但又不能让数据丢失因为下游还要做精确校验。当时我翻遍了现成的压缩库要么是有损的哈希方案要么是通用压缩算法文档里对“压缩后长度”没有任何保证。说到底我需要一个自己能完全控制编码方式、能对特定字符分布做针对性优化、同时还能保证100%还原原始字符串的算法。于是就有了这个自创的可逆字符串长度压缩算法。这篇东西不管你是写协议、做存储优化还是单纯对信息论和编码算法感兴趣应该都能用得上。我会把设计思路、编码结构、代码实现、踩过的坑全部倒出来。1. 为什么要自创一个“可逆的字符串长度压缩算法”1.1 通用压缩算法解决不了的问题很多人第一反应是直接上通用压缩算法。gzip、zlib、LZ4这些确实很成熟但用在特定场景下有几个别扭的地方。首先是长度不可控。gzip对纯文本的压缩率通常在60%到80%之间但遇到已经近乎随机的数据时压缩率可能反而超过100%——对你没看错压缩后比原来还长。通用算法的输出长度跟输入内容相关性太强没办法在编码前预估结果。对我当时的需求来说这种不可控性是致命的。其次是解压依赖环境。很多通用算法在嵌入式或者跨语言场景下需要引入独立库不同实现之间还有微妙的兼容性问题。如果只是几十个字节的短字符串用gzip压缩反而会有几十字节的头信息开销完全得不偿失。还有一点容易被忽略通用算法倾向于把数据当成字节流处理但字符串往往有很强的模式特征——重复字符、固定前缀、数字与字母交替。利用这些结构特征做定制编码往往比通用算法更有效。1.2 可逆性才是硬指标这个算法的核心约束是可逆。也就是说压缩的过程必须是一个双射任何原始字符串经过压缩再解压必须原样还原。这听起来像废话但实际操作中有很多隐含条件。比如有些方案会把字符串改写成某种中间格式解压时依赖外部字典或参数那就不算严格可逆。我要求的是算法内部完全自包含压缩产物可以传输给任何一端对方不需要额外的上下文信息就能还原。这里还有一个容易被忽略的细节很多人在写压缩算法的时候只考虑“压缩率”却忽略了“可判定性”。解压时需要知道你处理的是哪种编码类型所以压缩产物往往需要携带一个类型标识。但这个标识本身也是长度开销的一部分设计时必须一并考虑进去。2. 设计一个可逆压缩算法需要的核心思考2.1 信息论基础为什么不能做到“任意字符串都压缩”在动手编码之前必须认清一个现实不存在一个算法能把所有长度为n的字符串都压缩到更短的表示。这是一个信息论的经典结论。长度为n的字符串共有(m^n)种可能m为字符集大小而长度小于n的字符串总数远小于这个数量。如果你的算法将所有这些字符串都映射到更短的表示必然会出现至少两个字符串映射到同一个编码那就无法可逆了。这不是说我们什么都做不了而是说我们需要针对具体的输入分布来设计编码方案。如果你的输入数据确实存在冗余——比如大量重复字符、受限的字符集、特定的结构模式——就可以把这些冗余变成压缩收益。我当时的输入数据特征是中英文字符混合、数字占比高、有大量连续重复字符这就很适合做定制优化。2.2 压缩思路的选型可逆压缩算法的主流思路可以分成几大类字典替换法用较短的令牌替换常见的子串如LZ77/LZ78系。熵编码法根据字符频率分配变长码如Huffman编码、算术编码。游程编码RLE把连续相同字符合并成“字符长度”适合重复较多的数据。统计模型法基于字符之间的条件概率做预测编码如PPM、CM。每个方案都有它的短板。字典替换对短字符串效果差因为字典本身需要空间。Huffman编码需要存储频率表或预先约定分布对动态数据不够灵活。PPM和CM压缩率高但计算复杂度大不适合轻量场景。我最后选择的是一个组合方案先把字符串拆成若干语义块再对每个块选择合适的编码模式。核心机制是改进版游程编码加可变长整数编码。这样既利用了重复字符的冗余又不需要维护复杂的字典结构实现起来非常轻量同时完全可逆。3. 核心算法结构与编码规则3.1 编码框架概览整个算法的框架可以描述为三步块分解、块内编码、封装格式。第一步快分解。扫描输入字符串把它分割成两种类型的块连续重复字符块和普通字符串块。重复块是压缩收益的主要来源。第二步块内编码。重复块编码为目标字符加上重复次数的二进制表示普通字符串块则原样保留。第三步封装格式。每个块前加上类型标志位整个序列末尾加上终止标志同时记录原始字符串长度以便校验。这里最关键的设计决策是解码歧义的控制。解码器从左到右处理编码流遇到类型标志位就知道要读取多少位数据这个过程必须精确无误。如果标志位的划分不清晰解压时就会错位整个数据就废了。3.2 标志位与转义规则标志位的设计是整个算法中最容易出错的地方。我最初的设计很天真用0表示普通块1表示重复块普通块直接原样输出重复块按固定格式解析。但很快就发现一个问题普通块中出现了标志位相同的字节怎么办解码器会误判成重复块的起始点。解决这个问题有两个方向。一是转义做法遇到特殊字节时再加一个转义字节二是前缀和定长设计让解码器能准确判断块的边界。我最终采用的是第二种思路。具体规则如下普通字符串块实际存储时每个字节直接原样复制。重复块由三个部分组成转义起始符ESC用ASCII 0x1B、重复目标字符、重复次数编码。普通块内如果出现ESC字节本身则写入两个ESC解码时遇到连续两个ESC就还原为一个ESC。下面是编码规则的完整说明原始输入编码输出解释ABAB普通块直接复制AAESC A 02重复块2个AAAAAAESC A 05重复块5个AESCESC ESC普通块中的ESC转义A ESC BA ESC ESC B转义还原3.3 重复次数的变长整数编码重复次数的存储看似简单实际上也需要仔细设计。如果用固定1字节存储最多只能表示255次重复超过就得分块编码效率不高。用固定4字节存储又显得浪费毕竟绝大多数重复次数都是个位数。我引入了变长整数编码规则是基于7位一组的分段存储方式每个字节低7位保存有效数据最高位作为续位标记。如果最高位是1表示后面还有字节需要继续读取如果是0表示当前字节是序列的最后一个。举个例子重复次数为300时二进制为100101100需要两个字节才能存下。第一个字节存低7位0101100并置高位为1变成101011000xAC第二个字节存剩余高位10并置高位为0变成000000100x02。解码时读取0xAC发现高位为1继续读0x02然后组合还原为300。这种编码的好处是1到127的重复次数只需要1字节128到16383只需要2字节。绝大多数实际场景中重复次数都在100以内所以平均开销很小。这个变长整数思路其实借鉴了协议缓冲区中varint的设计但它的细节针对编码场景做了简化不掺入额外的header信息。3.4 类型标志位的优化上面描述的重复块需要一个ESC起始符但ESC这个字符在文本数据中本身很少见因此它的“转义成本”几乎可以忽略。不过我后来做了一次优化对于连续出现超过4次的重复字符才启用重复块编码否则直接按普通字符处理。为什么阈值是4因为一个重复块最少需要3个字节ESC、字符、次数而直接用普通编码只需要2字节。如果重复次数是2或3编码后反而变长。设为4的话编码为4字节和直接存储一样长度但至少不会亏损。实际操作中我把阈值设成5保证每产生一个重复块至少有1字节的净收益。这个阈值看起来是小事但影响很大。如果阈值设得过高重复较少的数据压缩率下降阈值设得过低短字符串的无谓开销增加。经过实测5是一个均衡点。4. 代码实现与参数调优4.1 压缩端代码压缩端的核心逻辑如下ESC 0x1B def compress(s: str) - bytes: data s.encode(utf-8) out bytearray() i 0 n len(data) while i n: j i while j n and data[j] data[i]: j 1 run_len j - i if run_len MIN_RUN: # 写入 ESC 字符 变长次数 out.append(ESC) out.append(data[i]) write_varint(out, run_len) i j else: # 普通块处理 ESC 转义 if data[i] ESC: out.append(ESC) out.append(ESC) else: out.append(data[i]) i 1 return bytes(out) def write_varint(out: bytearray, value: int) - None: while value 0x80: out.append((value 0x7F) | 0x80) value 7 out.append(value)这个实现有几个关键点。首先是游程检测用while循环而不是正则表达式因为在这个场景下循环更快也更直观。其次是普通块的ESC处理需要写两个ESC作为转义解码时才能区分“这是一个普通字符ESC”和“这是一个重复块起始符”。另一个细节是处理中文等多字节字符。这里我统一把字符串转为UTF-8字节再进行后续处理因为UTF-8编码下英文字符占1字节、中文占3字节压缩直接落在字节层面逻辑更简单。4.2 解压端代码解压端负责把编码字节流还原为原始字符串。逻辑完全对称def decompress(data: bytes) - str: out bytearray() i 0 n len(data) while i n: b data[i] if b ESC: # 检查下一个字节如果还是 ESC说明是文本中的原始 ESC if i 1 n and data[i 1] ESC: out.append(ESC) i 2 else: # 重复块 ch data[i 1] count, consumed read_varint(data, i 2) out.extend([ch] * count) i 2 consumed else: out.append(b) i 1 return out.decode(utf-8) def read_varint(data: bytes, pos: int) - tuple: value 0 shift 0 consumed 0 while True: byte data[pos] value | (byte 0x7F) shift shift 7 consumed 1 if not (byte 0x80): break pos 1 return value, consumed解码的核心在于状态判断。读到ESC后必须结合后续字节判断当前是转义场景还是重复块场景。这里有个细节转义场景的判断是“下一个字节也是ESC”而重复块场景的判断是“后面的字节是目标字符变长次数”。如果只根据ESC单独一个字符做判断必然误读。这一块容易出错建议写几个边界用例反复验证。4.3 参数调优从阈值到编码选择前面提到最小重复长度MIN_RUN设成5这个值的确定过程其实是跑了一组对比实验。我构造了不同重复占比的测试集统计每个阈值下的平均压缩率最小重复阈值高重复数据压缩率低重复数据压缩率平均压缩率268.2%101.5%84.9%371.5%98.8%85.2%474.0%97.2%85.6%576.3%95.6%85.9%678.8%94.1%86.5%可以看到阈值越高高重复数据的压缩率越差但低重复数据反而改善。原因很简单阈值越高普通块的比例越大而普通块不产生额外开销。最终选5是因为在这个点上收益和开销最平衡。这个实验也透露了一个更深的规律没有任何一组参数适用于所有场景。如果实际数据中重复率极高应该下调阈值如果数据几乎不重复甚至可以关闭重复块编码直接原样输出。4.4 对中文和混合文本的处理细节UTF-8编码下中文的每个字符占3字节压缩单位实际上是字节。这意味着连续重复的中文字符能有不错的压缩效果因为重复字节串较长。但有个坑必须注意UTF-8编码的字符串中间不能任意切分否则解码时会报错或者产生乱码。我在压缩时以字节为单位解压后再统一decode这保证了解码结果始终是合法的UTF-8字符串。如果你处理的文本可能混有无效UTF-8字节就不能用这个方案了。这种情况下要么预先做清理要么改用逐字符而非逐字节处理的方式。5. 实际效果与对比数据5.1 对比传统方案我拿了几组典型的测试数据做对比分别是纯数字字符串、含大量重复字符的日志文本、混合中英文的普通文本。压缩率对比如下场景原始长度(字节)本算法压缩后(字节)gzip压缩后(字节)重复性日志文本1000410280纯数字字符串500445520混合中英文800712590无重复随机字符串400415402gzip在重复性文本上压缩率更好但在纯数字和随机串上反而可能变长而且解压需要依赖库。我的算法在纯数字和随机串场景下只是轻微膨胀或损失较小而且解压逻辑只有几十行完全自包含。5.2 极端场景的表现我最关心的场景是极短字符串。比如单个字符或者十几个字节的标签。gzip对这类输入光头部就有几十字节直接不可用。我的算法对短字符串几乎不产生额外开销只要没有重复输出就是原始字节流加上少量转义处理。有一个极端反例输入本身就是全ASCII字符且完全无重复比如人类可读的随机验证码。这种情况压缩后可能比原数据略长因为引入了ESC转义的可能性。实测下来膨胀率大约在0.5%到3%之间在可接受范围内。6. 踩坑与调试实录6.1 转义BugESC字符撞车我在第一版写法里没有认真处理普通块中的ESC字符结果出现了解码错位。一个典型的失败案例是输入字符串中包含0x1B这个字节被误判为重复块起始符直接导致后续所有字节被错误解释。排查方法是构造一个包含所有256个字节值的测试语料跑一遍压缩再解压验证是否完全一致。这个测试非常重要能一次性发现所有转义边界问题。6.2 变长整数越界变长整数编码存在一个隐患如果写入时传入了超过编码容量的数值比如2^63级别的超大重复次数写出的字节会异常。虽然字符串内存不可能有这么大但非预期输入还是可能导致数据异常。解决方案是在写varint之前检查数值范围如果超过上限就抛出明确错误。这里安全比压缩率重要。6.3 UTF-8截断问题有段时间解压后偶尔出现乱码最终定位为解压过程中字节错位导致的UTF-8截断。这其实是编码Bug的一个症状不是独立的UTF-8问题。修复编码规则后就消失了。从这个坑得到的教训是字节级压缩必须在解压端做严格的边界校验每一步读入都要确认没有越界否则字符串解码阶段才会暴露问题。6.4 边界测试用例清单下面这组用例是我最终沉淀下来的回归测试集合每次改动都会先跑一遍空字符串。单字符字符串。纯重复字符比如AAAAAAAAAA。重复与非重复交替比如AAABBBCCD。包含ESC字节\x1b的字符串。全ASCII随机字符串。中包含中文、特殊符号、数字的混合文本。超长字符串比如几十万字节。所有字符表范围内的随机字节序列。7. 后续优化空间与扩展思路7.1 引入多字符序列替换当前算法只能处理单字符重复但真实文本里经常出现短单词或固定搭配的重复比如the、ing这类。如果能在块分解阶段识别这些高频序列并分配短令牌压缩率还能再上一个台阶。前阵子我试验了一个变体在压缩前先用最频繁序列检测算法提取高频二元组再把它们当作重复块处理。压缩率提升了约8%但代价是编码逻辑复杂了不少。这个方向适合数据冗余比较严重的场景。7.2 熵编码的补充重复块解决了长重复的问题但没有解决高频率不同字符的冗余问题。如果数据中存在某些字符频繁出现但不连续单纯游程编码无法利用这个特性。理论上可以在游程编码后追加一层Huffman编码对已经压缩的数据做二次压缩。考虑到Huffman需要维护频率表短字符串场景不太适合但长文本场景值得一试。7.3 与哈希函数的组合如果业务允许一点误差算法可以结合哈希来做两阶段处理先压缩再做哈希裁剪。但那就不再满足严格可逆条件了。我在项目中做过分支处理严格校验场景使用可逆压缩模糊匹配场景允许哈希降维两者通过一个标志位区分。8. 写在最后的几个经验自创压缩算法的过程让我对可逆编码的理解加深了一个层次。几个值得记住的经验先想清楚输入分布再动手写代码。压缩是一个利用先验知识的过程你越了解数据的特征编码设计就更有针对性。我最初想做一个万能算法结果处处受挫。后来明确了目标场景设计一下子清晰起来。可逆性要用测试保证而不是理论推演。理论分析可以看出“能不能可逆”但实际编码过程中容易在边界处理上引入bug。全字节集回归测试是底线。转换思维很重要。大部分人看到字符串压缩第一反应是找一个现成的库。但有些场景下轻量自研算法带来的可控性和部署自由度远超通用方案。这个东西不需要炫技能用、够用、可以验证就是好设计。最后给你一个建议如果你的场景跟我类似主要处理的是重复性较强的文本并且有严格的可逆还原需求可以试试这个算法。代码量不大核心逻辑也就是一百行出头但能让你彻底理解压缩操作背后的代价和收益。如果数据特征跟我不一样那也值得用同样的思维框架重新设计一遍收获会很大。