案例库 · 软件与 IT · 技术决策 · 1994
Burrows 和 Wheeler 重新排序块的旋转，使其压缩效果大幅提升
Burrows 和 Wheeler 在 1994 年提出的变换将块的旋转排序，使相同字符聚集，让 bzip2 胜过旧式压缩器。
Digital Equipment Corporation
那一手
无损压缩受限于方法能看到的冗余程度。LZ 系列和 Huffman 编码在普通文本上分别达到瓶颈。
Burrows 和 Wheeler 在 1994 年的 DEC 报告中描述了一种块排序变换：列出块的每个旋转，排序，并输出最后一列。由于旋转共享后缀，相同字符聚集，短游程和move-to-front 编码将其转化为很少的符号。
该变换是可逆的，因此是重排而非损失。结果用于 bzip2，其压缩文本效果优于当时工具，使该技术成为慢但紧凑压缩的标准。
为什么管用
- 对旋转排序使上下文相同的相同符号聚集。
- 游程和 move-to-front 编码随后找到长且便宜的游程。
- 变换是一种排列，因此解压是精确的。
- 它适用于任何重复结构，因此不针对特定文件类型。
值了多少对块的旋转进行排序，使相似邻居聚集聪明
可以搬走什么
在压缩之前，重新排列数据，使相同符号相邻。聚集可预测部分的变换能让普通压缩器显著增强。
后来呢
Burrows-Wheeler 变换成为 bzip2 的核心，后来成为 FM-index 的基础，用于查找子串和基因组图谱。同一思想如今驱动着高通量生物信息学比对工具。
资料来源
发现哪里写错了？告诉我们。