Burrows-Wheeler变换

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

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

举个例子:

算法输入	SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
算法输出	TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT

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

Burrows–Wheeler变换过程

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

Burrows–Wheeler变换过程
算法输入	序号	所有的循环字符串	将所有的字符串按照字典序排序	next值	输出最后一列
abracadabra	0 1 2 3 4 5 6 7 8 9 10	a b r a c a d a b r a b r a c a d a b r a a r a c a d a b r a a b a c a d a b r a a b r c a d a b r a a b r a a d a b r a a b r a c d a b r a a b r a c a a b r a a b r a c a d b r a a b r a c a d a r a a b r a c a d a b a a b r a c a d a b r	a a b r a c a d a b r a b r a a b r a c a d a b r a c a d a b r a a c a d a b r a a b r a d a b r a a b r a c b r a a b r a c a d a b r a c a d a b r a a c a d a b r a a b r a d a b r a a b r a c a r a a b r a c a d a b r a c a d a b r a a b	2 5 6 7 8 9 10 4 1 0 3	rdarcaaaabb

下面的伪代码提供了一个朴素的算法过程,设s为输入的字符串并以EOF为结尾：

 function BWT (string s)
   生成s所有的循环字符串
   将这些字符串按字典序排序
   返回最后排序后字符串的最后一列
 

Burrows–Wheeler变换的逆过程

前面的next数值记录了某个循环字符串向右移动一位之后的字符串在排序之前的位置。知道next之后很容易恢复原字符串。

下面的伪代码提供了一个逆过程的朴素实现(输入字符串s为原过程之输出)：

 function inverseBWT (string s)    
   生成length(s)个空串
   repeat length(s) times
       将字符串s的第i个字符插入第i个字符串的串首//第一次插入的为空串
       将length(s)个字符串按照首字母排序
   返回结尾为EOF的行

外部链接

COS 226 Programming Assignment,Burrows-Wheeler Data Compression Algorithm（英文）