Lempel-Ziv-Welch(LZW)压缩数据误码修复技术

2020-06-09王刚彭华唐永旺靳彦青

北京理工大学学报 2020年5期

王刚，彭华，唐永旺，靳彦青

(1.信息工程大学信息系统工程学院，河南，郑州 450001；2.国家数字交换系统工程技术研究中心，河南，郑州 450002)

1948年Shannon发表的“A Mathematical Theory of Communication”标志着信息论的诞生. 在信源信道分离理论的指导下，目前的通信系统中，信源编码实现了通信有效性问题，信道编码实现了通信可靠性问题. 由于分离定理的局限性，级联编码的设计思想使信源编码后的序列抗干扰能力变得十分薄弱. 事实上，自适应数据压缩缺乏修复能力是在许多应用中存在的一个突出缺点. 从信源编码机理分析可见，信源编码得到的数据几乎是没有冗余的，这种数据经过信道传输后，由于信道噪声和干扰的影响，往往存在误码[1]. 而近乎零冗余的压缩数据是没有抗误码能力的，在这种情况下进行信源译码时，误码会导致构造码表和重构数据出现错误，随着译码进行码表和数据误码的影响就呈现出扩散的态势，引发大规模的差错传播即误码扩散，所以少量误码就有可能造成严重后果. 因此，压缩数据流对传输错误非常敏感，含误码的压缩数据无法进行译码，往往一个比特的错误就会危及后续所有数据[2]，并造成整个文件无法解压，严重影响了压缩数据恢复的质量，导致信息的丢失.

联合信源信道编码[3-4]成为解决这个问题的一种可能方案. 但是根据网络协议的划分，信源编码和信道编码处于协议的不同层，联合编码需要进行跨层的优化，而目前网络协议不同层之间的数据是独立的，从而使得联合信源信道编码不能有效发挥作用[5]. 所以，需要从信源的角度考虑解决信源编码数据的误码修复难题.

Lempel-Ziv-Welch(LZW)[6]压缩算法是一种无损数据压缩算法，作为Lempel-Ziv 78( LZ78)字典编码算法的改进版本，由T.Welch提出，用于高性能磁盘控制器的硬件实现. 当程序压缩成为Unix系统中标准压缩方案时，该算法得到了广泛的应用. LZW算法作为GIF图像格式和V.42bis调制解调器的标准被采用，在TIFF图像和PDF格式文件中都使用了LZW算法.

由于信源经过压缩后去除了大量的相关性，压缩编码后的数据中冗余很小，在译码端压缩数据恢复过程中进行误码修复可利用的冗余信息非常少. 因此目前关于提高Lempel-Ziv(LZ)系列压缩算法抗误码能力的研究主要集中于改进编码端的容错能力：Frenkel等[7]分析了LZW的编码规则，提出一种新的码表构造及更新的优化方法并能对压缩数据提供一定的保护；Kostina等[8]利用随压缩数据一同传递的信源状态和信道状态的先验信息，在一定误码率条件下对压缩数据的误码进行了修复；Zhang等[9]采用了信道编码保护数据的思路，通过对编码数据进行分组并为分组码字额外增加了校验码；Klein等[10]将LZ方法的标准编码转换为固定长度的编码，可以提高译码速度并在发生错误的情况下提供更强的健壮性. 这些方法虽然能取得一定的效果，但算法复杂度较高，还会降低压缩性能，更重要的是由于对编码规则以及数据格式进行了修改，导致无法与标准算法兼容，因此实用性打了折扣.

本文针对LZW算法的误码修复问题，提出一种与标准LZW算法保持兼容的新设计方案，即用本文给出的LZW算法压缩的数据，在具有误码修复功能的同时可以使用标准LZW算法进行译码. 与标准算法兼容是一种基本属性，因为它可以确保在不中断服务的情况下逐步部署新方案.

本文的思路是在LZW压缩数据流中，通过选取部分编码码字并动态调整其对应的被压缩字符串的长度，来满足上述约束条件，这样就可以利用动态调整的码字短语模式嵌入额外消息比特. 根据实验结果，采用本文提出的嵌入校验码的LZW算法压缩的数据，比附加校验码的标准LZW算法压缩的文件还要短，因此新策略几乎不会影响LZW算法的整体压缩性能. 通过对LZW解码器的广泛测试表明，由于没有改变编码规则和数据格式，基于误码修复的LZW编码方法与标准LZW算法完全兼容.

1 基本概念

在有限符号集A中，文本T的长度为|T|=n，T′表示对应的LZW编码数据流，T[i]表示T的第i个符号. 用T[i,j]来表示T[i]T[i+1]…T[j](1≤i≤j≤n)的缩写形式，约定T[i,i]=T[i]. 给定两个字符串y和w，y+w表示通过连接y和w得到的字符串.

标准LZW算法[6]将字符串T按照从左到右的顺序分解成短语序列，其中每个短语是之前搜索到的最长匹配字符串再加上一个额外的符号. 字典首先被初始化为包含字符集中的所有单个符号，每个新短语都被添加到字典中. 把最长匹配短语的索引作为一个新的码字加入到输出序列T′中，同时把额外的符号即当前短语的最后一个符号作为下一个短语的第一个符号.

为了解码压缩数据T′，解码器需要首先将字符集中的所有符号填入字典，然后从压缩数据T′中逐个读取码字. 每当解码器读取一个新的码字时，通过搜索字典查找相应的短语. 根据码字识别出的字符串被添加到输出结果中，同时把一个新短语添加到字典中，该短语由将当前码字的第一个符号附加到前一个码字来构造.

2 LZW压缩数据中额外比特的嵌入和提取

由于标准LZW算法固有的贪婪性，在编码过程中，总是只有一种生成码字的方法，因此字典中的每一个短语都是唯一的[11]. 这种贪婪意味着缺乏冗余，反过来会造成无法直接将额外的比特嵌入到压缩数据流中. 解决这个问题的有效方法是通过使用非贪婪算法让一些短语变短一些，这样可以引入足够多的冗余来对额外的比特进行编码. 通过选择使用非贪婪算法来缩短部分短语，就有了必要的额外空间来存储用于检测和校正错误的信息位. 需要注意的是，通过非贪婪算法，字典中的某些条目将会有多个与之关联的码字.

文献[12]中，通过调整匹配LZW短语的长度，以便在压缩文件中隐藏额外的位元. 根据实验测评，由于压缩性能下降太多，这种策略不具有实用性.

在进一步研究之前，首先要确定在用改进的编码器中生成的压缩文件，是否仍然可以被标准LZW算法(称为Standard-LZW，简记为S-LZW，以区别于本文提出的算法Carrier-LZW，简记为C-LZW)解压缩. C-LZW算法的兼容性依赖于在LZW解码器实现中用来表示字典的特定数据结构. 在文献中，字典总是以trie树的形式表示，LZW的实现一般都使用固定大小的哈希表(通常包含4 096个条目). 因为解码器使用哈希表而不是trie树，它不会受到字典中多个相同条目的影响. 解码器通过索引找到其对应的短语，并串联两个字符串来产生下一个短语，不论是否存在多个这样的短语. 因此，本文提出的C-LZW方案能够兼容标准LZW解码算法. 实验也验证了C-LZW对各种软件的兼容性. 例如，对于GIF图像，测试了MS Paint，MS Internet Explorer和Mozilla Firefox. 另外还测试了Unix压缩、PDF和TIFF解码器以及Winzip，所有软件都能够解压C-LZW算法生成的数据流.

用M表示将要嵌入到压缩数据T′中的额外数据，称之为消息. 因为C-LZW算法而变短的LZW短语被称为非贪婪短语. C-LZW算法的性能由两个非负整数参数K和L决定. 整数K指定在两个连续的非贪婪短语之间的间隔内嵌入的消息位数，参数L指定在每个非贪婪短语长度中嵌入的位数.

首先从逻辑上把要嵌入的消息M划分为连续的(K+L)位为一组的数据块. 每个块被进一步分成两个长为K和L的子块. 两个子块的值分别用k和l表示(k∈[0,2K-1],l∈[0,2L-1]). 根据LZW编码方案，在编码压缩T时每次把消息M的一组(K+L)位的数据块嵌入到压缩数据T′中. 初始化一个计数器为0，并根据S-LZW算法生成新短语. 每生成一个新短语，就将该短语长度与2L进行比较(2L是l的最大值). 如果该短语长度更大，就把计数器增加1. 一旦计数器达到k这个值，就把该短语对应的原始数据减去长度为l的字符串并重新编码. 重置计数器，开始新的循环. 在压缩文本T的同时把消息M嵌入LZW编码数据流如下.

C_LZW_ENCODER(T,M,K,L)

1.T′={},i=0

2.k←getKbits fromM

3. if(k=0)thenk=2K

4. while (encoding!=end) do

5. phrase←encode phrase according to the S-LZW algorithm encoder

6. if (|phrase|>2L) then

7.i=i+1

8. if (i=k) then

9.i=0

10.l←get nextLbits fromM

11. if (l=0) thenl=2L

12. reduce the length of phrase by l symbols

13.k←get nextKbits fromM

14. if (k=0) thenk=2K

15.T′=T′+phrase

16. returnT′

译码过程相对简单，随着码字的读入，短语被重构. 对于每个短语，解码器判断该短语是贪婪的还是非贪婪的. 如果这个短语是非贪婪的，根据遵循的嵌入规则将一个(K+L)位的消息块恢复出来，同时根据LZW算法对原始文本进行重构. 为了确定一个短语是否贪婪，解码器需要考虑几个相连的短语. 这可以通过在前面的缓冲区中保存最后几个短语来实现. 从非贪婪LZW数据流T′中提取出嵌入的消息M流程如下.

C_LZW_DNCODER(T′,K,L)

1.T={},M={},i=0

2. while (decoding!=end) do

3. phrase1←decode phrase according to the S-LZW algorithm decoder

4.T=T+phrase1

5. phrase2←encodeTaccording to the S-LZW algorithm encoder

6. if (|phrase2|>2L) then

7.i=i+1

8. if (|phrase1|<|phrase2|) then

9.M=M+(i&(2K-1))+((|phrase2|-|phrase1|) &(2L-1))

10.i=0

11. return (T,M)

3 参数K和L的选择

将额外的信息嵌入LZW数据流显然不是没有代价的. 由于嵌入了额外的位，C-LZW编码数据流会稍微长一点. 从直观上看，随着K的减少和L的增加压缩性能会降低，但同时嵌入在压缩数据中的比特数增加. 在误码修复的应用中，确定最佳的平衡点是至关重要的. 第一步是计算所需的校验码的总数，一旦完成，就需要通过函数(参数为K和L)估计可以嵌入到T′中的比特数量，其目的是用来为校正误码的校验码创建足够多的空间.

把T中用S-LZW算法编码的短语部分称为T1，用C-LZW算法编码的短语部分称为T2. 那么，压缩编码后把码字符号分成两部分，这两部分分别对应原始数据的T1和T2，大小分别是n1和n2，则有n=n1+n2.

根据上面的公式，可以根据给定的n、h1、K和L的值估计能够嵌入的消息的大小|M|. 熵h1可以根据定义直接从文本中计算出来，也可以通过实验推断出来. 在估计阶段，首先计算由S-LZW算法压缩文本时产生的短语数量P，然后根据渐近方程P≈nh/lbn，可以得到熵的表达式h=Plbn/n. 用这种方式获得h的优点是能考虑到可能隐藏在渐近方程中的常数因子.

4 冗余度的渐进分析

定义函数μ(x)来描述文本长度，并以短语的数量x作为成员变量

因此，平均冗余rn为

将其与S-LZW进行比较，得到C-LZW的冗余度增加量为

5 LZW数据的误码修复

文献[1]提出利用LZ77编码过程中最大匹配的非唯一性，通过嵌入Reed-Solomon(RS)[15]码来检测和纠正错误. RS编码是一种基于块的错误校正码，广泛应用于数字通信和存储. RS码标准形式为RS(a,b)，a表示码长即数据块的大小，b表示信息长即有效载荷的大小，RS解码器可以在一个数据块中纠正e个错误，其中e=(a-b)/2. 本文采用在C-LZW编码器产生的额外冗余中嵌入RS码来检测和修复数量有限的错误.

具有LZW误码修复功能的编码器及解码器的操作流程如图1所示. 首先，文本T被S-LZW压缩. 如上所述，典型的LZW实现有一个固定大小的字典(作为散列表实现)，当字典中条目填满后，字典就会定期更新. 在图中，当字典更新时，在LZW文件中用字典终止(EOD)符号*来标示在压缩数据T′中的位置. 因此，压缩文本T′可以被分割成块.

基于误码修复的LZW编码器按照从右到左的块顺序，从最后一块开始处理. 在通用步骤中，首先计算块Ci的RS校验码，然后按照第4节的方法在块Ci-1中嵌入该校验码，嵌入过程要求编码器再次压缩Ci-1数据块. 由于算法改变了部分短语的长度，可能会在词典中提前引入结尾. 因此，使用2个连续的EOD符号来编码块的边界，这样就不会影响算法的兼容性.

基于误码修复的LZW解码器按照从左到右的块顺序，从第一块C1开始处理. 在通用步骤中，首先解压Ci压缩数据块，并按照第4节的方法恢复出RS校验码. 校验码可以在压缩数据块Ci+1被解压缩之前检测和纠正错误. 为了保证兼容性，第一个压缩数据块不受校验码的保护.

6 实验及结果分析

由于GIF文件采用的是标准LZW压缩算法且具有可视直观性，因此使用 GIF文件进行测试. 实验包括两个部分，即C-LZW压缩算法和C-LZW解压算法. 使用C-LZW压缩编码时，输入标准GIF文件和待嵌入的消息文件(可以是隐蔽传送的信息，也可以是压缩编码相应数据块的RS校验码)，并设置参数K、L，程序生成嵌入信息的GIF文件，编码器还提供一些有用的统计信息，如短语的总数、已嵌入的消息长度等. C-LZW译码器接收嵌入消息的GIF文件和参数K、L(必须与编码中使用的那些参数相匹配)作为输入，提取出嵌入的消息并利用RS校验码对数据块进行误码修复，再把数据块重新生成无嵌入消息的GIF文件.

为了保证兼容性，使用一些现有软件打开嵌入消息的GIF文件，实验证明这些软件都可以正确显示GIF图像. 实验还验证了提取的GIF文件与原始GIF文件完全相同，并且从C-LZW文件中提取的消息与嵌入的消息完全相同.

测试数据使用的是用于数字图像处理和数据压缩的图像. 表1给出了K=5且L=1时的实验结果. 实验中，嵌入的额外比特是由一个0和1等概独立同分布的模型随机生成的. |M|为可以嵌入到原始GIF文件中的额外字节数量；|T′|为原始GIF文件的大小(单位:字节)；l为嵌入前LZW编码码字的平均长度；|T′M|为嵌入消息后GIF文件的大小；lM为嵌入后LZW编码码字的平均长度；|T′M|-|T′|-|M|描述了根据不同参数引起嵌入数据量发生变化的情况下，C-LZW与S-LZW压缩性能的比较结果. 最后一列列出了对消息长度的估计值.

表1 将GIF图像分别用S-LZW与C-LZW进行压缩比较(K=5，L=1)Tab.1 Compressing and comparing GIF images with S-LZW and C-LZW(K=5，L=1)

通过与S-LZW算法的对比，C-LZW算法在文件3和6上比其他的GIF文件更好，而文件4在所有这些文件中是最差的. 这是因为文件3和6的平均短语长度(分别为5.78和4.87)比文件4(2.49)要高得多，因此，减少前两幅图像的短语长度对压缩的影响不会超过文件4. 列|M|/|T′|给出了压缩文件中平均每个字节能嵌入的字节数，例如对于文件3，平均每38字节可以嵌入一个字节. 实验发现，除了文件4，这些文件之间的|M|/|T′|比值变化很小，这是由于文件4的压缩比相对较差. 表中给出了|M|的估计值，通过对比发现准确度较高，特别是当K>4时.

表2列出了参数K和L取不同值的实验结果. 如预期的那样，可以嵌入的额外数据|M|随着参数K的增加而减小. 然而，|M|和参数L之间的关系并不明确. 实验中，当参数K很小的时候，例如小于4，将参数L从0增加到1通常会增加可以嵌入的位数. 然而，当参数L超过1的情况下，既不能嵌入更多的比特，也不能提高图像压缩比.

当嵌入RS码对LZW压缩数据进行误码修复时，通常选择RS(255，255-2e)，其中255是包含压缩数据和校验码的数据块的大小，255-2e表示有效载荷即压缩数据的大小，e是可以纠正的最大错误数，即RS解码器可以在255个字节的数据块中纠正e个字节的误码. 当取e=1时，得到BER=1/255≈3.92×10-3，此时需要嵌入2e=2×1=2个字节的校验码，即嵌入率满足|M|/|T′|=2/255=0.007 843即可. 根据表2的实验结果发现，在BER<3.92×10-3的情况下，当1≤K≤7且0≤L≤1时，可实现LZW压缩数据的误码修复. 实用中，可以根据误码率动态调整参数K和L的取值，以得到不同的嵌入率，从而进行有效的LZW压缩数据的误码修复.