LZ77文本压缩算法是将当前位置开始的、未知长度的文本数据与已经扫描过的文本数据进行匹配，查找到合理的匹配文本数据，记录下相应的偏移量、匹配数据长度、首次出现的文本数据等信息。

假设当前位置为i，从第一个匹配文本数据开始，搜索到的所有偏移量、匹配数据长度分别为${\mathit{\Delta }_{ij}}$、${l_{ij}}$，其中j=1, 2, …, ${N_i}$，${N_i}$表示搜索到的匹配文本数据的数量。按照某种准则从${N_i}$个备选参数集合(${\mathit{\Delta }_{ij}},{l_{ij}}$)来选择其中一组参数作为当前搜索的结果，从而使得整个文本数据压缩后的码流最短。

选择好的参数(${\mathit{\Delta }_i},{l_i}$)来自于备选参数集合(${\mathit{\Delta }_{ij}},{l_{ij}}$)，表示为：

式中，${\rm{T}}( \cdot )$表示从参数集合中选择一种最佳参数。为了实现文本数据压缩，参数选择后应该经过熵编码器进行编码，从而得到文本压缩的码流，并从各种可能中选择最优参数。显然这种全局优化选择方法在工程中几乎无法实现。

除了上述备选集合参数外，还涉及到另外一个问题，就是首次出现的文本数据问题。如果文本压缩是全文搜索，且不论压缩效率如何，对备选参数集合中的参数进行压缩，那么首次出现的文本数据的数量实际是非常有限的，例如将文本数据按照8 bit划分，首次出现的文本数据的数量不大于2⁸=256。更多情况下，文本数据压缩需要设置一个窗口，数据匹配是在窗口内进行的，即使在窗口内能够找到备选参数，为了提高压缩效率，也需要对备选参数进行选择，如果所有的备选参数都不能满足压缩效率的要求，则应该将当前文本数据视为首次出现文本数据。为了不至于产生误解，将这类文本数据称之为保留文本数据。

从备选参数集合中选择压缩编码所需参数，实际是一个全局优化问题。即：

式中，$L({\mathit{\Delta }_\iota })$、$L({l_i})$分别表示被选择好的参数压缩所产生的比特数，如果没有从备选参数集合中选择出合适的参数，那么就将当前文本数据设为保留文本数据pre_j；L(pre_j)表示保留字的压缩输出比特数。

对于该优化问题，最简单的思路就是考虑所有可能选择，从而得到最短压缩码流长度L_min。但文本数据的统计特性十分复杂，且压缩编码的效率与参数选择过程密切相关，全局优化难以实现。考虑局部优化替代全局优化，从而便于工程实现。构造决策函数：

如果c_i=0，表示备选参数集合中没有参数被选中，当前文本数据作为保留文本数据；c_i=1，表示备选参数集合中有参数被选中，并将最优参数作为编码参数输出。

根据上述分析，可以得出文本数据压缩结构如图 1所示。

图  1  文本压缩结构框图

上述局部优化看起来合理，但实际上无法实现。因为实际编码并没有进行，无法知道参数的编码比特数，无论是偏移量、长度还是保留文本数据。为了解决上述问题，本文采用一种较为简洁算法解决上述局部优化问题，具体如下。

首先假设偏移量、长度都是采用Glomb编码，对应的参数为k₁、k₂，根据Glomb编码可知，编码输出码长分别为：

同时选择调节参数${\alpha _1}$，决策函数为：

如果认为保留字采用等长编码，即$L({\rm{pr}}{{\rm{e}}_i})$是恒定值，令，则式(5)退化为：

将式(4a)、式(4b)代入式(6)，可以得到：

式中，$\alpha = {\alpha _2} - 1/{2^{{k_2}}}$。在实际工程中通过调节以实现参数优化。

对于满足上述条件的参数，以长度最大且偏移量最小为准则，作为最终选择参数$({\mathit{\Delta }_i},{\rm{ }}{l_i})$；如果参数集合中所有参数满足式(7)，则令偏移量${\mathit{\Delta }_i} = 0$，输出保留文本数据；否则输出偏移量${\mathit{\Delta }_i}$和匹配数据长度l_i。

在文本数据压缩中，偏移量${\mathit{\Delta }_i}$、匹配数据长度l_i的分布都比较复杂。偏移量${\mathit{\Delta }_i}$中经常会出现许多幅值很大的数据，其分布动态范围很大；为了记录保留文本数据的位置信息，偏移量为0表示该数据为保留文本数据，译码时一旦遇到0，就可以从已经译码出的保留文本数据中取出数据，从而实现数据重建。位置信息的引入，又增加了数据分布的复杂性，也相应增加了编码复杂度。与此同时，l_i的幅值尽管相对比较小，但是数据分布也是非平稳的，无法使用数学分解工具对其进行分解，从而提高压缩效率。

考虑到上述因素，为了提高编码效率，可以进行预测编码。文本数据往往具有一定的规律，每隔一定间隔，有些数据就会重复出现，这类情况可以加以利用。

图  2  改进算法结构框图

设定一个间隔gap，如果文本数据x(i)满足$x(i - {\rm{gap}}) = x(i - {\rm{gap}} \times 2)$，则进入预测编码模式，预测函数如式(8)，保留下来的预测参数可以送往熵编码器进行编码。

MQ算术编码是改进的Q算法，属于自适应的二进制算术编码方法^[4-5]，能够有效实现高效数据压缩，该编码器在图像压缩中已得到广泛应用。MQ编码器是通过自适应状态跳转，从而使最终编码输出的字节数量能够尽可能小。为了提高编码效率，MQ算术编码提供了数据分类算法，数据分类采用上下文(CX)表示，编码输入为二进制判决(D)，如图 3所示。

图  3  MQ算术编码器

MQ编码器效果与上下文设计密切相关。在文本数据压缩中使用MQ算术编码器，需要研究上下文、判决的形成问题。根据上文可知，文本数据扫描过程中会产生偏移量、匹配数据长度、保留文本数据、预测参数等。这些数据都可以使用算术编码进行熵编码。

预测参数是二进制，不涉及判决产生问题，只需要进行简单的数据分类即可。本文中，上下文为前一个预测值。偏移量、匹配数据长度、保留文本数据的编码都是采用比特平面编码方法，其判决形成与图像压缩中的方法相同，而上下文的形成和编码过程则需要根据各类数据的特点进行研究。偏移量、匹配数据长度的编码分为两个步骤：零编码和细化编码。零编码对当前比特平面编码之前还不重要的系数进行比特平面编码；而细化编码则是对在当前比特平面编码之前已经重要的系数进行编码。

零编码的上下文是根据前后数据的重要性产生，即：

式中，CX_i表示当前数据的上下文；${\rm{sig}}(i - 1)$表示前一个数据的重要性；${\rm{sig}}(i + 1)$表示后一个数据的重要性。${\rm{sig}}(i) = 0$表示该数据是不重要的，${\rm{sig}}(i) = 1$表示该数据是重要的。如果数据在当前比特平面编码之前的判决都为0，而在当前比特平面的判决为1，则该数据在当前比特平面编码时由不重要变为重要。

而细化编码的上下文则是采用零编码没有使用的固定上下文，即CX_i=4。保留文本数据的编码只有一个步骤，而上下文则取当前比特编码之前的数据。

对所提出的文本压缩算法进行仿真和测试。采用4种文本数据对本算法性能进行测试，并与Winzip、WinRar压缩效率进行比较，具体结果如表 1所示。其中Test1是Word文档，Test2是纯文字文档，Test3是C语言程序代码(JPEG-LS核心算法)，Test4是Lena图像。

由表 1结果可以看出，对这4类不同类型数据，本文算法压缩性能明显好于Winzip，而在Word文档或者纯文字文档压缩方面与WinRar相当或者略好；而在C语言程序代码压缩方面，本文算法也与WinRar相当或者略低，而对图像压缩进行压缩时，本文压缩效率与WinRar还有一定差距。

与WinRar比较结果可以看出，本文算法对图像数据压缩没有取得好的效果，这是因为本文算法没有进一步使用数据之间的相关性进行编码，因此如何进一步利用相关性进行编码值得进一步研究。

为了考察参数$\alpha $变化对压缩效率影响，选择参数k₁=10，k₂=6，使用Test1进行测试，具体结果如表 2所示。从表 2可以看出，当$\alpha $大于一定值时对压缩效率影响非常有限。从式(7)可以看出，只有当偏移量很大时，参数选择才有意义，其目的是去除那些偏移量很大，而匹配字节长度较小的那些参数。而当$\alpha $大于一定值时，选择参数的差异并不是太大，所以压缩效率变化较小。

当$\alpha $取值较小时，参数选择的变化就体现出来，一些偏移量很大而匹配字节长度有限的参数被选择，从而降低了编码效率，编码输出文件长度增加较大，从而影响总体编码效率。

为了考察Glomb参数选择对压缩效率的影响，取$\alpha = 6.2$，${k_2} = 6$，改变参数${k_1}$，使用Test1进行测试，结果如表 3所示。

从表 3可以看出，参数的变化对压缩效率有一定影响，参数小于10时，随着参数减小，压缩效率明显降低；而当参数大于等于10时，由于偏移量大而匹配数据长度小的参数被去除，压缩效率没有明显变化。

为了观察k₂变化对压缩效率影响，取$\alpha = 6.2$，k₁=10，改变参数k₂，使用Test1进行测试，实验结果如表 4所示。

从表 4可以看出，随着k₂的变化，对压缩效率有一定影响，但是不是十分明显。从式(7)可看出，由于大偏移量受到k₁约束，k₂取值只是辅助参数选择的细节，且受到α变化的制约，因此对总体效率的影响不是很大，其取值大小与匹配字节长度小的参数选择产生一定影响。当其取值太大，会增加小匹配字节长度选取的门槛，所以对压缩效率影响较大；而取值较小时，其影响反而不是太大。

综合k₁、k₂变化对压缩效率影响，结果与式(7)说描述的含义是相符的，即：

1) k₁主要是限制偏移量大而匹配字节长度较小的参数，以提高编码效率；当其取值较小时，偏移量大，匹配字节长度较小的参数被选择，从而影响编码效率；而取值较大时，只有极少的参数被限制，对压缩效率的影响反而较小。因为匹配字节长度较大的参数，k₁变化对其没有约束。

2) k₂对偏移量变化没有限制作用，主要辅助设置匹配字节长度门槛。取值越大，更多长度较小的参数被去除，效率降低；而较小的取值，反而对结果影响不大。

本文提出了一种基于算术编码的文本数据压缩算法，与Winzip、WinRar算法相比，在对纯文本数据、Word文档数据、C语言程序代码进行压缩时，本文算法优于WinZip，与WinRar算法相当或略好，但在图像压缩方面的性能与WinRar相比略有不足。当然，本文算法还存在以下不足：一方面，简单使用LZ77扫描算法，从而导致偏移量数据较大，不利于后续数据压缩；另一方面，没有对相关性数据进行进一步处理，对诸如图像数据这类关联性很强的数据压缩效率不足。针对上述不足，今后将考虑更好的扫描算法，以提高压缩效率；对数据的相关性进行检测，对相关性强的数据进行数据分解，进一步提高编码效率。