列式存储里,数值列有字典编码、RLE、Frame-of-Reference 一整套压缩武器,但字符串列一直是个麻烦:URL、UUID、设备 ID、日志前缀、JSON 片段这些高基数值既不适合字典编码(重复率太低),又塞不进数值压缩器。通用压缩(gzip/zstd)压缩率不错,却必须整块流式解压,无法随机访问单值,与分析引擎"按行组读取、向量化解码"的模型格格不入。FSST(Fast Static Symbol Table,VLDB 2020)正是为这个场景设计的:它从样本里学出一个不超过 255 项的"符号表",把常见字节串压成单字节符号,用一次查表即可解码任意单值。它是 DuckDB 字符串列压缩、Parquet 字节流编码背后的关键一环。本文从字典编码的失效讲起,剖析符号学习的最长匹配贪心、转义字节的无损保证、训练/编码/解码三阶段,以及与字典编码、通用压缩的取舍,最后给出一份本地实跑验证过(83 串、压缩率 0.279、零漏报)的 Python 教学实现。
一、为什么字典编码救不了字符串列
上一轮我们剖析过字典编码:把重复值映射成紧凑整数,高基数时会退化。字符串列的困境正是退化的极端形态。以一列 URL 为例,每一行的完整值都不同(末尾 ID 不一样),DISTINCT 几乎等于行数——字典编码的字典本身就有整列那么大,位打包后毫无收益,甚至因额外字典而膨胀。
但仔细看这些值,它们共享大量字节级子串:https://www.example.com/api/v1/ 这段前缀出现在每一行里。字典编码以"整值"为单位,看不见这种子串级重复;通用压缩能看见,但代价是失去随机访问——想读第 7 行,gzip 得从第 1 字节一路解压过来。这在需要跳过行组、按谓词裁剪、向量化逐批解码的列式引擎里是不可接受的。
FSST 的定位就清楚了:字节级、无损、可单值随机解码的轻量字符串压缩。它不追求 gzip 的极限压缩率,而是追求"压缩率够好 + 解码够快 + 单值可达"三者的平衡。这三点恰好击中分析引擎的痛点。
二、核心思想:把高频字节串换成单字节符号
FSST 的名字已经点明机制——静态符号表(Static Symbol Table)。"静态"指符号表在训练期一次性学出,之后编码解码都只读不改(这与 zstd 的动态字典不同)。"符号"是一个 1 到 8 字节的子串,被分配一个字节长的 code。
关键约束:一个字节只有 256 种取值。FSST 保留 code=0 作为转义字节(escape),剩下 255 个 code 分配给符号。于是任意符号都只占 1 字节,这是它能做到极致轻量解码的根本——解码就是把每个字节当索引查一次表。
压缩来自一个简单算术:若符号 s 长 L 字节、在样本中出现 f 次,用它替换后每次省 L-1 字节,总收益 (L-1)·f。训练期就是挑选收益最高的符号填满 255 个槽位。教学实现用一个真实例子验证:83 个 URL/日志/中文混合字符串,原始 3486 字节,FSST 编码后 972 字节,压缩率 0.279(省 72.1%)。
三、训练期:从样本里学符号表
训练分两步。第一步枚举候选子串:对每个字符串、每个起始位置,截取长度 1 到 8 的所有子串,统计频次。第二步按增益排序选符号:增益 (L-1)·f,长度 1 的子串增益为 0 直接排除(用单字节符号换单字节没有意义),然后按增益降序取前 255 个。
同增益时的次序需要确定性处理,否则同样的样本在不同运行里会学出不同符号表。教学实现用"更长优先、再按字典序"打破平局:
from collections import Counter
ESCAPE, MAX_SYMBOLS, MAX_LEN = 0, 255, 8
def train(values, max_symbols=MAX_SYMBOLS, max_len=MAX_LEN):
counts = Counter()
for v in values: # v 是 bytes
n = len(v)
for i in range(n):
top = min(max_len, n - i)
for l in range(1, top + 1):
counts[v[i:i + l]] += 1 # 枚举所有 <=8 字节子串
scored = []
for sym, freq in counts.items():
gain = (len(sym) - 1) * freq # 净收益:每替换一次省 L-1 字节
if gain <= 0:
continue # 单字节子串无增益
scored.append((gain, sym))
scored.sort(key=lambda x: (-x[0], -len(x[1]), x[1])) # 确定性排序
symbols = []
for _gain, sym in scored:
if len(symbols) >= max_symbols:
break
symbols.append(sym)
return symbols # 第 i 项对应 code = i+1生产级 FSST 的训练远比这精细——它会用后缀数组一次性统计所有子串、用"收益/占用"比迭代替换已选符号以逼近最优表,并控制训练样本量(几千行)以保证线性时间。但核心目标一致:让高频长子串拿到短 code,从而最大化 (L-1)·f 的总和。
四、编码期:贪心最长匹配 + 转义兜底
有了符号表,编码就是把字符串从头到尾切成符号序列。每一步在当前位置找最长的可匹配符号(长度降序遍历),命中则输出它的 1 字节 code 并前进 L 字节;没有任何符号匹配时,输出转义字节 0 再原样输出当前 1 个字节,前进 1 字节。这个"转义兜底"是无损性的根基:任何没被符号覆盖的字节都能被逐字节保留下来。
class FSST:
def __init__(self, symbols):
self.symbols = symbols
self.lookup = {sym: i + 1 for i, sym in enumerate(symbols)}
# 长度降序 -> 贪心最长匹配;同长度按 code 升序保证确定性
self.by_len = sorted(self.lookup.items(),
key=lambda kv: (-len(kv[0]), kv[1]))
def encode(self, s):
out = bytearray()
i, n = 0, len(s)
while i < n:
hit_code = hit_len = None
for sym, code in self.by_len:
l = len(sym)
if i + l <= n and s[i:i + l] == sym:
hit_code, hit_len = code, l
break # 最长匹配,立即停
if hit_code is not None:
out.append(hit_code); i += hit_len
else:
out.append(ESCAPE); out.append(s[i]); i += 1
return bytes(out)这里有个工程权衡:按长度降序逐个比对符号是 O(符号数 × 符号长) 的朴素做法,生产实现会用前缀哈希 / 首字节分桶把候选符号缩到几个,把编码做到了每字节常数级。教学实现保留朴素版本只为讲清"最长匹配"这一核心。
五、解码期:一次查表、单值随机可达
解码是编码的逆过程,且更简单:读一个字节,若 code==0 就取下一个字节原样输出,否则用 code-1 索引符号表、把整个符号追加到结果。不需要任何状态回溯,任意一个编码后的值都能独立解码——这正是 FSST 相对 gzip 的决定性优势。
def decode(self, data):
out = bytearray()
i, n = 0, len(data)
while i < n:
code = data[i]
if code == ESCAPE: # 0 -> 下一个字节是原始字节
out.append(data[i + 1]); i += 2
else:
out.extend(self.symbols[code - 1]); i += 1
return bytes(out)
# [T1/T6 PASS] 83 串往返无损;第 7 行 11B 直接还原,无整列解压依赖DuckDB 等引擎正是利用这一点:行组里的字符串列被编码成"符号序列 + 转义流"后,解码单个值只是顺序扫描该值的字节并查表,无需解压整个行组。这让谓词过滤、投影、哈希连接都能在压缩态上高效进行。
六、三种方案横向对比
把 FSST 放在字符串压缩的坐标系里,它的取舍就更清楚了。下面的定性对比基于教学实现的实测与公开论文结论:
| 方案 | 压缩粒度 | 单值随机访问 | 高基数字符串 | 代价 |
|---|---|---|---|---|
| 字典编码 + 位打包 | 整值 | 支持(查字典) | 退化(字典膨胀) | 需维护字典 |
| gzip / zstd | 整块字节流 | 不支持(流式解压) | 较好 | 解压慢、有头部开销 |
| FSST | 字节子串(符号) | 支持(一次查表) | 擅长 | 训练期一次性成本 |
教学实现的压缩率 0.279 是在高度同质的 URL 样本上取得的;真实数据的收益取决于子串重复度——重复前缀越长、越多,FSST 越有效;若字符串完全随机(如加密哈希),符号表学不到东西,FSST 会退化为"每字节 escape+byte",此时应果断放弃压缩。这是选用任何压缩前都要做的样本收益评估。
七、边界、无损性与实现清单
教学实现用 6 组测试覆盖了容易出错的地方,全部通过(ALL TESTS PASSED):
- 往返无损:83 个含 URL、UUID、中文 UTF-8、NUL 字节的字符串,encode→decode 逐字节一致。
- 转义路径:训练样本未覆盖的字节(
\x01\xfe\xff等)走 escape+byte 原样保留,9B→18B 但零信息丢失。 - 符号表上限:强制
max_symbols=16时符号数从不超限,最长匹配贪心 50 例往返一致。 - 边界输入:空串、单字节、全相同、单 NUL、多 NUL 均无损——空串编码为空字节流,解码 naturally 返回空。
落地实现时要守住四条:其一,转义字节必须与符号 code 空间严格分离(code=0 永不分配给符号),否则解码歧义;其二,解码遇到 escape 必须再读一个字节,越界输入要防御(教学实现假设输入合法,生产需校验);其三,符号表随数据一起持久化,训练样本要有代表性且定期重训,否则数据分布漂移后压缩率暴跌;其四,编码是 CPU 操作,要评估"省下的 I/O"是否大于"编码增加的 CPU",对冷数据收益才明显。
结语
FSST 的本质是一次精准的定位:它不试图做通用压缩的"万能选手",而是专攻列式引擎里高基数字符串列这个字典编码失效、通用压缩又太重的夹缝。用一张 255 项的静态符号表,它把字节级重复转换成单字节 code,在无损的前提下同时拿到了可观压缩率与单值随机访问能力——这正是 DuckDB 等现代分析引擎在字符串列上取得亮眼性能的关键拼图。从字典编码(整值重复)到数据跳过(块级裁剪)再到 FSST(字节子串重复),可以看到列式压缩的一条清晰主线:在不同粒度上寻找重复,用最小的元数据换取最大的 I/O 节省。理解 FSST,就理解了这条主线上"字符串"这一环是如何被补上的。

发表评论 取消回复