Burrows–Wheeler Transform（简称BWT，也称作块排序压缩），是一个被应用在数据压缩技术（如bzip2）中的算法。该算法于1994年被Michael Burrows（英语：Michael Burrows）和David Wheeler（英语：David Wheeler）在位于加利福尼亚州帕洛阿尔托的DEC系统研究中心（英语：DEC Systems Research Center）发明。它的基础是之前Wheeler在1983年发明的一种没有公开的转换方法。
当一个字符串用该算法转换时，算法只改变这个字符串中字符的顺序而并不改变其字符。如果原字符串有几个出现多次的子串，那么转换过的字符串上就会有一些连续重复的字符，这对压缩是很有用的。该方法能使得基于处理字符串中连续重复字符的技术（如MTF变换和游程编码）的编码更容易被压缩。
举个例子：
该算法的输出因为有更多的重复字符而更容易被压缩了。
算法将输入字符串的所有循环字符串按照字典序排序，并以排序后字符串形成的矩阵的最后一列为其输出。
banana
$ b a n a n a
a $ b a n a n
n a $ b a n a
a n a $ b a n
n a n a $ b a
a n a n a $ b
b a n a n a $
$ b a n a n a
a $ b a n a n
a n a $ b a n
a n a n a $ b
b a n a n a $
n a $ b a n a
n a n a $ b a
a n n b $ a a
Burrows–Wheeler变换的还原过程
- 基于上述的BWT变换过程，以字符串“banana”为例，我们得到了变换结果“annb$aa”。其还原过程见以下过程：
- 1 基于原字符串矩阵的最后一列为“annb$aa”，我们进行该列进行排序，得到“annb$aa”,并将其作为还原矩阵的第一列
| Burrows–Wheeler 还原过程 1 | |||||
|---|---|---|---|---|---|
| 输入 | 转移 | 排序 | 组合 | ||
- - - - - - a | a - - - - - - | $ - - - - - - | $ - - - - - a | ||
- 2 经过1.1的转移、排序和组合，我们得到了7对邻接字符串：<a$> <na> <na> <ba> <$b> <an> <an>，将这7对邻接字符串进行排序后，得到<$b> <a$> <an> <an> <ba> <na> <na>，由此，我们得到了还原矩阵的第二列“b$nnaaa”
| Burrows–Wheeler 还原过程 2 | |||||
|---|---|---|---|---|---|
| 输入 | 转移 | 排序 | 组合 | ||
$ - - - - - a | a $ - - - - - | $ b - - - - - | $ b - - - - a | ||
- 3 经过1.2的转移、排序和组合，我们得到了7对邻接字符串：<a$b> <na$> <nan> <ban> <$ba> <ana> <ana>，将这7对邻接字符串进行排序后，得到<$ba> <a$b> <ana> <ana> <ban> <na$> <nan>，由此，我们得到了还原矩阵的第三列“abaan$n”
| Burrows–Wheeler 还原过程 3 | |||||
|---|---|---|---|---|---|
| 输入 | 转移 | 排序 | 组合 | ||
$ b - - - - a | a $ b - - - - | $ b a - - - - | $ b a - - - a | ||
- 4 经过1.3的转移、排序和组合，我们得到了7对邻接字符串：<a$ba> <na$b> <nana> <bana> <$ban> <ana$> <anan>，将这7对邻接字符串进行排序后，得到<$ban> < a$ba > <ana$> < anan > < bana > < na$b > < nana >，由此，我们得到了还原矩阵的第四列“na$naba”
| Burrows–Wheeler 还原过程 4 | |||||
|---|---|---|---|---|---|
| 输入 | 转移 | 排序 | 组合 | ||
$ b a - - - a | a $ b a - - - | $ b a n - - - | $ b a n - - a | ||
- 5 经过1.4的转移、排序和组合，我们得到了7对邻接字符串：<a$ban> <na$ba> <nana$> <banan> <$bana> <ana$b> <anana>，将这7对邻接字符串进行排序后，得到<$bana> <a$ban> < ana$b > <anana> <banan> <na$ba> <nana$>，由此，我们得到了还原矩阵的第五列“anbana$”
| Burrows–Wheeler 还原过程 5 | |||||
|---|---|---|---|---|---|
| 输入 | 转移 | 排序 | 组合 | ||
$ b a n - - a | a $ b a n - - | $ b a n a - - | $ b a n a - a | ||
- 6 经过1.5的转移、排序和组合，我们得到了7对邻接字符串：<a$bana> <na$ban> <nana$b> <banaan> <$banan> <ana$ba> <anana$>，将这7对邻接字符串进行排序后，得到<$banan> <a$bana> < ana$ba> <anana$> <banana> <na$ban> <nana$b>，由此，我们得到了还原矩阵的第六列“naa$anb”。
| Burrows–Wheeler 还原过程 5 | |||||
|---|---|---|---|---|---|
| 输入 | 转移 | 排序 | 组合 | ||
$ b a n a - a | a $ b a n a - | $ b a n a n - | $ b a n a n a | ||
经过六次排序转移与组合，还原出了原有的字符串即“$banana”。
def bwt(s): """对字符串进行Burrows-Wheeler变换 不使用唯一字符('EOF')做标记 返回索引值列表""" #创建所有循环字符串 table = + s 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 < len(s)-1 else 0 index2 = table_sorted.index(table) indexlist.append(index2) #取排序后结果的最后一列作为结果字符串 r = ''.join( for row in table_sorted]) return r, indexlistdef ibwt(r,indexlist): """对字符串进行反Burrows-Wheeler变换 有索引值的反变换比使用唯一标记的反变换简单很多""" s='' x = indexlist for _ in r: s = s + r x = indexlist return s