（计算机软件与理论专业论文）快速有限阶burrowswheeler变换的算法设计及应用.pdf

中山大学硕士学位论文 快速有限阶b u r r o w s - w h e e l e r 变换的算法设计及应用 快速有限阶b u r r o w s w h e e le r 变换的 硕士生：李舒雯 指导教师：农革 算法设计及应用 计算机软件与理论 摘要 本文基于对一种新的s t 逆变换算法的分析，实现了快速s t 正向变换算法， 并将两者结合实现了一个快速有限阶b w t 算法。此算法实现的目的在于验证新 逆s t 算法的可行性及其能否保持s t 正向变换相对于b w t 的时间复杂度优势， 同时使新的逆s t 算法能够实际应用。s t 是针对b w t 正向变换中超线性排序时 闻复杂度改进的一个b w t 变种。现存逆s t 算法由于采用了哈希表而导致了较 高的复杂度，影响了s t 正向交换带来的优势。新的逆s t 算法的提出使得s t 正 向变换相对于b w t 的优势能得以保持。因此要验证新的逆s t 算法的理论意义， s t 正、逆变换的快速实现尤为关键。实现s t 正向变换的主要难点是如何在线性 的复杂度内实现正向变换中的排序操作。本文采用了一种改进的基数排序来解决 此问题。为了验证新的逆s t 算法的可行性，本文对所实现的快速有限阶b w t 算法与无限阶b w t 算法进行对比实验，在c a l g a r y 数据集上进行验证和性能分析。 实验数据表明新的快速有限阶b w t 算法可在保持压缩率为无限阶b w t 算法的 9 9 8 3 的同时，提高运行速度6 9 0 8 。显示了新的逆s t 算法在高性能无损数据 压缩应用中的潜力。 关键词：有限阶b v r r ，逆变换，算法设计，性能评估。 中山大学硕士学位论文 快速有限阶b u r r o w s - w h e e l e r 变换的算法设计及应用 f a s ta l g o r i t h m sf o rt h el i m i t e d o r d e r c o n t e x tb u r r o w s w h e e l e rt r a n s f o r m ：d e s i g n s a n d a p p l i c a t i o n s s o f t w a r ea n dt h e o r e t i e a lc o m p u t e rs c i e n c e n a m e ：s h u w e nl i s u p e r v i s o r ：g en o l a g a b s t r a c t w es t u d yi nt h i st h e s i st h ep r o b l e mo f f a s ll i m i t o d - o r d e rc o n t e x tb t m o w s - w h c e l e rt r a n s f o r m 0 3 w t ) ，w h i c hi sa l s ok n o w n 勰t h es o r tt r a n s f o r m ( s d t h es ti sav a r i a n to f t h eb w t w i t ha 搿m i a ls o r t i n gs c h e m eu s e di nt h ef o r w a r du a n s f o r mt oa c 陆c v cas p e e d 印g a i no v e i t h el a t e r h o w e v e r , t h ee x i s t i n gi n v e r s es t0 s t ) a l g o r i t h m sl l s eah a s ht a b l ef o rc o m p u t i n gt h ei n v e r s i o n , w h i c hm a k e si tf a rm o r c o m p l e xt h a nt h ei n v e r s eb w ta n do i j c t st h eb e n e f i t6 m u s i n gt h e f o r w a r ds t s o m en e wi n v e r s es ta l g o r i t h m sw g t cp r o p o s e dr e c e n t l y a sar e s u l t , t h e r ei sa d e m a n di np m c i i f o rmt oe v a l u a t ei t sv 础o m m c ev s t h eb w t , w h i c hm o t i v a t e do u i s t o d yi n t h i st h e s i s f i r s t , af a s tf o r w a r ds ta l g o r i t h mi si m p l e m e a t e du s i n gm i m p r o v e dr a d i xs o r t i n gf o r v e r i f y i n gt h ef e a s i b i l i t yo ft h en e wi s ta l g o r i t h m n e x t , t oe v a l u a t ot h ep m m a n 瞄o f p 蒯s o l u t i o n su s i n gt h ei s ta l g o r i t h mi ne o m p a r i s o uw i t ht h a tu s i n gt h eb w ta l g o r i t h m , w ei m p l e m e n taf a s tl i m i t e d - c o n t e x tb w t a l g o r i t h mb yc o m b i n i n gt h ef a s tf o r w a r ds ta n dt h e u e wi s t f u r t h e r , aa e r i e so f e x p e r i m e n t sa l ec a r r i e do u tt o 酬u 如t h ep e r f o r m a n e 嚣o f t h e s et w o k i n d so f a l g o r i t h m sw i t ht h e e c o n l i g u r a t i o or u n n i n g0 1 1t h ec a l g a r yc o r p u s t h ee x p e r i m e n t a l r e s u l t ss h o wt h a t , t h ee o m p r e s s i o os o l u t i o nu s i n gt h el i m i t d l - o r d e rb w tc ma c h i ma l la v e r a g e c o m p r e s s i o nr a t i oo f9 9 8 3 e st h a tu s i n gt h eb w ta l g o r i t h m , m e a n w h i l e , g a mma v m g e i n c r e a s ei ns p e e do f 6 9 0 8 o v a t h el a t e r n - i sd e m o m m a t 目t h eg r e a tp o t e n t i a lo f t h en e wi s t a l g o r i t h m s f o r b u i l d i n g h i g h - p e r f o n m a c e l o s s l e s s c o m p r e s s i o n a p p f i c a t i o m k e yw o r d s ：l i m i t e d - o r d e rb w t , i n v e r s er e f o r m , a l g o r i t h md e s i g n , p 耐研m a 嘲 i i 中山大学硕士学位论文 快速有限阶b u n 口w s - 、 i 钟l 玎变换的算法设计及应用 1 1 数据压缩概述 第1 章引言 数据压缩是现代计算最重要的领域和工具之一。从获取数据到c i ) - r o m ，从 编码理论到图像处理，现代计算的许多层面都依赖于数据压缩。信息论之父 s h a n n o n 提出的“信息熵”概念是所有数据压缩算法的理论基础 1 从本质上 讲，数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理正是用数 学方式精确地描述了信息冗余的程度。利用信息熵公式，人们可以计算出信息编 码的极限，即在一定的概率模型下，无损压缩的编码长度不可能小于信息熵公式 给出的结果。这样数据压缩就有了一个理论追求的极限。我们可以注意到，这里 提到的理论极限是针对于无损压缩而言的。然而现实应用中，数据压缩算法可以 分为通用数据压缩和多媒体数据压缩。其中多媒体数据压缩属于对特殊数据的专 用压缩算法，由于目标数据对于压缩损失具有一定的容忍度，通常会采用有损数 据压缩，例如视频，语音等。而通用数据压缩通常属于无损数据压缩，也正是本 文研究所属的领域。它原先主要应用于文本领域，后来随着计算机应用的日益广 泛，也开始应用于一些其他数据，例如医用图象的无损压缩。衡量压缩算法有三 个主要性能指标：1 压缩率，即指压缩对象被压缩的程度，被压缩程度越大， 压缩率越高；2 压缩质量，指压缩对象被解压缩后，相对于压缩前信息损失的 情况，损失越小，压缩质量越高，我们可以很直观地得知在压缩质量的指标上， 无损数据压缩通常会优于有损数据压缩；3 压缩与解压缩速度，这个指标则与 压缩算法的实用意义密切相关。在本文后面的内容中，将会多次用到相关的性能 指标来分析一些压缩算法的优点与劣势。 1 2 通用数据压缩算法的分类介绍 通用数据压缩又可以分为三种基本类型：基于统计模型的压缩算法，基于字 典模型的压缩算法以及后来新兴的基于b w t ( b u r r o w s - w h e e l e rt r a n s f o r m ) 的 第1 章0 i 苦 压缩算法。 1 2 1p p m 系列算法 基于统计模型的压缩算法以p p m ( p r e d i c t i o nb yp a r t i a lm a p p i n g ) 2 系 列的算法为代表，它是算术编码和部分匹配预测模型的结合。它使用了一系列的 概率预测模型。这些模型通过对源数据串中已经出现的符号进行分析，来得出即 将会出现的下一个符号的各种可能性的概率预测。然后在此基础上应用算术编 码。这种压缩算法的显著优点是压缩率很高，可以成功逼近信息熵的极限。但是 它的一个致命缺点则是复杂度过高，使得实现起来所需运行时间过长，实用意义 不大，所以并没有得到广泛的应用。后来出现了许多p p m 的变种，大多是集中于 对p p m 算法进行复杂度的降低。其中2 0 0 0 年，美国的m i c h e l l ee f f r o s 在i e e e 上发表了一篇文章 3 ，提出了一种p p m 算法的改良算法，可以达到0 f ) 的复杂 度并维持较好的压缩率。 1 2 2l z g 系列算法 基于字典模型的压缩算法则以l z we 4 系列算法为典型，这系列算法起源于 一种将字典模型应用于压缩编码的l z 编码。它以词的方式来处理源串，将长度 不同的符号串编码成一个一个新的“单词”，它们形成了一本“词典”的索引。 若单词的码字短于它所代表的短语，就达到了数据压缩的目的。后来，又有了一 系列的改进算法，例如l z 7 7 5 和l z 7 8 6 ，再到l z w 算法。这系列算法相对于 p p m 系列算法而言，对于可预测性不大的数据具有较好的处理效果，它在图象压 缩上所取得成就更大。它的显著优点是逻辑性强，易于硬件实现，压缩和解压速 度快。但是它只对于数据流中连续重复出现的字节和字串具有很高的压缩比。我 们熟悉的p k z i p 、w i n z i p 、w i n r a r 、g z i p 等压缩工具以及z i p 、g i f 、p n g 等文件 格式都是这系列算法的受益者。 2 1 2 3 基于b w t 的压缩算法 这类压缩算法与以往所有通用压缩算法的设计思路都迥然不同。它的核心部 中山大学硕士学位论文快速有限阶b u r r o w s - w h e e l e r 变换的算法设计及应用 分并不是在压缩过程本身，而是从另一个角度来对数据压缩进行各项性能的提 高。它先将需要压缩的源文本进行一次b u r r o w s - w h e e l e r 变换 4 ，该变换把源 文本的字符进行了重排列，变换后的文本长度并没有缩短。然而和源文本对比， 变换后的文本中，相同字符排列在一起的概率通常能得到很大的提高，因此能更 好地被一些快速简单的局部适应算法所压缩。比如用行程长度编码和前移编码后 再加上哈夫曼编码或算术编码。这种压缩方案已经被证实可在l z l r 系列算法的速 度下达到p p m 系列算法的高压缩率。当然，b u r r o w s - w h e e l e r 变换是可逆的在 解压缩得到源文本的b u r r o w s - w h e e l e r 变换输出后，能将其再进行一次 b u r r o w s - w h e e l e r 逆变换，从而得到源文本的内容，完成真正意义上的解压缩。 前面已经介绍过，p p m 系列算法由于其使用了部分匹配的预测模型，所以只对于 可预测性较大的数据有很好的处理效果。而l z w 系列的算法在文本压缩领域中只 对于数据流中连续重复出现的字节和字串具有很高的压缩比。可见压缩算法的成 功应用范围都会因进行压缩的源文本的固有属性而受到局限。而基于b w t 的压缩 算法则通过b u r r o w s w h e e l e r 交换及其逆变换来一定程度上改变源文本的固有 属性，在提高压缩的性能之外，也拓宽了一些原有压缩算法的成功应用范围。基 于b w t 的压缩算法因其卓越的性能表现得到了广泛的应用，它在开放源码的压缩 工具b z i p 中获得了巨大的成功，b z i p 对于文本文件的压缩效果要远好于使用l z w 系列算法的工具软件。基于b 耵的压缩算法还被应用在了d n a 序列压缩 8 ，e c g 信号压缩 9 ，通信数据压缩 1 0 和图像压缩 1 1 等实践领域。然而，由于它的 核心部分一b w t 变换中包含了大量的排序操作，从而造成了较高的时间复杂度， s t 变换则是针对这一问题提出来的b w r 的一个变种。但是s t 在较好地解决了b w t 排序时间复杂度的问题后，又带来了新的问题，本文正是在此基础上进行了研究， 解决了s t 中产生的新问题，对b 霄t 进行了较完整和系统的优化。 第2 章b w t 和s t 第2 章b w t 和s t 2 1 符号和名词介绍 本小节中列出本文将要用到的符号及一些名词的定义 s ：用于表示长度为r 的源文本，一个由字符组成的一维行向量。 s = 【而屯x 3 一，$ 】。其中$ 代表大于与任何源文本字符的文本结束符。 m ：由源文本轮转后得到的n x n 字符矩阵。下一节中有详细定义。 m ：将m 的所有行按照字典顺序排序后得到的m x n 矩阵。 肘。；将m 的所有行根据前列按照字典顺序排序后得到的n x n 矩阵。 f ：一维n 元行向量，为m 的第- - y j 的转置。 三：一维m 元行向量，为肘的最后一列的转置。 磊：一维靠元行向量，为膨。的第一列的转置。 厶：一维n 元行向量，为膨。的最后一列的转置。 i n d e x s ：源文本s 在m 或m 女中的行号。 p ：将工中的每个元素映射到其在f 中的位置的一个行向量。 q ：将f 中的每个元素映射到其在工中的位置的一个行向量。 最：l k 中的每个元素映射到其在e 中的位置的一个行向量。 g ：将中的每个元素映射到其在中的位置的一个行向量。 前继；s 中字符一。为字符的前继，字符为字符的前继。( 循环定义) 。 后继：s 中字符为字符i 。的后继r 字符丑为字符的后继。( 循环定义) k 阶上下文：s 中一个字符的后k 个字符称作这个字符的k 阶上下文。( 循环定 4 中山大学硕士学位论文快速有限阶b u n o w s - 、v i l c e l c r 变换的算法设计及应用 义) 当l f - n - 时，也称为无限阶上下文，m 中的每一行的前 j 个字符都是这 行最后一个字符的无限阶上下文。 前继列：彳列中的每一个字符都是b 列对应位置上的字符在源文本中的前继，则 彳列是雪列的前继列。 2 2b u r r o w s - w h e e l e r 变换及其逆变换的介绍 2 2 18 w t 变换的原理 b w t 转换的核心思想是对源字符串轮转后得到的字符矩阵进行排序和变 换。其具体步骤如下：1 ) 构造一个n x n ( 为输入源文本s 的长度) 的矩阵m ， 矩阵的第一行等于s ，从第二行开始，每一行都是将上一行循环左移一位所得， 直到第拧行。我们可以发现，将第嚣行再循环左移一位，又会得到第一彳亍的s ， 即到第n 行为止，刚好完成一次对源字符串的轮转。2 ) 对矩阵膨的所有行按照 字典顺序进行排序，第一列的排序权重最大，其次第二列，第三列，直至最后一 列，得到膨。3 ) 将肼的最后一列的转置和s 在肘中的行号i n d e x s 这个二元 组作为s 的b w t 变换的输出。 下面以s = 1 6 bcbbc 口$ i 为例说明： 用s 所有的循环移位变换构造矩阵肼： m = b b bc cb b b bc c a 口$ $ b cb bb bc c a 口$ $ b bb bc bc c口 口s $b bb bc cb bb a$ $ b 6 b bc cb bb bc c口 对m 所有行按字典次序排序( $ 小于所有其他字符) 得到m ： 5 第2 章b w t 和s t m = a$ bb b b bc bc c a cb $ b bb ca cb a$ b b $b bc bc cb $b bc b b c a bc a$ bb bc bc a$ cb $b b b bb c a 将矩阵肘。的第一列的转置标为f ，。最后一列的转置标为上。则 ，= k b b b bc c $ 】，三= kc $bb bb4 】。此例中i n d e x s 可 明显得出为 3 。所以s 的b w t 变换的输出为 ( ，i n d e x s ) = c $ b b b b a 1 3 ) 。 通过上面的例子，我们可以更直观地得出b w t 的两个性质： 1 ) 源文本s 进行了b w t 变换后，文本长度并没有缩短，没有起到压缩的 作用，但是对s 重排列得到的中，相同字符排列在一起概率却得到了很大的提 高。因此能更好的被一些简单快速的局部适应压缩算法处理，达到更高的压缩 率。 为什么三中相同字符排列在一起的概率能够提高呢? 实质上这是由b w t 变 换中的排序机制所决定的【7 】。换个角度看，b w t 变换中的矩阵排序可以看成是 对最后一列的字符按照它们的无限阶上下文进行排序。这样的排序会将源文本中 所有位于相同字符串前的字符排列在一起。以英文中经常出现的单词t h e 为例， 当所有的循环位移行排好序后，所有以h e 开头的行肯定都会排列在一起，而这 些行很大概率上都会以”t 结尾，这样，中的某个字段内就会高概率的出现t ， 中间夹杂一些英文中同样后带h e 的字母，例如s 。这样的性质对于所有单词都 同样适用。因此b w t 变换能够提高源文本中相同字符排列在一起的概率。 2 ) 矩阵肘的每- n 的组成内容都相同，都是源文本的不同排列。所以，可 以通过对进行排序得到。而且中每一个字符都是f 中对应位置字符在源串中 的前继。 而我们又知道源文本在m 中的行号，即是知道源文本最后一个字符在中 6 中山大学硕士学位论文快速有限阶b u n o w s - w h e e 百变换的算法设计及应用 的位置。因此可以通过输出的工 i n d e x s ，用找前继的方法，以源文本结束符为 起点，来推出源文本。b w t 的逆变换就建立在以上的思想基础上。 2 2 2b t r f 逆变换 b w t 变换是可逆的，这样才决定了它可以应用与压缩算法领域。当源文本 经过b w t 变换后，再被一些快速简单的压缩算法压缩，再解压后，就只会得到 源文本的b w t 变换的输出。这时就需要将解压出来的文本再进行一次b w t 逆 变换，以恢复出源文本。 b w t 逆变换的思想很简单，在上一小节中已经给出，它的实现步骤如下： 它首先通过对工排序得到，。然后遍历l 和f 构造一个行向量p ，户记录了中 的每个元素在，中的下标，且保持了相同字符之间的的相对次序不变，以便在源 文本的恢复过程中，能对当前已恢复的字符查找它的前继。最后，从源文本的最 后一个字符开始，对源文本进行恢复，源文本的最后一个字符可以直接从工的第 i n d e x s 位获得，然后通过向量p 得到这个字符在f 中的位置，那么的对应位置 上的字符便是这个字符在源文本中的前继了，这样就恢复了倒数第二个字符，再 通过将倒数第二个字符映射到f 中来找倒数第三个字符，直到恢复出整个源文 本。 其中存在一个相同字符的相对次序问题，这里说的三中的相同字符，当放在 整个源文本的环境中来说时，其实是不同的，它们位于源文本的不同位置，有着 不同的前继字符。如上- - 4 , 节中的示例中，l ：【cc$bbbb4 】，其中 有4 个扩，放到整个矩阵m 中来看，我们就可以分辨，三中的第1 个6 - 是源文 本中的第4 个字符，第3 个6 t ，它的前继为一。l 中的第2 个6 - 则是源文本中 的第1 个字符，第1 个b ，它的前继为t $ t 由于尸只是通过对三和f 进行一次 简单的遍历得来，那么对于中相同的字符，p 如何能保证找到其在，中的正确 位置呢? ，如果不能定位到其在，中的正确位置，就不能找到这个字符在源文本 中的真正前继。实质上这是由b w t 排序机制所决定的，也可以说是b w t 变换 的固有属性 7 】，矩阵m 。的第一列和最后一列中，相同字符的相对次序已经得到 了保持，可是这一点在b w t 被提出的学术报告【7 】中并没有给出证明，我们可以 7 第2 章b w t 和s t 先以上面提出的两个b 在f 中的位置来进行验证，从整个矩阵肘来看，中的 第1 个b 也是源文本中的第3 个b ，f 中的第2 个一b 也是源文本中的第1 个l t b 。 这两个相同字符b 的相对次序在和f 中是保持不变的，对于上例中任意其它 两个相同字符也同样可以得到验证。 下面对与f 中任两个相同字符的相对次序相同的性质给出一个一般化的 证明： 1 假设在m 的第一列中，有任意两个字符m f ，i = m d ，1 】， ( 1 i 歹群) ，根据b w t 的排序机制，它们在膨的f 中的相对 z m g ，2 ：月】和m 【，2 ：”】的大小关系决定的。 2 由m 的定义可知，m i ，1 - 与m i + i ，n 】，m l ，1 - 与m b + i ，h 】每对表示 的都是源文本中的同一字符。 3 根据b w t 的排序机制，同样可知字符m 【f ，1 1 和m ，l 】即m i + l ，l 】和 m + i ，月】在m 的l 中的相对次序又是由m i + i ，l ：n 一1 】和 m j + i ，l ：n l 】的大小关系所决定的。 4 由m 的定义可知， m i + i ，l ：n l 】- m 【f ，2 ：n 】， m j + i ，1 ：以一l 】- 肘【，2 ：n l 5 因此，任意两个相同字符的相对次序在f 和中是不变的。即是可 以通过向量p 找到每一个字符的正确前继。 b w t 逆变换的伪代码如图2 1 ： 中山大学硕士学位论文快速有限阶b u r r o w s - w h e e l e r 变换的算法设计及应用 图2 - ib w t 逆变换算法 2 3b u r r o w s - w h e e l e r 变换的复杂度问题及应对( 包括应用于b w t 排序中的各种s u f f i xa r r a y 算法复杂度) 分析可知，b w t 逆变换只需d ( ) 的时空复杂度。然而正向变换中，由于 包含了大规模的排序操作而造就了算法较高的时间复杂度。假如采用通用排序 方法例如快速排序，会达到最坏情况下o ( 2l o 鼬) ) 的时间复杂度，这样会很大 程度地影响整个压缩系统的压缩速度。这一问题激发了许多从不同方面来降低 b w t 变换中的排序复杂度的研究 1 2 1 8 】。其中较常采用的技术是利用后缀树 【1 3 】，后缀数组【1 4 】以及它们的一些变种【1 5 】。这些研究都取得了较好的结果。其 d p 1 s 中采用的后缀列表技术更是将b w t 正向变换中的排序时间复杂度降低到 了最坏情况下d 【l o g j 的水平。然而s c h i n d l c r 在【1 2 ，1 6 】中提出了一种不同与 以前所有研究的方法，简称为s t ( s o r tw a n s f o r m ) 它提出了有限阶上下文的概 念，将b w t 中的排序操作改成了只对有限阶上下文排序，从根本上减少了b w t 的排序工作量来降低时间复杂度。本文正是在这一改良变换的基础上做的研究， 下一节会较详细地介绍s t 变换。 9 第2 章b w t 和s t 2 4s o r t r 变换( s o r tt r a n s f o r m ) 及其逆变换的介绍( 包括原 理及存在的问题) s t 1 2 ，t 6 1 是b w t 众多变种中较优的一个。它采用对源文本轮转矩阵材进 行有限阶上下文伙阶) 排序来提高整个变换的速度。直观说来，就是只对肘按照 其前k 列进行字典排序来减少b w t 中大规模的排序操作。s t 变换的排序采用一 种两级优先权的排序。它首先对肘的所有行按照它们的前k 个字符进行排序， 当任两行的前k 个字符相同时。则它们的相对次序由它们在m 中的相对次序决 定。而且这种对k 阶上下文的排序可以采用基数排序法来实现，所需的时间复杂 度均仅为o ( k n ) ，从而又能进一步提高算法的性能。 可是人们不禁会提出质疑，当只采用有限阶上下文排序后，会不会影响到 b w t 变换后带来的高压缩率呢? 已经有实验结果对这个问题给出了回答。文献 1 6 q ，用4 阶的s t 和b w t 进行了对比，用它们加上相同的后续压缩处理算法， 在标准压缩数据集c a l g a r y 上进行了实验，结果表明二者的压缩率非常接近。也 有其它的实验表明当s t 的阶数增加过了一定数值后，将不能再显著增加压缩率。 s t 进行了k 阶上下文排序后，仍然以吖。的最后列的转置厶和i n d e x s 作为 输出。对2 2 1 小节中的例子进行2 阶s t 变换，即是对m 的所有行按前两列进 行排序，得到矩阵m ，： m 2 = a$ 6b b6 bc bc c口 cb $b bb cb c a b b a$ $b bc bc cb bc sb c a bb bc a$ b b bc a$ bc $b cb b b b b c a 输出为也，i n d e x s ) = c $ c b b 6 b a 1 2 ) 。 然而，正是由于s t 的核心思想一有限阶上下文，决定了s t 的一个固有属 性：每个有限阶上下文不一定是唯一的。而b w t 中采用的无限阶上下文都是唯 1 0 中山大学硕士学位论文快速有限阶b u r r o w s - w h e e l e r 变换的算法设计及应用 一的。因此s t 才需要采用二级优先权捧序机制，而这种排序机制使得原来的 b w t 变换的一个重要固有属性在s t 变换中不再存在，即是相同字符在，和三中 的相对次序不能再保持不变，从上例中我们可以验证工中的第3 个b 和第4 d 6 的相对次序在，中发生了变化。用前面证明b w t 中相对次序得到保持的方法证 明s t 中的这个例子，f 中这两个字符t l b 的相对次序是由m 1 4 ，1 ：2 i - 6 ，c 和 m 【5 ，l ：2 】_ t 6 ，c t 所决定的，而由于这两个2 阶上下文相同，则它们间的相对次序 由它们在m 中的相对次序决定，即是源文本中的第2 个t6 在源文本中第4 个6 前。而在工中，这两个6 t 的相对次序是由m 【6 ，1 ：2 】一c ， l 时，原理 也是一样的。定义两个长度为一的数组，口。这两个数组的每个元素可以容纳 一个k 阶上下文，且都初始为空。然后从l 阶开始迭代k 次。每次迭代都会使所 还原的上下文阶数增加l 。每次的操作为： 1 研玎= t k f qo a i ( 审表示字符串连) 2 将口中所有元素按字典次序排序后存入一中。 还原所有k 阶上下文的时间空间复杂度都为0 ( 埘) 。 而对于源文本的还原则比较棘手，s c h i n d l e r 在其文献 1 2 。1 6 q h 提出了一种基 于哈希表的策略，并给出了当k 2 时的详细算法。但是对于更高阶的情况却只 做了十分粗略的描述。没有具体给出如何统一高效地对任何k 来构造哈希表。我 们知道当k 较大时，基于哈希表的算法虽然理论上比较简单，但在技术层面上会 十分复杂，而且时间空间复杂度也较大，对于较高阶的逆s t ，硬件实现起来也 第2 章b w t 和s t 会很困难。这种缺点在算法在实时磁盘解压和由硬件实现解压 1 9 】的应用中会表 现得尤为严重。因此，虽然s t 成功地在不影响压缩率的情况下，降低了b w t 变换的排序时间复杂度。但目前对逆s t 问题的解决方案比b w t 逆变换，效果 并不理想。 1 2 中山大学硕士学位论文快速有限阶b u w o w p w h e e l 玎变换的算法设计及应用 第3 章新的逆s t 算法 针对上一章中总结出的问题，【2 0 q b 提出了一种新的逆s t 算法，新算法采 用和b w t 逆变换相同的矩阵方法来实现源文本的还原过程。这种算法能在 o ( 拼) 的时空复杂度内完成。【2 1 q b 继续对此新算法进行了优化，算法优化后能 在。岍) 的空间复杂度和d ( l o g 七) 的时间复杂度内完成。使得s t 正向变换对于 b w t 的优势能得以保持。 本章对这种新的逆s t 算法的设计和优化过程进行了回顾和分析。后续章节 中实现的快速有限阶b w t 算法正是采用了这种新的逆s t 算法作为有限阶b w t 逆变换的算法。同时这种新的逆s t 算法也是本文后续章节中实验的验证对象。 3 1 算法介绍及分析 新的有限阶b w t 逆变换仍然由两部分组成一七阶上下文还原和源文本还原。 本节主要详细介绍的是新算法最初阶段的主要突破点一源文本还原部分，对于k 阶上下文还原，主要对其实现原理进行分析以助于理解后面小节中介绍的针对k 阶上下文还原进行优化的内容。 3 1 1k 阶上下文还原 这里所说的k 阶上下文还原实质上是指根据正向变换的输出厶还原出m 。的 前_ | 列的过程，即是要还原出已经排好序的所有k 阶上下文，我们将肘。的前k 列称作k 阶上下文矩阵，这种所有k 阶上下文的有序捧列才会和厶中的元素一 一对应，才能用来在源文本恢复过程中找前继和判断k 阶上下文是否相同。新算 法中的k 阶上下文还原部分采用和逆s t 一样的原理，在第二章中介绍s t 时已 经给出了简单的描述：定义两个长度为一的数组爿，风这两个数组的每个元素 可以容纳一个阶上下文，且都初始为空。然后从1 阶开始迭代k 次。每次迭代 都会使所还原的上下文阶数增加l 。每次的操作为： 1 3 第3 市靳的逆s t 算法 b i l l = 厶【f 】0 4 【f 】。】( o 表示字符串连) 将b 中所有元素按字典次序排序后存入a 中。 3 1 2 源文本还原 在新的逆s t 算法中，源文本还原部分采用与无限阶b w t 逆变换一致的矩 阵方法。从源文本的最后一个字符开始，对源文本进行恢复。源文本的最后一个 字符可以直接从厶的第i n d e x s 位获得，然后找以这个字符开头的k 阶上下文在 m 。中行数，那么丘的对应位置上的字符便是这个字符在源文本中的前继。如果 以某个字符开头的k 阶上下文并不是唯一的，那么所有相同的k 阶上下文中每个 都会有一个对应的厶中字符。由于这些相同的k 阶上下文在肘。中已经保持了它 们在m 中相对次序，那么它们所对应的l 中的字符也应该保持了它们原来在肘 的最后一列中的相对次序。而对于m 的最后一列中的字符，如果采用由尾到头 的还原次序，除了结束符$ 外，排在越靠后的字符应该被越早还原。所以此 时我们选择这组相同的k 阶上下文中排在最后的那个所对应的t 中的字符作为 前继来继续整个源文本还原过程，直到还原出整个源文本。 从前面已经还原的k 阶上下文矩阵中，能获得关于k 阶上下文相同的相关信 息，包括每个k 阶上下文是否唯一，如果不唯一，又有多少个和它相同的k 阶上 下文。由于k 阶上下文矩阵中，所有的k 阶上下文已经排好序，所以如果存在相 同的k 阶上下文，那么它们一定会排列在一起，于是又包括了每组相同的k 阶上 下文在k 阶上下文矩阵中的起始行数。在对当前已还原字符找前继时，首先判断 以这个字符开头的k 阶上下文是否唯一。如果唯一，则直接以这个k 阶上下文在 m 。中对应的厶中字符作为当前已还原字符的前继。如果这个k 阶上下文不唯一， 则根据这组相同k 阶上下文的起始行数以及它们的个数，来选择排在最后的那个 k 阶上下文，以它在m 。中所对应的厶中字符作为当前已还原字符的前继来继续 还原过程，并且把这个使用过的k 阶上下文进行标志，以便下次再找到这组相同 的k 阶上下文时，能从排在倒数第二的那个开始处理。 1 4 ! 生堂圭堂垡堡塞 堡壅壹里堕! ! ! 翌竺兰尘型竺壅垫箜苎鲨堡生墨生旦 图3 - 1 新逆s t 算法源文本还原过程 笫3 章新的逆s t 算法 整个源文本还原过程的伪代码 2 0 描述图3 1 所示。下面结合算法伪代码 对算法的详细实现进行说明。新算法中，引进瓦和q 两个向量来存储七阶上下 相同的相关信息。其中c 。用于标示每组相同的阶上下文的个数以及它们在七 阶上下文矩阵中的起始行数。g 对应| 阶上下文矩阵的每一行，q 的值如果为 0 ，则表示这一行的j i 阶上下文不唯一，且不是这组相同j j 阶上下文的起始行。q 的值如果为正，则表示这一行为第一行，或者这行的_ | 阶上下文不同于上一行， 为一组新的后阶上下文的起始行，而且从这行开始( 包括这行) ，往下连续排列 了g 个相同的后阶上下文，如果q 为1 ，则表示只有1 个相同的尼阶上下文， 即这行的七阶上下文是唯一的。简单来说，g 就是将每组相同正阶上下文的个 数存在这组上下文的起始行处，对于这组其他上下文则都标为0 。正则用于把所 有的j i 阶上下文组和厶中的每个元素对应起来。瓦中的值与厶中的每个字符一 一对应。用于表示以t 中的每个字符开头的七阶上下文所属的k 阶上下文组的 在m 。中的起始行数。瓦同样可以看成是把厶映射到e 的变量，但是它又是不同 于向量最的。通过最，厶和e 之间的元素是一一对应的，而瓦却可能是多对一 的映射。而瓦和c 。的计算则通过对阶上下文矩阵进行一次遍历来完成( 第5 行到第9 行) 。 源文本的还原从源文本的最后一个字符一t 的第i n d e x s 个字符开始，循环i 1 次，每次循环还原一个字符，对源文本的所有字符从尾到头进行还原，每次对当 前循环中还原出的中字符，寻找以它开头的七阶上下文所在组的起始行号即疋 的值( 第1 3 行) ，然后加上这组i 阶上下文的个数( g 的值) 减1 ( 第1 4 行) ， 以得到这组阶上下文中排在最后的那一个上下文的行号。厶中与这个行号对 应位置上的字符就是当前循环中还原的字符在源文本中的前继，也就是下一个循 环中将被还原的字符。然后将这组七阶上下文的个数减1 ，标志这组后阶上下文 1 6 中山大学硕士学位论文快速有限阶b u r r o w s - w h e c | e r 变换的算法设计及应用 的最后一个已经被处理过( 第1 5 行) ，以便下次再找到这组k 阶上下文时会找到 倒数第二个进行处理。 3 3 算法关键点分析一恢复源文本过程中字符还原次序问题 通过第二章中对s t 的分析，我们可以总结出造成逆s t 难度增大的主要原 因一一经过s t 的有限阶上下文排序后，f 和工中的相同字符问的相对次序可能 会发生改变，如果在逆变换中再简单地通过向量p 来找当前已恢复字符的前继， 就有可能错找到一个与当前字符相同的源文本中另一字符的前继。这样源文本的 恢复就会出现次序上的错误，可能会出现以相同字符开始的字段间的调换。因此 新算法要解决的问题就是在可以接受的时空复杂度内，消除相同字符间相对次序 的改变对源文本还原次序的影响。 我们知道相同字符问的相对次序之所以会发生变化，是由于s t 中排序采用 的有限阶上下文。因为这些有限阶上下文并不一定是唯一的，所以在排序中，如 果碰到有相同有限阶上下文的情况，必须有一种机制来决定它们之间的相对次序， s t 采用的机制是保持它们在原矩阵膨中的相对次序。下面对相同有限阶上下文 引起相同字符间的相对次序发生变化的过程做一个一股化的详细分析： 1 假设s t 的阶数为双1 茎七 u b + 1 ，七1 。 4 又因为m 【f + 1 ，l ：k l 】= 肘【f ，2 ：k l = m b ，2 ：七】= m 【，+ l ，1 ：_ i 一1 】( 根据 m 的定义) ，根据b w t 的排序机制，在m 。中m 的第f 纠行与第_ ， 1 7 第3 章新的逆s t 算法 l 行的相对次序为第，行在第i 行前。即是在中，字符m d + 1 ，月】 在字符们b + l ，n 1 之前。 5 由第2 步可得，是在中，- 字 q m ，1 】在字符m 【f ，1 】之前。这时我们 就可以看到两个相同字符之间的相对次序在，和三中发生了变化。 由上面的推理过程我们可以得出，相同字符的相对次序发生改变只有在有k 阶上下文相同时才可能发生，而七阶上下文相同是是有限阶上下文的固有属性， 有限阶上下文的概念又是s t 降低b w t 排序时间复杂度的理论基础，因此是不 可动摇的。所以要解决这个问题，必须先要获得所有豇阶上下文中是否有相同的 信息，这就要求必须要有k 阶上下文的还原。可是后阶上下文相同又不是必然会 引起相对次序发生改变。因此我们也不能通过简单判断k 阶上下文是否相同来决 定是否对p 向量中的值做对调来解决这个问题。 新的逆s t 算法从s t 的二级排序机制中获得了启发，当k 阶上下文相同时， 这两行的相对次序保持为它们在矩阵m 中的相对次序，那么这两个_ j 阶上下文 所在行的行尾字符也保持了它们在肘的最后一列中的相对次序。根据m 的定义 可知，m 的最后一列中的字符( 除了结束符$ 外) ，实际上就是由上往下的 源文本的原序排列。所以，如果我们采用由尾到头的次序还原源文本，只需要确 保在肘的最后一列中越靠后的字符，在逆变换中被越早还原，就不会出现还原 次序上的错误，因此，新算法利用了这个性质来解决在源文本还原过程中碰到相 同的k 阶上下文时，如何找到正确前继的问题。从而很好地消除了相同字符间相 对次序的改变对源文本字符还原次序的干扰。 3 1 4k 阶上下文还原原理分析 3 2 1 小节中介绍的k 阶上下文还原的迭代过程实际上就是正向变换中k 阶上下文矩阵形成过程的反向等价过程。正向变换中，根据s t 的排序机制，要 对矩阵吖的所有行按照前k 列进行排序，其中第一个列的权重最大，其次为第 二列，第三列，直到第k 列。k 阶上下文矩阵就是由m 的前k 列按照这种机制排 序产生的。我们可以用一种和s t 排序机制反向的等价的排序的过程来构造出k 阶上下文矩阵。即从权重最小的列开始排序，直到权重最大的列。结合前面给出 中山大学硕士学位论文快速有限阶b m r o w s - w h e c t e r 变换的算法设计及应用 的迭代过程进行说明： 先对正向变换的输出丘进行排序。作为k 阶上下文矩阵的最后一列一排序 权重最小的一列一一对应第一次迭代中的第一步和第二步 然后在排序后得到的列最前加上这列的前继列五作为| ； 阶上下文矩阵中权 重次小的列。由于k 阶上下文矩阵中，每一行都是源文本中相连的k 个字符，所 以为了保证构造的七阶上下文矩阵每行的字符间的相连关系，只能在前面加上当 前列的前继列。一一对应第二次迭代中的第一步。 加上丘后，后面所有已添加列再一起按照厶( 当前最大权重的列) 的大小 进行一次排序一一对应第二次迭代中的第二步。 排序后，厶又变成了疋，再在其前加上它的前继列厶继续排序过程，直到 迭代了k 次，构造出了包含七列的k 阶上下文矩阵。这个过程中，权重最大的列 只需进行最后的一次排序，权重第二的列则需要进行两次捧序，先按自身大小撵 序，后来再按加上的最大权重列的大小捧一次序，依次类推，权重最小的列要捧 七次序。以此来实现s t 的排序机制。 我们可以看到，这个k 阶上下文还原的过程似乎