串编辑和LZW压缩算法设计

赵美勇 史昊臻 朱珍珍

摘  要：串编辑一类字符串转换的问题，将两个字符串按照某种规则进行转换，转换将有三个消费函数，利用动态规划的方法可以得到各个操作的耗费之和，解决串编辑的问题。利用HASH链式散列来实现LZW压缩方法，利用字典组织，节省空间降低算法的复杂度，从而达到快速的代码简化法。

关键词：串编辑;LZW压缩;动态规划;HASH

中图分类号：TP301.6       文献标识码：A 文章编号：2096-4706（2019）08-0094-03

Abstract：String editing a class of string conversion problem，the two strings are converted according to a certain rule，the conversion will have three consumption functions，using the dynamic programming method can get the sum of the cost of each operation，solve the problem of string editing. LASH compression method is implemented by HASH chain hashing，which uses dictionary organization to save space and reduce the complexity of the algorithm，thus achieving fast code simplification.

Keywords：string editing;LZW compression;dynamic programming;HASH

0  引  言

串编辑是一类动态规划问题，也是一类优化问题。在一些大型的字符串算法中，比如：后缀树、AC自动机、KMP等算法中，其作用相当重要。它主要解决的就是字符串转换问题，将两个字符串按照某种规则转换，其中转换的代价就是所要求得目标。它利用的动态规划的思想，通过记忆化搜索保存每种状态，这个算法在转换一些大字符串时表现相当优秀。LZW压缩算法是处理图像压缩的，应用在某些神经网络算法中，因为其优秀的图像压缩功能，可以大幅度减少神经网络在处理卷积时的复杂度。

1  串编辑和LZW压缩算法需求描述

1.1  串编辑算法需求

在串编辑问题中，给出两个串a=a1a2…an和b=b1b2…bm及三个耗费函数C，D和I。其中C（i，j）为将ai改为bj的耗费，D（i）为从a中删除ai的耗费，I（i）为将bi插入a中的耗费。通过修改、删除和插入操作可把串a改为串b。如可删除所有ai，然后插入所有bi;或者当n≥m时，可先把ai变成bi（i≤i≤n），然后删除其余的ai。整个操作序列的耗费为各个操作的耗费之和。

1.2  LZW压缩算法需求

在一个文本文件上实现LZW压缩和解压缩，其中每个字符就是该文本的8位ASCLL码;对一个256色BMP图片文件实现压缩和解压缩。

2  串编辑和LZW压缩算法设计

2.1 串编辑设计

2.1.1  数据及数据类型定义

（1）输入模块：

用户使用键盘完成字符串a和b的输入。

（2）编辑模块：

首先调用随机模块，随机产生三个函数的值。设f[i][j]为将字符串a的前i个字符改为字符串b的前j个字符的最小耗费，考虑f[i][j]可能的取值：将字符串a的前i个字符改为字符串b的前j-1个字符，再将字符串b的第j个字符插入到a中，即：f[i][j]=f[i][j-1]+I[j]。将字符串a的前i-1个字符改为字符串b的前j个字符，再将字符串a的第i个字符删除，即：f[i][j]=f[i-1][j]+D[i]。如果字符a[i]和b[j]相等，则：f[i][j]=f[i-1][j-1]。如果字符a[i]和b[j]不相等，可以将字符串a的前i-1个字符改为字符串b的前j-1个字符，再将a[i]改为b[j]，即：f[i][j]=f[i-1][j-1]+C[i][j]，f[i][j]的取值为上面四种情况的最小值。为了方便输出路径，还需要记录它的前一个状态指针和得到当前状态的操作。

（3）随机模块：

通过分析可知，函数C对应一个大小为|a|*|b|的二维数组，函数D对应长度为|a|的一维数组，函数I对应长度为|b|的一位数组;通过C++的随机函数rand（）为数组每一个位置赋值，并且分析可知，修改、删除、插入操作都可以在线性时间内完成，因此每个的大小应该小于字符串的长度，大于0。

（4）输出模块：

通过编辑模块中记录的状态指针，从f[|a|][|b|]移动到f[1][1]，将得到的编辑序列逆序输出，即为最小耗费对应的编辑序列。

2.1.2  數据及数据类型定义

（1）每个状态需要储存的信息：

w为当前状态的最小耗费，fi、fj为上一状态的下标，id表示得到当前状态操作的标号。

（2）操作序列每一项的信息：

记录对a[i]和b[j]进行对应操作的id号。

（3）串编辑类：

C、D、I三个数组分别代表修改、删除、插入三个函数，edg存储编辑序列，f为存储状态。

2.1.3  设计及分析

（1）编辑模块：

（2）时间复杂度分析：

随机模块中生成D和I数组需要线性时间，生成C数组的时间复杂度为O（|a|*|b|）;编辑模块中状态共有|a|*|b|个，每次状态转移为常数时间，因此时间复杂度为O（|a||b|）;输出编辑序列需要线性时间。综上，总的时间复杂度为O（|a|*|b|）。

2.2  LZW压缩算法设计

2.2.1  结构设计

LZW压缩和解压使用了链式散列表;BMP图片构造图片信息格式。

2.2.2  数据及数据类型定义

字典中的元素使用数对来表示，类型定义：template <class K， class E>;图片类型包括文件类型、信息头、像素信息。

2.2.3  算法设计及分析

（1）抽象字典类：

（2）Hashchains实现字典类：

（3）压缩LZW类：

（4）解压缩UNLZW类：

3  结  论

利用动态规划方法，基本解决了串编辑问题。但因为题目中C、D、I三个函数的限制较少，我们采用随机生成的方式并不是很好，这里就没有考虑字符串中出现相同的字符的问题，例如：对于相同的字符，执行插入操作和删除操作的耗费是不是一样？因此，具体的串编辑问题还需要重新设计随机模块。另外，我们还期望将执行每个操作之后a数组的变化展现给用户。

HASH链式散列实现形式下的一个应用LZW压缩的实现方法。在压缩中对字典组织的使用，以及为了节省空间降低算法复杂度以达到加快速度的代码简化法，还有在对图片文件处理时了解BMP文件本身不单单是多个像素块的堆叠，它有明确的格式，复杂的构造，包括三个头部信息，一个图片像素信息。

参考文献：

[1] Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，等.算法导论 [M].第3版.殷建平，徐云，王刚，等，译.北京：机械工业出版社，2012.

[2] Robert Sedgewick，Kevin Wayne.算法 [M].第4版.謝路云，译.北京：人民邮电出版社，2012.

[3] Brian W. Kernighan，Dennis M. Ritchie.C程序设计语言 [M].徐宝文，李志，译.北京：机械工业出版社，2004.

[4] 刘汝佳，陈锋.算法竞赛入门经典：训练指南 [M].北京：清华大学出版社，2012.

[5] 刘汝佳.算法竞赛入门经典 [M].第2版.北京：清华大学出版社，2014.

作者简介：赵美勇（1997-），男，汉族，山东聊城人，本科，主要研究方向：计算机科学与技术;史昊臻（1998-），女，汉族，山东菏泽人，本科，主要研究方向：通信工程;朱珍珍（1998-），女，汉族，河南驻马店人，本科，主要研究方向：信息管理与信息系统。