注：这是《数据压缩》课程的课程设计，同样是以个人独立完成。当时看了一篇文章是介绍Re-pair数据压缩算法，我觉得算法的思路很好，就是不断的迭代，每次把字符串中的最经常出现的字符对，用另一个不在当前字符串中的字符来取代。原文中提到了使用BWT和MTF变换可以提高压缩率，但原文没有做具体的实现，于是我参试将它实现。
摘要： 本文简要的介绍了数据压缩方法当中的 Re-pair 算法，该算法是一种基于字典编码的无损压缩算法， 有着较快的解码效率，但是加密过程是离线的而且耗时较久。单纯的 Re-pair 算法压缩率并不算高，不过引入 BWT 和 MTF 变换能减少信息熵，并取得更好的压缩效率。最后本文会将引入 BWT 和 MTF 变换的Re-pair 算法和其它压缩算法进行比较。
1.引言
在众多的数据压缩算法， 常见的有霍夫曼编码、 游程编码、 算术编码、基于字典的编码等，本文介绍的 Re-pair 算法是一种基于字典的编码。在基于字典编码的数据压缩方法当中，一个很著名的方法就是 LZW 算法，该算法提取原始文本文件数据中的不同符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小 [ 1 ]。从 LZW 算法的思想可以得知其能够根据输入的字符串自适应的生成字典，解密的时候也能根据压缩后的字符串自适应的生成字典，所以数据传输的过程不需要发送字典，进一步节省了空间。 在 LZW 算法中，数据的压缩过程和解压缩过程都是在线（ online）的，压缩时，它可以根据数据流的实际情况一边输入一边处理，解压过程可以根据传输过来的字符在输入的同时生成字典文件并解压，时间连续性较好。
Re-pair 算法 [ 2 ]是一个不断迭代的过程， 每次迭代会找到原字符串中最常出现的字符对，并用一个未在原字符串的字符来替换。这个过程也就会生成字典，与 LZW 算法不同的是，该字典不能自适应的生成，必须和压缩后的字符串一同发送过去才能正常的解压。 由于压缩过程一开始就需要把整个字符串输入，所以该压缩过程是一个离线的算法。 Re-pair 解压过程需要先读入字典文件，之后只要数据接收到即可进行解压，可以发现该解压过程是一个在线的算法。
和 LZ 系列算法类似，每次压缩过程，会将较长的语句用短的语句来替换。Re-pair 在每次迭代中，原来字符串中会有若干数量的同一字符对（ 2 个字符）被一个字符所替换，从而减少源字符串的长度，从而达到压缩的效果。根据这个，可以知道它的字典是定长编码的方式。 Re-pair 算法起初是由 Moffat 和Larsson 提出来的 [ 3 ]，虽然一开始就要保存整个字符串，但在现在的日益强大的电脑面前，这个已经没什么障碍了。同时该算法时间复杂度和空间复杂度都极其的低，都是 O(n) 级别的， 所以很适合在 FPGA 等资源受限的芯片上实现。 关于复杂度的分析，后面会介绍到。
BWT (Burrows– Wheeler_transform) 也称为块排序压缩， 该算法由 Michael Burrows 和 David Wheeler 于 1994 年发明 [ 4]。 该算法只改变这个字符串中字符的顺序而并不改变其字符。如果原字符串有几个出现多次的子串，那么转换过的字符串上就会有一些连续重复的字符，这对压缩是很有用的。该方法能使得基于处理字符串中连续重复字符的技术(如 MTF 变换和游程编码) 的编码更容易被压缩。
MTF（ move-to-front），它主要的原理是使用数据的“空间局部性”，也就是最近出现过的字符很可能在接下来的文本附近再次出现 [ 5 ]。 并不是所有的文本数据都有较好的局部相关性，通常情况下和 BWT 变化一起使用，因为经过 BWT变换后，可以将文本转换为局部相关性较好的序列。
2.Re-pair 算法设计与实现
在上一章里已经简单的介绍了一下 Re-pair 算法， 在这一章中 ， 主要参考了 Radu Radescu 和 Radu Mitoi 两人介绍的Re-pair 算法的实现 [ 6]， 从压缩过程和解压过程来分别具体介绍。
2.1 Re-pair 压缩过程
2.1.1 算法介绍
Re-pair 压缩算法的整体思路是：
Step 1 : 读入原字符串 s
Step 2: 寻找字符串 s 中最频繁出现的字符对 C1C2（字符对是指仅由两个字符组成的一个字符串，如 ab, ac, ca 之类）。
Step 3: 找一个不在原字符串中的字符 C3 来替换掉 s 中所有的 C1C2，形成新的 s。并将(C1C2,C3) 添加到字典中去。
Step 4: 不断的循环 step 2， step 3 直到没有重复的字符对或者没有不在原字符串出现的字符（也即是 s 中已经包含了所有字符，找不到新的字符来做字典） 为止。
举个例子，给定字符串 S = ababacabcacabbbbbd， 我们需要对其进行压缩，以下为步骤：
首先找出所有的字符对，一共有 ab, ba, ac, ca, bc, bb, bd 七个。 统计它们出现的次数。可得
可知，最经常出现的是 ab, 那么我们用不在 s 中的字符 A 来替换它， 则原字符串 变为， AAacAcacAbbbbd。 之后重新统计新的字符对次数。
| 字符对 | ab | ba | ac | ca | bc | bb | bd |
|---|---|---|---|---|---|---|---|
| 次数 | 4 | 2 | 2 | 3 | 1 | 2 | 1 |
可知，最经常出现的是 ab, 那么我们用不在 s 中的字符 A 来替换它， 则原字符串变为， AAacAcacAbbbbd。 之后重新统计新的字符对次数。
| 字符对 | AA | Aa | ac | cA | Ac | ca | Ab | bb | bd |
|---|---|---|---|---|---|---|---|---|---|
| 次数 | 1 | 1 | 2 | 2 | 1 | 1 | 1 | 2 | 1 |
我们可以发现 ac,cA,bb 的频次都是 2，那我们选择第一个 ac，用一个不在s 的字符 B 来替换，则原字符串变为 AABAcBAbbbbd. 再如此迭代下去， 可用 C 替换 bb， D 替换 BA， 最终得到字符串 AADcDCCd， 这时已经没有重复的字符对了。
最终我们得到的字典为(ab,A) ,(ac,B),(bb,C),(BA,D) 。
2.1.2 算法实现
由于算法运行过程中，需要对字符串进行频繁的修改，如果用数组的话，中间设计的字符串替换会涉及到很多 内存复制导致时间消耗较大。所以使用链表来存储输入的原字符串 S， 这里使用 STL 中的 list 来实现。字符对次数的统计，由于只有两个字符，这里使用一个二维数组 freq 来记录,freq[i ] [j] 表示字符对 ij 出现的次数。之后再用一个链表 unuse 来保存未使用的字符。 字典只需要一个 256x3 的数组 code 来存储即可。
另外， 如果文件太大的话， 一次性可能读不完所有的字符， 那么这个时候需要对原字符串进行分块，将大的字符串分为相对较小的字符串进行处理。那么对于每块字符串，都需要输出自己独立的字典和压缩后的字符串。
具体实现：
- 程序刚开始，先设定好参数：是否启用变换算法、数据块最大大小。 并将是否启用变换算法输出到文件中。
- 分块读入字符串，保存在 list a 当中 。 并初始化 freq、 unuse、 code为空。
- 依次遍历 a 中的每一个元素，将其与后一位字符作为一个字符对，在freq 相应的地方加一。并确定没有出现过的字符，初始化 unuse。
- 遍历 freq，找出值最大的数，并记录是其字符对 c1,c2. 如果次数不大于 1 或者 unuse 为空，那么跳到步骤 7
- 从 unuse 中取出第一个元素 c3， 将 c1c2c3 保存到 code 中 。 并重新遍历一遍 a 中的所有相邻元素， 如果找到 c1c2， 将其替换为 c3.
- 回到步骤 3.
- 输出字典的个数以及字典到文件中去。 输出压缩后的 S 的字符个数和 S中的字符到文件中去。回到 2 继续读下一块字符串。
2.1.3 时间空间复杂度分析
从前面一节中，因为我们使用的是链表， 添加或删除仅仅消耗 O（1）的时间复杂度。里面消耗时间最大的是每次迭代都需要遍历两次链表 a，设每一块数据的长度为 n，那么一次迭代所用的时间是 O（ n）。我们可以知道，一共不会超过 256 次迭代。因为每次迭代会使用一个字符， 256 次后肯定用完所有字符，程序也会终止的。所以压缩过程总的时间复杂度是 O(n) 。在测试过程中，程序运行时间相比其它压缩算法要稍慢。主要的原因是，它虽是 O(n) ， 但常数系数较大另外链表中的寻址也会造成一定的时间消耗。
空间复杂度上面， 可以看到它是非常省空间的， 使用链表， 只需要保存 O（n）的链表就好。另外 freq 占用空间为 256x256， unuse 是一个不超过 256 的链表， code 为 256x3 的数组。 整体占用空间非常小。 总体空间复杂度为 O（ n）。
2.2 Re-pair 解压过程
2.2.1 算法介绍和实现。
解压的算法非常易于实现，在一开始先要确定好字典，而且这个字典顺序要和压缩过程生成的字典顺序是相反的，也就是我们从字典的后面往前面来替代。对于字典中的每个记录，需要从字符串中依次还原。
具体的实现如下：
- 读入字典数目 codenum，然后根据字典数目读入字典 code。
- 读入压缩后字符串长度 len 和读入压缩后的字符串 S，保存在链表 a 中。
- 对于字典中的每一条 c1c2c3， 依次遍历 a 中每个元素， 如果其等于 c3，将其还原为 c1c2。
2.2.2 时间空间复杂度分析
显而易见， 时间上，一共要处理 codenum 次，每次遍历一遍 a。那么总的时间复杂度是 O(codenum*n), 事实上由于 codenum 不超过 256，可以近似认为其是 O(n) 的。另外空间复杂度上面，由于主要耗空间的是保存字典和链表 a，所以总的时间复杂度也不会超过 O(n) 。
3.在 Re-pair 中使用 BWT 和 MTF 变换
字符串变换通常是一种数据压缩过程的辅助技术， 无损压缩下的字符串变换不会改变原来文件所表达的信息，只是在上面基础上进行一定的变换，使之更适合用于压缩，进而提高压缩比。 由于是无损压缩，在变换之后，同样也会有个逆变换的过程来使变换后的字符串还原成原来字符串。 这里介绍的两种变换： BWT 变换和 MTF 变换，前者不改变原字符串的字符，只是稍微调整了一下各字符的顺序，使得相同的字符有更大的可能性排在一起，后者会对源字符串进行处理，会改变原来的字符串字符，它的思想是基于最后出现的通常是最近使用的。如果说字符串经过 BWT 会出现多个连续相同的字符，那么经过 BWT 的字符串再经过 MTF 会出现连续的 0。所以很多情况下， BWT 和 MTF 是相辅相成的，在 Re-pair 算法中，使用 BWT 和 MTF 做预处理，常常会得到一些好的结果。
3.1 BWT 变换
BWT 是 Mike Burrows 根据 David Wheeler 提出的变换思想， 完善并成功用户实际数据压缩的变换方法 [ 7 ]。它的核心思想是利用字符串轮换后得到的字符串矩阵进行排序和变换。作为一种无损压缩的变换，它有正变换和逆变换。
正变换过程： 以字符串 S=“ banana” 为例，其中字符个数 n 为 6。那么我们可以建立一个 n*n 的矩阵 M， 其中每行有 6 个字符，初始时候第 i 行 M[i] 表示 S 循环右移 i 个单位（ i 从 0 开始）。那么可以得到矩阵 M 如下表所示。将矩阵 M 中的各行当成一个字符串，在矩阵 M 中的各行字符串进行排序可以得到矩阵 M_sort。 其中 M_sort 的最后一列所构成的字符串即是变换后的字符串 。如表所示，变换后字符串为 T=“ nnbaaa”。另外我们看 R， R 是变换后的 M_sort各列对应之前矩阵 M 的序号。
| 序号i | 矩阵M | 矩阵M_sort | R |
|---|---|---|---|
| 0 | banana | abanan | 5 |
| 1 | ananab | anaban | 3 |
| 2 | nanaba | ananab | 1 |
| 3 | anaban | banana | 0 |
| 4 | nabana | nabana | 4 |
| 5 | abanan | nanaba | 2 |
事实上，在实现的过程中，如果每次都生成一个 n*n 的矩阵， 那么耗费的空间太大了 。 事实上， 我们只需要保留最开始的字符串即可。 之后定义一个 int数组 R， 初始化时 R[i ] =i, 之后我们对 R[i] 进行排序 。 这里我们使用 stlalgorithm 中的 sort 排序， 排序为 sort（ R， R+n, comp）， comp 是我们自定义的比较函数。最后排序的结果，假如 R[j]=k, 那么就是 M_sort 中的第 j 行（也就是所有字符串中第 j 大）是原字符串 S 右移 k 个单位得到的。最后排序得到的数组也就是上述的 R=[5, 3, 1, 0, 4 ,2] . 那么最后得到变换后的字符串 T满足 T[i ] =S[(R[i]+n-1)%n];
逆变换过程： 逆变换过程有两种方式，这里介绍一种相对速度较快的方法，仅用 O(n) 的时间复杂度。这里要求输入变换后的字符串 T，以及原字符串 S 在M_sort 中的位置， 这个位置假设为 k， 那么对应于上述的 R 会有 R[k]==0。
在该逆变换算法中 ， 需要先明确变换中的一些性质 。 我们先定义前面的M_sort 矩阵的第一列字符串为 L， 那么会有如下性质 ：
- 对应 M_sort 中的每一行， 第一个元素都是最后一个元素的下一个元素。
- L 中相同字母出现的顺序和 F 中相同字母出现的顺序相同。
有了上面两条性质 ， 以及从前面给出的 k 中得到 S 最后一位字符。 然后逐个的确定前一个字符， 直至所有的字符都被找出来。
寻找某一个字符 T[k] 的前一个字符的方法是： 首先初始化好辅助数组， K[c]表示字符 c 在 F 中出现的次数， P[c] 表示字符 c 在 F 中出现的首位置， C[i] 表示 T[i] 字符在 T 字符串的 0 到 i -1 位出现的次数。那么 T[k] 的前一个字符的位置为 C[k]+P[T[k]] 。
时间复杂度分析 ： 正变换过程初始化需要 O(n) 的时间 ， 排序过程需要O(nlogn) 时间 ， 所以总的时间复杂度为 O(nlogn) 。逆变换过程中，初始化需要O(n) 的时间 , 之后确定每一个字符的前一个字符只需要 O(1) 的时间 ， 一共要确定 n 个字符， 所以复杂度也为 O(n) ， 所以逆变换过程总的复杂度为 O(n). 可以发现， 这是个很高效的算法。
3.2 MTF 变换
前面说到 MTF（ move-to-front） 变换主要使用的是数据的“空间局部性”，最近出现的字符很可能在接下来的文本附近再次出现。
MTF 正变换变换： MTF 正变换的主要过程如下：
- 初始化一个列表（ list），列表中的字符是原字符串中所有可能出现的字符的某一个特定序列（列表中没有重复的字符出现）。
- 读入原字符串 S
- 对于 S 中的第 i 位字符 c（从前往后遍历），找出字符 c 在列表 list 中的位置 pos， 令 S[i ]=pos。将字符 c 从 list 中删除，插入到 list 的前面去。一直处理到 S 末尾。
- 输出字符串 S 为变换后的字符串
可以发现在处理的过程中， list 是动态的变换的。
MTF 逆变换： MTF 逆变换的主要过程如下：
- 初始化一个列表（ list），该列表应该和正变换初始化时候一致。
- 读入变换后的字符串 S
- 对于 S 的第 i 位字符 c（从前往后遍历），把 c 转换为整数 pos，之后在list 中找到第 pos 个字符 c1, 令 S[i ] =c1. 将字符 c1 从 list 中删除， 插入到 list 的前面， 一直处理到 S 末尾。
3.3 BWT 和 MTF 在 Re-pair 中的使用
BWT 和 MTF 在 Re-pair 中是作为一个预处理来进行的。 在本文的实现中，压缩过程为：读入字符串后，会先进行 BWT 变换，之后再进行 MTF 变换，最后才进行 Re-pair 算法压缩。 BWT 和 MTF 中的字符串长度和当前块的字符串长度相一致。解压过程则刚好逆过来：读入字符串后，会先进行 Re-pair 算法解压，之后进行 MTF 逆变换再进行 BWT 逆变换。
4.实验与测试
在本章中，会对自己实现的 Re-pair 算法以及使用了 BWT 和 MTF 变换的Re-pair 算法与其它算法进行比较并做一定的分析。
4.1 实验与测试环境
所有的测试都是在 Intel e3 1230v2 CPU， 8G ddr1600 内存上。使用的测试数据集是比较经典的 Calgary 和 Canterbury Corpora[8]。 其中 Calgary 数据集是 1987 年发布的，用来测试和与其它压缩方法作为比较。 另外使用了一些较新的数据集如 Canterbury, 以及一些其它第三方的数据集。
4.2 测试结果与分析
虽然 Re-pair 算法的解压速度挺快， 但是没有进行性能上的优化， 可能难以与其它压缩工具进行速度上的比较。所以作为压缩的算法，这里仅仅考虑它的压缩比。这里定义的压缩比为源文件的大小除以压缩后的文件大小得到的比值。 以下是不同的文件在不同压缩算法下进行的比较。其中，为了统一起见，我定义 Re-pair 算法中，分块的大小为 10000 个字符。
| Text | Re-pair | Re-pair(transform) | WinRAR | Lempel-Ziv | Arithmetic |
|---|---|---|---|---|---|
| Bib | 1.879 | 2.096 | 3.303 | 2.595 | 1.79 |
| Book1 | 1.788 | 1.814 | 2.771 | 2.092 | 2.02 |
| Book2 | 1.837 | 2.017 | 3.373 | 2.488 | 1.87 |
| Alice29 | 1.935 | 2.041 | 2.923 | 2.375 | 1.99 |
| Asyoulik | 1.836 | 1.922 | 3 | 2.438 | 1.89 |
| E.coli | 2.878 | 2.829 | 2 | 2 | 4 |
| World192 | 1.791 | 1.89 | 3.336 | 2.453 | 1.85 |
| average | 1.992 | 2.087 | 2.958 | 2.349 | 2.201 |
通过对上述文件的比较， 可以看到的是引入 BWT 和 MTF 变换的 Re-pair 压缩算法在大部分的情况下会比不带变换的 Re-pair 算法压缩率要高一些，但提升效果没有想象中那么好，而且有些文件，压缩率反而更低了，可能是原文件的局部性就很好，变换反而适得其反。
- 总结
本文实现了在 Re-pair 算法中使用 BWT 和 MTF 变换进行预处理，并得出了在大部分情况下， 引入变换能达到更好的压缩效果的结论。另外本文也有不足之处，数据块的大小的选择会对压缩效率有着比较严重的影响，但限于时间关系，没有很好的做比较， 这也是个可以改进的地方。
参考文献
[1] 百度百科–LZW 算法, http://baike. baidu.com/view/401141.htm
[2] G. Navarro, L. Russo, Re -Pair Achieves High-Order Entropy, Proc. DCC'08,p. 537 (poster).
[3] N. Jesper Larsson, Alistair Moffat, Offline Dictionary -Based Compression,Proc. DCC'99, pp. 296.
[4] Burrows-Wheeler 变换, http://zh.wi kipedia.org/wiki/BWT.
[5] MTF(Move-to-front transform) 数据转换, http://www.cnblogs.com/xudong-bupt/p/3763916.html
[6] Radu Radescu, Radu Mitoi, ON THE RECURSIVE PAIRING COMPRESSION ALGORITHM.2011.3.15.
[7] 倪桂强 , 李彬, 罗健欣, 张雪 . BWT 与经典压缩算法研究 [J]. 计算机与数字工程,2010,11:26-29+41.
[8] The Canterbury Corpus, http://corpus.canterbury.ac.nz/descriptions/
