Burrows–Wheeler Transform（简称BWT，也称作块排序压缩），是一个被应用在数据压缩技术（如bzip2）中的算法。该算法于1994年被和在位于加利福尼亚州帕洛阿尔托的发明。它的基础是之前Wheeler在1983年发明的一种没有公开的转换方法。

当一个字符串用该算法转换时，算法只改变这个字符串中字符的顺序而并不改变其字符。如果原字符串有几个出现多次的子串，那么转换过的字符串上就会有一些连续重复的字符，这对压缩是很有用的。该方法能使得基于处理字符串中连续重复字符的技术（如MTF变换和游程编码）的编码更容易被压缩。

举个例子：

该算法的输出因为有更多的重复字符而更容易被压缩了。

Burrows–Wheeler变换过程
算法将输入字符串的所有循环字符串按照字典序排序，并以排序后字符串形成的矩阵的最后一列为其输出。

Burrows–Wheeler变换的还原过程

• 基于上述的BWT变换过程，以字符串“banana”为例，我们得到了变换结果“annb$aa”。其还原过程见以下过程：

1 基于原字符串矩阵的最后一列为“annb$aa”，我们进行该列进行排序，得到“$aaabnn”,并将其作为还原矩阵的第一列

2 经过1.1的转移、排序和组合，我们得到了7对邻接字符串： ，将这7对邻接字符串进行排序后，得到 ，由此，我们得到了还原矩阵的第二列“b$nnaaa”

3 经过1.2的转移、排序和组合，我们得到了7对邻接字符串： ，将这7对邻接字符串进行排序后，得到 ，由此，我们得到了还原矩阵的第三列“abaan$n”

4 经过1.3的转移、排序和组合，我们得到了7对邻接字符串： ，将这7对邻接字符串进行排序后，得到 ，由此，我们得到了还原矩阵的第四列“na$naba”

5 经过1.4的转移、排序和组合，我们得到了7对邻接字符串： ，将这7对邻接字符串进行排序后，得到 ，由此，我们得到了还原矩阵的第五列“anbana$”

6 经过1.5的转移、排序和组合，我们得到了7对邻接字符串： ，将这7对邻接字符串进行排序后，得到 ，由此，我们得到了还原矩阵的第六列“naa$anb”。

经过六次排序转移与组合，还原出了原有的字符串即“$banana”。

python实现(基于next值方式)
def bwt(s):
"""对字符串进行Burrows-Wheeler变换 不使用唯一字符('EOF')做标记 返回索引值列表"""
#创建所有循环字符串
table = [s[i:] + s[:i] for i in range(len(s))]
#获取排序后的结果
table_sorted = table[:]
table_sorted.sort()
#获取已排序表每个字符串在未排序表中对应字符串的下一个字符串在已排序表中的索引值
indexlist = []
for t in table_sorted:
index1 = table.index(t)
index1 = index1+1 if index1

python实现(基于末尾添加唯一字符方式)
通过在末尾添加唯一字符(不与输入字串中任何字符相同)后再进行变换，可以不需要传递索引值列表，不过逆变换的时候要做更多计算。

下面的伪代码提供了一个逆过程的朴素实现（输入字符串s为原过程之输出）：
function inverseBWT(string s)
生成length（s）个空串
repeat length(s) times
将字符串s作为一列插入每个字符串的串首
对所有字符串排序
返回结尾为EOF的行

END = '\1' #必须不与原字符串中任何字符相同

def bwt(s):
"""对字符串进行Burrows-Wheeler变换"""
s = s + END
#创建所有循环字符串
table = [s[i:] + s[:i] for i in range(len(s))]
#获取排序后的结果
table_sorted = table[:]
table_sorted.sort()
#取排序后结果的最后一列作为结果字符串
return *.join([row[-1] for row in table_sorted])

def ibwt(r):
table = [] len(r)
for _ in r:
table = sorted([r[m] + table[m] for m in range(len(r))])
s = [row for row in table if row.endswith(END)][0]
return s.rstrip(END)

参考资料
外部链接
*[https://web.archive.org/web/20110210104353/http://compressionratings.com/bwt.html Compression comparison of BWT based file compressors]
*[http://marknelson.us/1996/09/01/bwt/ Article by Mark Nelson on the BWT]
*[http://bijective.dogma.net/00yyy.pdf A Bijective String-Sorting Transform, by Gil and Scott]
*[https://web.archive.org/web/20170306035431/https://encode.ru/attachment.php?attachmentid=959&d=1249146089 Yuta's openbwt-v1.5.zip contains source code for various BWT routines including BWTS for bijective version]
*[http://arxiv.org/abs/0908.0239 On Bijective Variants of the Burrows–Wheeler Transform, by Kufleitner]
*[http://google-opensource.blogspot.com/2008/06/debuting-dcs-bwt-experimental-burrows.html Blog post] and [https://code.google.com/p/dcs-bwt-compressor/ project page] for an open-source compression program and library based on the Burrows–Wheeler algorithm
*[https://www.youtube.com/watch?v=P3ORBMon8aw MIT open courseware lecture on BWT (Foundations of Computational and Systems Biology)]