BWT数据压缩

Burrows-Wheeler Transformation(BWT)压缩算法介绍 6 Burrower- Wheeler变换 在数据压缩领域最近时间一个比较有趣的发展就是1994年Michael Burrows 和David Wheeler在《A Block-sorting Lossless Data Compression Algorithm》一文中共同提出了一种全新的通用数据压缩算法。 6.1原理 与ziv 和lempel 另辟蹊径的做法如出一辙,burrows 和wheeler 设计的bwt 算法与以往所有通用压缩算法的设计思路都迥然不同。现有比较著名的压缩算法都是处理数据流模型的,一次读取一个或多个字节,BWT使得处理成块的数据成为可能。这种算法的核心思想是对字符串轮转后得到的字符矩阵进行排序和变换。考虑一般的文本应用比如文本中the这个字符串经常会被用到,经过BW转换之后,所有的t都被移动到最后并且聚合在一起,这样变换之后的字符串用通用的统计压缩模型(Huffman coding、LZ算法、PPM算法)等进行压缩就能得到更好的压缩比。 6.1.1压缩变换 为了方便阐述,我们假设输入的字符串为S=“abraca”,字符串长度N=6. 第一步:排序变换 把字符串S循环移位后得到的字符串集合组合成一个N*N的矩阵。至少有一行包含了初始的字符串,I是第一行所在的序号。例子里变换后的矩阵M如下图,I=1. 0 aabrac 1 abraca 2 acaabr 3 bracaa 4 caabra 5 racaab 图6.1 变换后的矩阵 第二步:拿到矩阵中最后一列L,例子中L=“caraab”, I=1; 6.1.2解压变换 解压变换利用压缩变换的结果L和I重新构建原有的字符串.output(L,I)=S(N) 第一步:找到转换后的排序字符串 我们首先要找到矩阵M中的第一列F,这里只要把最后一列L进行排序就能得到.例子中F=’aaabcr’; 第二步:找到每个字符的前序字符数组 首先要申明的是在压缩和解压过程中,我们并不知道矩阵M,我们有的信息只是L,F,I,需要从中构建出原始的字符串S。 考虑我们上面的例子,我们定义另外一个矩阵M’,其中M’中的每行是M中每行循环右移一位(如图6-2)。M’[i,j] = M[i,(j-1)mod N]; 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’的第一行,我们构建一个向量T,用来表示两个矩阵之间的关系,其中M’的第j行和M中的第T[j]行相同。例子中T=(4,0,5,1,2,3). 第三步:输出原字符串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]]. 6.2应用效果 如今,bwt 算法在开放源码的压缩工具bzip 中获得了巨大的成功,bzip 对于文本文件的压缩效果要远好于使用lz 系列算法的工具软件。这至少可以表明,即便在日趋成熟的通用数据压缩领域,只要能在思路和技术上不断创新,我们仍然可以找到新的突破口,以推动整个压缩技术的不断前进。 Text Compression with the Burrows-Wheeler Transform See: