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为输入的字符串:

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

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

Burrows–Wheeler变换的逆过程[编辑]

寫成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

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:
        x = indexlist[x]
        s = s + r[x]
    return s

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)

参考资料[编辑]

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

外部链接[编辑]

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