Day 38：Burrows-Wheeler（BWT）
18年10月17日 · 吴超 1785 人阅读
Burrows-Wheeler 变换的作用
Burrows-Wheeler转换是一种用于 bzip2 压缩中的转换技术（也可称作块排序压缩，简称 BWT）从而使 bzip2 优于其他当时最先进的压缩算法
bzip2：能够进行高质量的数据压缩。能够把普通的数据文件压缩10%至15%，压缩的速度和解压的效率都非常高，支持大多数压缩格式，包括tar、gzip 等等。
Burrows-Wheeler 变换的原理
在语言中会有大量重复出现的子串，比如单词 he, the, there, her, where 中就存在 he 这个子串。布鲁斯惠乐转换就是把文本重新排序，在所给例子中就是尽力把 h 排到一起，结果是,,,,eeerrhhrhhhet tweee。之所以把相同的子串放到一起，是因为当压缩算法工作时，遇到多个相同的串排在一起的压缩效率更高。
Burrows-Wheeler 变换的思想
Burrows-Wheeler变换首先将输入的序列进行全排列（包括输入的符号）。之后将得到的“全排列”的字符串按照字典序排序。排序后的每个字符串的最后一个字母连成的字符串，即为Burrows-Wheeler变换的输出。
算法输入：her her she
所有的循环字典排序后：
 |
为了实现这个过程，我们从一个空集合开始。原始列被预置到当前集合，并且按字母顺序对集合进行排序。逐列重复最后完成排序。
有两个明显的问题：速度和内存占用。BWT 不需要在内存中保留所有的排列。BWT 的作者还声称他们能够在几乎线性的时间内实现字典序排序。并且，为了更好的处理结果，每个1MB 大小的块都会被预处理。虽然在今天看来 1MB 不值钱，但在 bipz2 的时代，内存可是很贵的。
Burrows-Wheeler 变换的实现
Python3Turtle
