基于C++实现的LZW压缩算法

Badguy

发布日期: 2018-11-02 15:56:05 浏览量: 727
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

1 特点

基于C++实现的LZW压缩算法,特点如下所示:

  • 使用stl::map键值对作为字典存储

  • 感觉算是简单的文件操作

  • 字典无限长,字典自生长。但是字典只能解析存储ascii编码之类存在,中文符号之类的碰到就挂

2 逻辑设计

2.1 总体思路

2.2 模块划分

3 总结

LZW算法的核心时字典的生成,因为字典是不保存的,是动态生成的,不管是在压缩还是解压缩的情况下都是如此。既然字典是自生成的,就需要解决解压或者压缩第一个输入字符的问题。在这里我使用的是ASCII码,在字典中声明256个空间,在读入第一个字符便可以对应之。关于编码存储,可以使用16进制来存储。

同时,既然是一种压缩算法,压缩率和压缩速度便是其两大评价标准。关于压缩率,限于算法性能,在压缩小型且重复率低文件时甚至会有副作用,这是无可避免的,只能在这种前提下避免使用这种算法。至于压缩速度,在我第一次编写程序时,因为使用的是Map来做字典,而且为了解压缩的方便,两种方法使用同一种字典,即<编码值, 关键字>存储,这样造成的问题是,在压缩时,要经常且循环检查关键字是否在字典中存在,而又因为map是形如红黑树的构造,在查找键的环境下时间效率是对数n,但是查找关键字就需要借助自行编写的迭代器,就造成了很大时间性能限制。所以,在第二次改进时,压缩变成了<关键字, 编码值>,解压缩则还是<编码值, 关键字>。这样虽然在同时进行压缩和解压缩的情况下会加大内存开销,但是在提升4-5倍速度的情况下我认为还是值得付出的代价。

4 程序主界面

上传的附件 cloud_download 基于C++实现的LZW压缩算法.7z ( 208.39kb, 49次下载 )
error_outline 下载需要4点积分

发送私信

日久不一定生情,但必定见人心

9
文章数
17
评论数
最近文章
eject