技术

BWT 变换原理：压缩前为何先排序

📅 2026-07-31 · ✍️ 闪压技术团队 · ⏱ 5 分钟阅读

一个反直觉的发现:排序能让数据变小

很多人对"压缩"的第一印象是:用更紧凑的方式重新编码。BWT(Burrows-Wheeler Transform)走了一条看似绕远路的路——先把数据打散成所有可能的循环移位,再对这些循环移位做字典序排序。

排序后,数据看起来"乱"了,但同一种字符会聚集成一小段一小段。这种"局部聚集"对后续的熵编码非常友好,从而显著提高压缩率。BWT 本身不做任何编码,只是一次预处理,但这一步常常是 bzip2 等工具能达到高压缩率的关键。

BWT 怎么把数据变成"排序后的样子"

理解 BWT 最直观的方式,是看它对"banana"做了什么。

列出所有循环移位:

banana
ananab
nanaba
anaban
nabana
abanan

按字典序排序:

abanan
anaban
ananab
banana
nabana
nanaba

只取排序后每一行的最后一个字符拼起来,得到 BWT 输出:"nnbaaa"。

注意看,"banana"里只有 a、b、n 三个字符,输出里同类字符却明显聚拢了——三个 a 排在一起,两个 n 排在一起。这就是 BWT 的精髓。

为什么"同类相聚"让后续压缩更高效

压缩能省多少空间,核心看它能不能高效表达"重复出现的符号"。熵编码对"某字符出现概率高"特别敏感——概率越高,用越短的码字表达越划算。

原始"banana"中,a 出现 3 次、n 出现 2 次、b 出现 1 次。BWT 处理后,"nnbaaa"里 a 连续出现 3 个、n 连续出现 2 个,b 单独一个位置。熵编码看到"连续出现 + 偶尔单独",可以用游程编码的方式表达,连续 3 个 a 只用几个比特就能表示。

这就是"局部聚集"的妙处:BWT 不直接压缩,只是把数据排列得更"易压"。

反变换:BWT 是无损的

BWT 是一个可逆变换,只要知道 BWT 输出和原始数据长度,就能完整还原。

反变换的关键:把 BWT 输出作为最后一列,在它左边加一列排序,再在最右边加新一列继续排序……迭代足够多次后,第一列重新出现时,原数据就还原出来。

只保留最后一列 + 原始长度 + 排序顺序,就能无损还原整串。这一点和字典压缩里的"滑动窗口"思路完全不同——字典压缩要保留整个字典表,BWT 几乎不需要额外的字典。

BWT 在压缩工具中的位置

闪压支持的 ZIP、7Z、gzip 等主流压缩格式,底层并不都用 BWT。通常情况下:gzip 和 ZIP(DEFLATE 算法)走 LZ77 + 哈夫曼编码,不走 BWT;7Z 的 LZMA 走字典 + 范围编码,不直接走 BWT;bzip2 把 BWT + 哈夫曼 + 游程编码组合,在文本压缩上常常能拿到比 DEFLATE 更小的体积。

BWT 不是"压缩的银弹",而是一种"预处理前置",适合放在熵编码前面,把数据整理成"易压"形态。数据本身已经接近随机(比如已压缩过的 JPG 视频流)时,BWT 起不到明显作用;但对重复模式多的纯文本、源代码、HTML,BWT 的预处理价值非常大。

BWT 与字典压缩的取舍

字典压缩的核心是"用之前出现过的短语表示当前位置",优势是压缩/解压速度快、实现简单。BWT 的核心是"重新排列字符,把同类聚在一起",优势是对重复字符密集的文本能拿到更高压缩率,缺点是反变换需要排序信息、内存开销更大。

实际工具常把两者结合:bzip2 用 BWT + 熵编码;7Z 的 LZMA 用字典 + 范围编码;闪压的 ZIP 输出走 DEFLATE 路径,7Z 输出走 LZMA 路径。通常情况下,对纯文本(代码、日志、HTML),bzip2 风格的 BWT 路线压缩更彻底;对通用混合文件,字典压缩路线速度更快。

一句话总结 BWT

BWT 不直接压缩任何东西,它只是把"分散的相同字符"重新排成"相邻的相同字符"。这一个看似简单的预处理动作,让后续的熵编码和游程编码能拿到更短的码字,从而整体压缩率上一个台阶。理解 BWT,就看懂一个核心:排序的妙处。