学完本文，你将能独立完成曾比特（Zengbit）编码的完整流程——包括位流切分、映射表构建、压缩写入与无损还原，并避开新手最常见的符号溢出与填充错位陷阱。
第一步：理解曾比特核心机制（15分钟）
曾比特并非通用压缩算法，而是一种面向固定长度二进制块的“位级重映射”技术。其核心假设是：数据块中某些位组合出现频率远高于其他组合。操作前，你必须明确三点：
1. 块长固定为N位（通常取8、16或32，实操推荐16位）。
2. 统计所有可能块值（0到2^N-1）的出现次数。
3. 将高频块映射为短码（如6位），低频块保留原码或加前缀标记。
本步不写代码，但需在纸上画出输入输出映射示意：例如N=8时，若块值0x3F出现100次，则将其映射为短码`011`，而0x7A仅出现2次，则保留原8位并前置1位转义符。
第二步：搭建位流读写环境（20分钟）
用Python（或C++）实现底层位流类。关键函数：
- `write_bits(value, bit_count)`：将value的低bit_count位写入缓冲区，自动处理跨字节边界。
- `read_bits(bit_count)`：从缓冲区读取bit_count位并返回。
实操代码骨架：
```python
class BitStream:
def __init__(self, data=None):
self.buf = bytearray(data) if data else bytearray()
self.bit_pos = 0
def write_bits(self, value, n):
for i in range(n-1, -1, -1):
byte_idx = self.bit_pos // 8
if byte_idx == len(self.buf): self.buf.append(0)
bit_idx = 7 - (self.bit_pos % 8)
self.buf[byte_idx] |= ((value >> i) & 1) << bit_idx
self.bit_pos += 1
def read_bits(self, n):
val = 0
for i in range(n-1, -1, -1):
byte_idx = self.bit_pos // 8
bit_idx = 7 - (self.bit_pos % 8)
val = (val << 1) | ((self.buf[byte_idx] >> bit_idx) & 1)
self.bit_pos += 1
return val
```
注意：写入后必须记录总位长（`self.bit_pos`），用于压缩头部存储。
第三步：统计原始数据块频率（10分钟）
读取原始文件（假设为二进制），按N位切分。若文件字节数不是N/8的整数倍，尾部不足N位需用0填充并记录填充数。统计每个块值的频次到字典`freq_dict`。示例：
```python
freq = {}
padding = 0
data = open('input.bin','rb').read()
total_bits = len(data)*8
if total_bits % N != 0:
padding = N - (total_bits % N)
# 补0后切分
```
此步务必用`collections.Counter`或自建哈希，O(块数)完成。
第四步：构建映射表并排序（15分钟）
将`freq_dict`按频次降序排列。取前K个高频块（K=2^M，M为短码位数，建议M=4或5，即短码长4~5位）。剩余低频块全部归入“转义组”。映射规则：
- 高频块编号0~K-1，对应短码二进制值0~K-1。
- 转义组统一使用固定前缀`1`（1位），后跟原始N位块值。
- 高频块短码前不加前缀，但为保证解码唯一性，短码首位必须为0（所以K最大为2^(M-1)）。若M=4，短码长4位，首位0，可用短码数=8个。若高频块超过8个，需增加M或调整阈值。
实操：生成两个字典`short_to_orig`和`orig_to_short`。保存映射表到压缩文件头部，格式：N（1字节）、M（1字节）、K（2字节）、K个原始块值（每块N/8字节）。
第五步：执行压缩写入（20分钟）
初始化输出`BitStream`，先写入头部信息（N、M、K及映射表），再逐块处理原始数据：
```python
out.write_bits(N, 8)
out.write_bits(M, 8)
out.write_bits(K, 16)
for orig_val in top_K_list: out.write_bits(orig_val, N)
for block in blocks:
if block in orig_to_short:
out.write_bits(orig_to_short[block], M) # 短码首位0
else:
out.write_bits(1, 1) # 转义前缀
out.write_bits(block, N) # 原块值
```
压缩完成后，将`out.bit_pos`写入文件末尾（4字节）。注意：短码写入时，必须保证其二进制首位为0，否则解码器会误判为转义。若K>2^(M-1)，自动将M加1并重新生成短码。
第六步：还原解码（20分钟）
读取压缩文件，先解析头部N、M、K及映射表。然后循环读取：
- 读取1位，若为0，继续读M-1位组成短码，查`short_to_orig`得到原始块。
- 若为1，继续读N位，直接作为原始块。
- 读到文件末尾（根据记录的总位长停止），丢弃填充的0块。
解码后写入新文件。注意：必须将短码的位序与写入时一致（高位在前）。验证还原文件与原文件字节完全一致（用`hashlib.md5`比对）。
第七步：性能测试与调参（10分钟）
对同一数据分别用N=8、16、32和M=4、5、6组合测试，记录压缩比（压缩后位数/原始位数）。常见规律：N越小，块数越多，但映射表头部开销增大；M越大，短码越长，但可容纳更多高频块。实操建议：先用100KB样本扫参，选择压缩比最高的组合。
结尾常见坑提醒（必读）
- 坑1：短码首位不固定为0，导致解码时转义前缀冲突。务必在生成短码时检查`(code >> (M-1)) == 0`，否则丢弃该映射。
- 坑2：填充位数未写入头部，还原时多出垃圾块。压缩文件末尾必须存储原始有效块数或填充数。
- 坑3：位流读写时跨字节顺序错误。统一使用“高位在前”规则，并严格测试读写对称。
- 坑4：映射表未排序，导致低频块误入高频区。必须按频次降序选择K个。
- 坑5：文件尾部不足N位时直接补0，但还原后原文件多出填充字节。需在头部记录原始字节长度，解码后截断。