【VC++开源代码栏目提醒】:网学会员鉴于大家对VC++开源代码十分关注,论文会员在此为大家搜集整理了“Linux下文件压缩和解压缩分析研究与实现 - 中考高考”一文,供大家参考学习
北方民族大学 学士学位
论文论文题目: Linux 下文件压缩和解压缩分析研究与实现 院部名 称: 电气信息工程学院 学 生 姓 名: XXX 专 业: 信息工程 学 号: 00000000 指导教师姓名: XX 教授
论文提交时间: 2013.5.15
论文答辩时间: 2013.5.25 学位授予时间: 北方民族大学教务处制 摘 要 在现代社会,计算机技术的发展,使得现代社会更加丰富多彩,我们可以随时随地在任何地方了解到世界各地的信息,而这又必须依赖信息的传递。
在信息化高度发达的当今社会,我们必须对信息的传递有着较高的要求,我们希望信息在传递的过程中,能够保持节省性和保密性和无损性,而著名的霍夫曼编码就能够达到这样的要求。
因此研究霍夫曼编码对信息的压缩和解压缩就时相当有必要的,我们用 C/C语言对霍夫曼编码给出算法以实现对文件的压缩和解压缩。
而Linux 系统提供了编辑器(vim)、编译链接器(gcc)、调试器(gdb)及项目管理工具(make)。
利用这些工具我们可以非常方便的进行 C/C程序的开发以实现对文件的压缩解压缩。
本文将利用霍夫曼树与数据结构中最优二叉树的相似性,以及通过对文件 I/O 的操作,在 Linux 环境下实现对文件的压缩与解压缩。
关键词: 压缩,解压缩,Linux,霍夫曼编码 ABSTRACT In modern society the development of the communication the more colorfulmodern society we have learned anywhere anytime anywhere around the worldwhich in turn must rely on the transmission of information. In the highly developedinformation technology in todays society we have a higher demand on thetrans
mission of information we hope that the information in the delivery process cansave and confidentiality and non-destructive and the famous Huffman coding will beable to achieve such requirement. A result of Huffman coding compression anddecompression of the information on quite necessary with C/C language forHuffman coding algorithm is given in order to achieve the compression anddecompression of files. The Linux system provides an editor vim compiler linkergcc debugger gdb and project management tools make. The use of these toolscan be very convenient for the development of the C program to implement filecompression decompression. The paper will use the optimal binary the Huffman treedata structure as well as file compression and decompression file I/O operation in theLinux.KEY WORDS: compression Decompression,Linux Huffman coding北方民族大学学士学位
论文 Linux 下文件压缩和解压缩分析研究与实现 目 录第 1 章 绪论.................................................................................................................. 1 1.1 数据压缩技术简介 .............................................................................................. 1 1.2 数据压缩的分类 .................................................................................................. 1 1.3 本文的主要工作 .................................................................................................. 2第 2 章 Linux 编程环境概述 ....................................................................................... 3 2.1 Linux 系统的由来及发展现状 ........................................................................... 3 2.2 Linux 下 C/C语言编程的主要工具 ............................................................... 4 2.2.1 编辑器 vim .................................................................................................... 4 2.2.2 编译链接器 gcc ............................................................................................ 5 2.2.3 调试器 gdb ................................................................................................... 7 2.2.4 工程管理器 make......................................................................................... 7第 3 章 霍夫曼编码原理.............................................................................................. 9 3.1 霍夫曼编码的理论基础 ..................................................................................... 9 3.2 霍夫曼编码 ....................................................................................................... 10 3.2.1 霍夫曼编码步骤 ........................................................................................ 10 3.2.2 霍夫曼表 .................................................................................................... 10 3.2.3 霍夫曼树 .................................................................................................... 11 3.2.4 霍夫曼树与压缩编码 ................................................................................ 12第 4 章 基于霍夫曼编码的文件压缩与解压缩的实现............................................ 15 4.1 程序的设计思想 ............................................................................................... 15 4.2 编码程序设计 ................................................................................................... 15 4.3 译码程序设计 ................................................................................................... 17 4.4 软件的运行结果 ............................................................................................... 19第 5 章 结论................................................................................................................ 21致 谢............................................................................................................................ 22参考文献...................................................................................................................... 23附录 1:程序源
代码................................................................................................... 25附录 2:英文原文....................................................................................................... 38附录 3:中文译文....................................................................................................... 47北方民族大学学士学位
论文 Linux 下文件压缩和解压缩分析研究与实现 第 1 章 绪论1.1 数据压缩技术简介 随着
计算机技术的发展,数据压缩技术有了越来越重要的作用1。
只有数据有重复性,冗余性,才能够实现压缩。
在我们的生活中,一部电影,一首歌曲等,这些数据都有着相当的重复部分。
比如一篇英文文章,即使很长,它也是由26 个英文字母组成的。
如果我们对这些数据进行编码,将大大减少数据的存储空间。
总之,生活中的许多数据都是有重复性的,而减少重复,以尽可能少的码来编排一段具有重复性的有效数据便是数据压缩的精髓2。
1.2 数据压缩的分类 数据压缩的研究己有几十年的历史,其间,人们提出了许多压缩算法。
在分类上,也存在几种不同的方法,一般根据压缩过程是否可逆分为两种:无失真压缩编码Noiseless Coding与有失真压缩编码Noise Coding也有人按编码的建模不同将其分为:模型基编码和波形基编码;还可按压缩技术所使用的方法进行分类,可分为预测编码Predictive Coding、变换编码Trannnsform Coding和统计编码Statistical Coding三大类。
其中第一类是最常用的分类方法3。
无失真压缩,也可称之为冗余度压缩Redundancy Compression,原始数据可通过对压缩数据的解码完整的还原。
这种压缩方法的原理是除去或尽量除去数据中重复和冗余部分,而不丢失其中的信息,从而确保被压缩了的数据还原后与压缩前完全一致。
无失真
压缩方法主要应用于不允许出现失真的场合例如对程序文件,文本文件的压缩等。
常用的无失真压缩技术有:霍夫曼Huffman编码,算术Arithmetic编码,LZ 编码,游程编码RLE等。
有失真压缩:也可称为熵压缩Entropy Compression,这是一种不可逆压缩。
1北方民族大学学士学位
论文 Linux 下文件压缩和解压缩分析研究与实现它主要适用于允许数据出现失真的场合。
例如图像,视频等。
由于丢失的部分信息,所以这种压缩方法可以实现较高的压缩率。
在这些方法中,霍夫曼编码是一种无损压缩方法,霍夫曼编码是可变字长编码VLC的一种。
一般用来压缩文本文件,程序文件。
霍夫曼压缩属于可变
代码长度算法一族。
意思是不同符号(例如,文本文件中的字符)用一个特定长度的位序列替代。
在文件中出现频率高的符号,使用较短的编码,而那些很少出现的符号,则用较长的编码。
在本文中将利用霍夫曼编码实现对文件的压缩与解压缩。
1.3 本文的主要工作 本文的主要内容将分为三部分: 第一部分,将对 Linux 系统做简单的介绍,对 Linux 系统中常用的工具简做单的介绍。
第二部分,将对霍夫曼编码进行介绍,并研究利用霍夫曼编码实现对文件的压缩与解压缩。
第三部分,将在 Linux 系统中,利用霍夫曼编码实现对文件的压缩与解压缩。
并给出给出了具体的实现示例,通过截图的方式直观地表现在
论文中。
2北方民族大学学士学位
论文 Linux 下文件压缩和解压缩分析研究与实现 第 2 章 Linux 编程环境概述 实现文本的压缩与解压缩,首先应找到一个非常利于编程的环境。
Linux 环境下的 C/C语言程序
设计与在其它环境中的 C/C程序设计一样主要包括编辑器(vim) 、调试器(gdb)和项目管理工具(make) 、编译链接器(gcc) 。
利用 在这些工具以及 Linux
开源的特点, Linux 下可以方便的进行 C 程序软件的开发。
2.1 Linux 系统的由来及发展现状 。
Linux 系统的创始人是林纳斯托瓦兹(Linus Torvalds)而 Linux 系统的出现则是无数自由
软件运动爱好者智慧的结晶。
Linux 是类 UNIX 操作系统,UNIX 上的软件不需或经过小的改动就可以在Linux 上运行。
1983 年,托瓦兹创建了以创建一个自由的操作系统为目标的 GNU计划。
在其后的几年中越来越多的开发者加入这个组织,致力于 Linux 内核的开发。
终于,在 1992 年,在 GNU GPL 下 Linux 内核被重新授权使用,产生了第一个“Linux 发行版本”4。
在 1994 年 3 月 托瓦兹认为内核的所有组件已经完全成熟,同年,他发布了 Linux 的 1.0 版本,Linux 内核版本的发展如表 2-1 所示。
XFree86 项目组提供了一个图形化操作界面(GUI)。
同年 red hat(红帽)公司和SUSE 发行了他们各自的 Linux 1.0 分发版本。
相比 windows 操作
系统,Linux 系统最大的特点是
开源性。
程序员可以阅读到 Linux 系统中任何程序的源
代码。
也正是这个特点使 Linux 系统迅速发展。
Linux 的应用领域不断扩展,从最早的 Web、FTP、邮件服务开始,逐步扩张到个人桌面应用、网络安全、远程教育、集群计算、网络计算、嵌入式系统等各个领域。
更是吸引了想 IBM、SUN、惠普这样的 IT 巨头积极参与到 Linux 应用的开发和推广中去。
Linux 之前主要应用于服务器及计算集群,未来应该该在个人计算机上有所发展,优化目前的图形化界面,以及加快桌应用的开发,以及在智能终端的应用。
3北方民族大学学士学位
论文 Linux 下文件压缩和解压缩分析研究与实现 表 2-1 Linux 内核版本 版本号 发布时间 说明 0.00 1991.2 两个进程分别显示 AAA BBB 0.10 1991.9 第一个正式向外公布的 Linux 内核版本 0.02 1991.10 内部版本,目前已经无法找到 0.10 1991.10 由 Ted Tso 发布的 Linux 内核版本 0.11 1991.12 基本可以正常运行的内核版本 0.12 1992.1 主要加入对数学协处理器的软件模拟程序 0.950.13 1992.3 开始加入虚拟文件系统思想的内核版本 0.96 1992.5 开始加入
网络支持和虚拟文件系统 VFS 0.97 1992.8 增加了对 SCSI 驱动程序的支持 0.98 1992.9 改善了对 TCP/IP 网络的支持 0.99 1992.12 从新设计内存分配,每个进程有 4G 空间 1.0 1994.3 第一个正式版本2.2 Linux 下 C/C语言编程的主要工具2.2.1 编辑器 vim vim 是 Linux 系统中
常用的文本编辑器。
vim 是在 vi 的基础上增加部分功能发展而来的。
安装好 Linux 操作系统后,一般已经默认安装完毕了 vim 编辑器。
使用 vim 可以方便是对程序进行编辑,vim 提供了相当丰富的命令。
例如:插入命令就有 i,I,a,A;删除整行 dd 等。
正是 vim 提供的丰富的命令使得程序员的手不离开键盘的主键盘区便可以完成对程序的编辑修改。
vim 的操作界面如图 2-1 所示,图中文字为 vim 常用设置。
4北方民族大学学士学位
论文 Linux 下文件压缩和解压缩分析研究与实现 图 2-1 vim 工作界面2.2.2 编译链接器 gcc GNU CC(简称为 gcc)是 GNU 项目中符合 ANSI C 标准的编译系统;gcc能够编译用 C、C和 Object C 等语言编写的程序。
gcc 不仅功能强大,而且可以编译如 C、C、Object C、
Java、Fortran、Pascal 对交互式数据压缩、Modula-3和 Ada 等许多语言。
因此在用 C/C实现文件的压缩与解压缩过程中,强大的gcc 是不可或缺的编译工具。
表 2-2 gcc 支持的后缀名及解释后缀名 对应语言 后缀名 对应语言.c C 原始
程序 .s/S 汇编原始程序.C/cc/cxx C原始程序 .h 预处理文件(头文件).m Objective-C 原始程序 .o 目标文件.i 预处理后 C 程序 .a/so 编译后的库文件.ii 预处理后 C原始程序 gcc 编译分为:预处理阶段,编译阶段,汇编阶段,链接阶段。
gcc 编译过 5北方民族大学学士学位
论文 Linux 下文件压缩和解压缩分析研究与实现程如图 2-2 所示。
图 2-2 gcc 编译过程 预处理阶段,在该阶段,对包含的头文件(include)和宏定义(define、ifdef 等)进行处理 。
可以使用 gcc 的选项“-E” 让 gcc 在预处理结束后停止编译过程。
以程序“hello.c”为例,其命令为:rootlocalhost gcc gcc –E hello.c –ohello.i。
接下来进行的是编译阶段,在这个阶段中,gcc 首先要检查
代码书写是否规范,是否含有语法错误,以确定
代码接下来要做的
工作。
检查结束后,gcc 将把
代码翻译成汇编语言。
此时,用户可以使用rootlocalhost gcc gcc –S hello.i命令进行查看,该选项只是进行编译。
汇编阶段,汇编生成目标文件.o,但是没有经过链接,所以不是可执行文件。
在此可使用选项“-c”就可看到汇编
代码已转化为“.o”的二进制目标
代码了。
命令为:rootlocalhost gcc gcc –c hello.s –o hello.o。
最后的链接阶段, 如果没有特别说明,gcc 会到系统默认的路径“/usr/lib” 6北方民族大学学士学位
论文 Linux 下文件压缩和解压缩分析研究与实现下查找,链接到 libc.so.6 库函数,也即实现了 printf 函数。
2.2.3 调试器 gdb gdb 是一款由 GUN 开发组织研究并发布的 UNIX/Linux 下的程序调试器。
它虽然没有图形界面,但是它拥有强大的功能不亚于
VC 等调试工具。
一般来说,gdb 可以实现一下四个功能:启动目标程序后,按照程序员意愿运行程序;设置断点,程序会在断点处停止;当程序被停住时,可以检查此时程序运行的现场,实时改变程序的运行环境5。
使用命令rootlocalhost gcc gcc –g hello.c –o hello 及rootlocalhost gccgdb hello 来运行 gdb。
此时可以看出在 gdb 的启动画面中指出了 gdb 的版本号、使用的库文件等信息。
然后可以通过设置断点,单步运行等方法来调试程序。
图 2-3 工作环境相关命令 命令格式 含义set args 运行时的参数 指定运行参数show args 查看运行参数path dir 设定程序运行路径show path 查看程序运行路径set environment varvalue 设置环境变量show environment var 查看环境变量cd dir 进入 dir 路径pwd 显示当前路径shell command 运行 shell 中 command 命令2.2.4 工程管理器 make 工程管理器就是管理较多文件的工具。
它能构根据文件时间戳自动发现更新过的文件,从而减少编译的工作量,同时,它通过读入 makefile 文件的内容来执行大量的编译工作6。
makefile 是 make 读入的配置文件。
在一个 makefile 中通常包含如下内容:需要由 make 工具创建的目标体(target),通常是目标文件或可执行文件;要创 7北方民族大学学士学位
论文 Linux 下文件压缩和解压缩分析研究与实现建的目标体所依赖的文件 ; (dependency_file) 创建每个目标体时需要运行的命令(command),这一行必须以制表符(tab 键)开头。
例如对“hell.c”进行编译其makefile 为: make hello.o gcc –c hello.c –o hello.o ls hello.c hello.h hello.o makefile 8北方民族大学学士学位
论文 Linux 下文件压缩和解压缩分析研究与实现 第 3 章 霍夫曼编码原理 霍夫曼编码是熵编码中最常用的压缩与解压缩方法之一。
在熵编码中霍夫曼编码应用较为广泛,而且比较容易实现。
1952 年 David. A. Huffman 提出了一种构造最佳码的方法称为霍夫曼码。
霍夫曼码非常适用于多元独立信源,对于多元独立信源来说是最.