块排序压缩的数学原理

Time: 十一月 14, 2009
Category: Programming practices

也叫 BWT 转换,严格来说不属于一个压缩算法,是压缩领域的辅助技术,BWT 的目的仅仅是将信息转换得更加适合压缩而已。BWT 巧妙的地方在于,只要精心设计,除了增加少额的计算量外,没有任何其他的开销。因为他的输出仅仅是将原有字符的排列顺序作了特定的安排

为了描述方便,举个简单点的例子,比如,即将处理的序列是 S = abraca ,S 的长度 N = 6,将 S 向右旋转一位,S 的末尾移动到 S 的首部,形成一个新的序列 S’ ,再将 S’ 向右移动一位再次产生新的序列 S”,重复这个步骤,直到得到一个 N*N 的矩阵 M,对 M 按字典排序,得到 M’ ,取矩阵 M’ 的最后一列作为输出,如下:

注意上面红色的 # 号,是一个辅助转换的结束符号,目的是为了标记原序列 S 属于 M’ 中的第几行,这个很重要,如果不使用结束标记符,就必须另外维护一个索引值,排序结果也会不一样,但是最终还原的字符序列是相同的。

逆转的过程更有意思,也非常简单,我们知道输出的序列 L=#rcaaba,L是表示矩阵 M’ 的最后一个序列,同理,F 是第一个,逆转的过程是从 L 恢复到整个 M’ 的过程,#号所在的 Row 就是原字符序列 S,因为 M’ 经过字典排序,自然 F 也是有序的

定理:对于包含 N 个字符的任意序列 S,按照 BWT 规则产生矩阵 M,对 M’ 进行字典排序得到 M’,假设 F 是 M’ 的第一列字符,L 是 M’ 的最后一列字符,若 F 是有序的,则 L 是唯一的。

从转换的过程我们知道,对于矩阵 M’ ,每行,每列所包含的元素都是相同的,也就是说,不考虑字典序,F 与 L 中的所有字符都存在一一对应的关系 T,在这里 L=#rcaaba ,所以 F=aaabcr#,则 T={6,5,4,0,1,3,2}

T 的计算过程有个需要注意的地方,L 与 F 中不是每个字符都是唯一的,也许有 N 个字符 value 相同,但是其实 index 不一样,L 中相同字符的索引顺序在 F 中也是完全相同的,也就是说,对 a,L=#rcaaba,F=aaabcr#,T 不可能是 {6,5,4,1,0,3,2},我们可以证明一下,为什么会这样。假设 ai 是 L 中所有字符 a 产生的一个序列,i=1,2,3,4……,i 表示 L 中出现该字符的序列,比如 a1 是 L 中第一个出现的字符 a,a2 是 L 中出现的第二个字符 a,以此类推,同理,对 F 中所有字符 a 产生的序列为 a’i,i=1,2,3,4……。能够证明,a’i 就是 ai

假设 pi 是序列 S 中紧接着 ai 后面的字符,对与 M’ 中任意一个最后字符为 ai 的行 r,则 r 的首位一定是 pi,不失一般性,取 L 中的 a1 a2,所在的行分别是 m n,而 m n 行的首位是 p1 p2,因为 index(a1) < index (a2) ,明显 index (p1) < index (p2) ,对于 F 中的 a’i,因为 a’i 的值是相同的,按照字典序,实际上排列的是 pi 而不是 ai,亦即 a’ipi=aipi,所以 a’i=ai,证毕。

有了关系 T,从 F 中得出原字符序列就变得相当容易了。S[N-1-i] = L[Ti[I]]  i=0,1,2,……,N-1 ,其中 I 就是结束符 # 在 L 中的次序,T0[x] = x ,  T(i+1)[x] = T[Ti[x]],本例中 I 是 0,所以有 S[N-1-0] = L[T0[I]] = L[I] = L[0] = F[6] = #,S[N-1-1] =  L[T1[I]] = L[T[0]] = L[6] = F[2] = a,最后 S0 = a,整个序列就出来了。

Michael Burrows 和 David Wheeler 确实很聪明,独辟蹊径完全从另外一个角度来思考压缩的过程,对算法设计的思考有很大的帮助,要学会如何寻找突破口。有没有想过,多阶 BWT 变换又会是什么情况?

参考文献:

^ Burrows M and Wheeler D (1994), A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation

Leave a Comment