Burrows-Wheeler变换

维基百科,自由的百科全书
跳转至: 导航搜索

Burrows–Wheeler变换(BWT,也称作块排序压缩),是一个被应用在数据压缩技术(如bzip2)中的算法。该算法于1994年被Michael BurrowsDavid Wheeler在位于加利福尼亚州帕洛阿尔托的DEC系统研究中心发明[1]。它的基础是之前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值: 在前述表格中,右邊新排序的字串,對應到左邊相同字串之下一個字串,所得到的新排序值

例如a a b r a c a d a b r在左邊的下一個字串

是a b r a c a d a b r a,而這個字串的新排序值是2

因此a a b r a c a d a b r的next值紀錄了2

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

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

寫成perl code如下:

my $x = 2;
my @next_idx = qw/2 5 6 7 8 9 10 4 1 0 3/;
my @optstr = qw/r d a r c a a a a b b/;
for(my $i = 0; $i < 11; $i++){
  $x = $next_idx[$x];
  print $optstr[$x];
}
print "\n";

執行後可得到原始字串: abracadabra

参考资料[编辑]

  1. ^ Compression comparison of BWT based file compressors(英文)。

外部链接[编辑]

COS 226 Programming Assignment,Burrows-Wheeler Data Compression Algorithm(英文)