Burrows-Wheeler 变换(BWT)

Burrows-Wheeler 变换(Burrows-Wheeler Transform,简称 BWT)是一种针对字符串的可逆变换,由迈克尔·伯罗斯(Michael Burrows)与大卫·惠勒(David Wheeler)于 1994 年在 DEC 系统研究中心的技术报告中发表。它本身不压缩数据,却能把文本重排得高度局部重复,从而大幅提升后续压缩算法的效果。

概述

普通压缩算法直接利用原文的重复,而自然语言和基因序列的重复往往分散在各处。BWT 的巧妙之处在于:对字符串的全部循环移位按字典序排序,取排序矩阵的最后一列作为输出。由于排序把相似上下文聚在一起,输出中相同字符会成段出现,配合游程编码、Move-to-Front 变换与霍夫曼或算术编码,就得到 bzip2 这类块排序压缩器。更重要的是,这个看似破坏性的重排是完全可逆的。

核心特点

• 可逆性:仅凭变换结果与原串结束位置(或加入终止符),利用 LF 映射即可线性时间还原原文。
• 上下文聚类:相同前后文的字符被排到一起,输出呈现长游程,极利于压缩。
• 与后缀数组同构:BWT 可由后缀数组直接导出,构造复杂度 O(n)。
• 可检索性:在 BWT 上加少量辅助结构即得 FM 索引,支持在压缩形态下直接做子串查询。

应用场景

压缩方面,bzip2 以 BWT 为核心,在文本压缩率上长期优于 gzip。生物信息学是另一大主场:人类基因组约 30 亿碱基,基于 BWT 的 FM 索引把参考基因组压缩进内存并支持快速匹配,BWA、Bowtie 等主流测序比对工具皆以此为基础,支撑了现代基因测序数据分析的流水线。

常见问题

问:BWT 自己会减小数据体积吗？答:不会,它只是同长度的重排,压缩收益来自重排后的数据对游程编码和熵编码更友好。

问:为什么变换是可逆的？答:排序矩阵的第一列就是末列字符排序的结果,同一字符在首列与末列中保持相对次序(LF 映射),据此可以从结束位置一步步倒推出整个原串。

问:FM 索引和 BWT 是什么关系？答:FM 索引由费拉吉纳与曼齐尼在 BWT 之上加上秩统计等辅助信息构成,使人们能在不解压的情况下统计与定位任意子串,是压缩全文索引的代表。