关于BWT格式:

BWT 压缩算法

关于BWT格式:

BWT文件是由Blind write生成的镜像文件。Blind write 5之前的版本可以制作BWT镜像文件，同时生成BWI信息文件。

Blind write 5生成的镜像文件为B5T+B5I，Blind write 6生成的镜像文件为B6T+B6I。

在windows下可以使用WinMount打开BWT格式的文件。

BWT 压缩算法

Burrower-Wheeler变换

在数据压缩领域最近时间一个比较有趣的发展就是1994年 Michael Burrows 和 David Wheeler在《A Block-sorting Lossless Data Compression Algorithm》[13]一文中共同提出了一种全新的通用数据压缩算法，Burrows-Wheeler Transformation[5,8,10,13]。

1、原理

与ziv和lempel另辟蹊径的做法如出一辙，burrows和wheeler设计的bwt算法与以往所有通用压缩算法的设计思路都迥然不同。现有比较著名的压缩算法都是处理数据流模型的，一次读取一个或多个字节，BWT使得处理成块的数据成为可能。这种算法的核心思想是对字符串轮转后得到的字符矩阵进行排序和变换。考虑一般的文本应用比如英语文本中the这个字符串经常会被用到，经过BW转换之后，所有的t都被移动到最后并且聚合在一起，这样变换之后的字符串用通用的统计压缩模型(Huffman coding、LZ算法、PPM算法)等进行压缩就能得到更好的压缩比。

1.1、压缩变换

为了方便阐述，我们假设输入的字符串为S='abraca'，字符串长度N=6。

第一步：排序变换

我们把字符串S循环移位后得到的字符串集合组合成一个N*N的矩阵。至少有一行包含了初始的字符串，I是第一行所在的序号。例子里变换后的矩阵M如下图，I=1.

row

0 aabrac

1 abraca

2 acaabr

3 bracaa

4 caabra

5 racaab

图6.1 变换后的矩阵

第二步:拿到矩阵中最后一列

假定L是矩阵M的最后一列,例子中L='caraab'，I=1；

1.2、解压变换

解压变换利用压缩变换的结果L和I重新构建原有的字符串。output(L,I)=S(N)

第一步：找到转换后的排序字符串

我们首先要找到矩阵M中的第一列F，这里只要把最后一列L进行排序就能得到。例子中F='aaabcr'；（每一列都是原字符串的一个排列，而矩阵M是把各行按照字典序排列的，哪个每一行的第一个字符也应该是有序的。）

第二步:找到每个字符的前序字符数组

首先要申明的是在压缩和解压过程中，我们并不知道矩阵M，我们有的信息只是L,F,I，需要从中构建出原始的字符串S。

考虑我们上面的例子，我们定义另外一个矩阵M'，其中M'中的每行是M中每行循环右移一位（如图6-2）。M'[i,j] = M[i,(j-1)mod N];

row M M'

0 aabrac caabra

1 abraca aabrac

2 acaabr racaab

3 bracaa abraca

4 caabra acaabr

5 racaab bracaa

图6-2 M和M'矩阵

这里需要指出的是M'的每一行也都是字符串S的一个变换。因为M'是从M转换过来的，也就是说M'是按照第二列进行严格排序过的。对于在M'中以某字符ch开头的那些行，他们出现的相对位置也应该是严格排好序的（他们以第二个字符进行排序，而且他们的第一个字符都相等，不会影响排序的结果）。也就是说在M中以ch字符开始的行出现的相对顺序和M'中以ch字符出现的相对顺序应该是一样的。比如例子中字符串'aabrac'，　'abraca'，'acaabr'在M中的顺序是0,1,2，在M'中的顺序是1,3,4。

F和L分别是矩阵M和M'的第一行，我们按照M'的第j行和M中的第T[j]行相同构建一个向量T。向量T就可表示两个矩阵之间的转换关系。例子中T=(4,0,5,1,2,3)。

其实，我们对M'进行字典序排序，就会转化为M。转变过程仅仅是行变换。

第三步:输出原字符串S

我们可以发现F和L分别是矩阵M的第一列和最后一列，而且其中的每一行都是S的一个变换，有L[i]肯定在F[i]前面。从T的构照中我们可以得出F[T[j]]=L[j]，我们把前面的i用T[j]代替，就有L[T[j]]在L[j]之前。由假设中I是第一行的序号，那么L[I]就是最后一个字符，我们根据矩阵T依次找到字符的前序就可以构建整个初始化的字符串了。T0[x]=x，Ti+1[x]=T[Ti[x]]。

2、应用效果

如今， bwt算法在开放源码的压缩工具bzip中获得了巨大的成功，bzip对于文本文件的压缩效果要远好于使用 lz系列算法的工具软件。这至少可以表明，即便在日趋成熟的通用数据压缩领域，只要能在思路和技术上不断创新，我们仍然可以找到新的突破口。

以推动整个压缩技术的不断前进。