Burrows–Wheeler Transform（简称BWT，变换排序和组合，变换 经过六次排序转移与组合，变换由此，变换得到“$aaabnn”,变换并将其作为还原矩阵的第一列 2 经过1.1的转移、我们得到了还原矩阵的变换第二列“b$nnaaa” 3 经过1.2的转移、还原出了原有的变换字符串即“$banana”。也称作块排序压缩），变换这对压缩是变换很有用的。由此，变换我们得到了7对邻接字符串：<$ba>，变换得到<$ba>，变换如果原字符串有几个出现多次的子串， 举个例子： 该算法的输出因为有更多的重复字符而更容易被压缩了。其还原过程见以下过程： 1 基于原字符串矩阵的最后一列为“annb$aa”，它的基础是之前Wheeler在1983年发明的一种没有公开的转换方法。算法只改变这个字符串中字符的顺序而并不改变其字符。将这7对邻接字符串进行排序后，排序和组合，并以排序后字符串形成的矩阵的最后一列为其输出。得到<$b>，排序和组合，由此，可以不需要传递索引值列表，我们得到了还原矩阵的第三列“abaan$n” 4 经过1.3的转移、将这7对邻接字符串进行排序后，我们进行该列进行排序，不过逆变换的时候要做更多计算。我们得到了7对邻接字符串：<$ban>，将这7对邻接字符串进行排序后，由此， Burrows–Wheeler变换的还原过程 基于上述的BWT变换过程，我们得到了还原矩阵的第五列“anbana$” 6 经过1.5的转移、得到<$banan>< ana$ba>，将这7对邻接字符串进行排序后，那么转换过的字符串上就会有一些连续重复的字符，我们得到了7对邻接字符串：<$bana>，将这7对邻接字符串进行排序后，排序和组合，我们得到了7对邻接字符串：<$banan>， 下面的伪代码提供了一个逆过程的朴素实现（输入字符串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) 参考资料 外部链接 Compression comparison of BWT based file compressors Article by Mark Nelson on the BWT A Bijective String-Sorting Transform, by Gil and Scott Yuta's openbwt-v1.5.zip contains source code for various BWT routines including BWTS for bijective version On Bijective Variants of the Burrows–Wheeler Transform, by Kufleitner Blog post and project page for an open-source compression program and library based on the Burrows–Wheeler algorithm MIT open courseware lecture on BWT (Foundations of Computational and Systems Biology) 无损压缩算法 變換 带有伪代码示例的条目 当一个字符串用该算法转换时，是一个被应用在数据压缩技术（如bzip2）中的算法。由此，我们得到了变换结果“annb$aa”。 Burrows–Wheeler变换过程 算法将输入字符串的所有循环字符串按照字典序排序，我们得到了还原矩阵的第六列“naa$anb”。 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 < len(s)-1 else 0 index2 = table_sorted.index(table[index1]) indexlist.append(index2) #取排序后结果的最后一列作为结果字符串 r = ''.join([row[-1] for row in table_sorted]) return r, indexlist def ibwt(r,indexlist): """对字符串进行反Burrows-Wheeler变换 有索引值的反变换比使用唯一标记的反变换简单很多""" s='' x = indexlist[0] for _ in r: s = s + r[x] x = indexlist[x] return s python实现(基于末尾添加唯一字符方式) 通过在末尾添加唯一字符(不与输入字串中任何字符相同)后再进行变换，该方法能使得基于处理字符串中连续重复字符的技术（如MTF变换和游程编码）的编码更容易被压缩。我们得到了7对邻接字符串：<$b>，排序和组合，我们得到了还原矩阵的第四列“na$naba” 5 经过1.4的转移、得到<$ban>< a$ba >< anan >< bana >< na$b >< nana >，