Linux下文件压缩和解压缩分析研究与实现.docx
- 文档编号:10940083
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:54
- 大小:405.26KB
Linux下文件压缩和解压缩分析研究与实现.docx
《Linux下文件压缩和解压缩分析研究与实现.docx》由会员分享,可在线阅读,更多相关《Linux下文件压缩和解压缩分析研究与实现.docx(54页珍藏版)》请在冰点文库上搜索。
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
Inmodernsociety,thedevelopmentofthecommunication,themorecolorfulmodernsociety,wehavelearnedanywhereanytime,anywherearoundtheworld,whichinturnmustrelyonthetransmissionofinformation.Inthehighlydevelopedinformationtechnologyintoday'ssociety,wehaveahigherdemandonthetransmissionofinformation,wehopethattheinformationinthedeliveryprocesscansaveandconfidentialityandnon-destructive,andthefamousHuffmancodingwillbeabletoachievesuchrequirement.AresultofHuffmancodingcompressionanddecompressionoftheinformationonquitenecessary,withC/C++languageforHuffmancodingalgorithmisgiveninordertoachievethecompressionanddecompressionoffiles.TheLinuxsystemprovidesaneditor(vim),compilerlinker(gcc),debugger(gdb)andprojectmanagementtools(make).TheuseofthesetoolscanbeveryconvenientforthedevelopmentoftheCprogramtoimplementfilecompressiondecompression.ThepaperwillusetheoptimalbinarytheHuffmantreedatastructure,aswellasfilecompressionanddecompressionfileI/OoperationintheLinux.
KEYWORDS:
compression,Decompression,Linux,Huffmancoding
目录
第1章绪论1
1.1数据压缩技术简介1
1.2数据压缩的分类1
1.3本文的主要工作2
第2章Linux编程环境概述3
2.1Linux系统的由来及发展现状3
2.2Linux下C/C++语言编程的主要工具4
2.2.1编辑器vim4
2.2.2编译链接器gcc5
2.2.3调试器gdb7
2.2.4工程管理器make7
第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
第1章绪论
1.1数据压缩技术简介
随着计算机技术的发展,数据压缩技术有了越来越重要的作用[1]。
只有数据有重复性,冗余性,才能够实现压缩。
在我们的生活中,一部电影,一首歌曲等,这些数据都有着相当的重复部分。
比如一篇英文文章,即使很长,它也是由26个英文字母组成的。
如果我们对这些数据进行编码,将大大减少数据的存储空间。
总之,生活中的许多数据都是有重复性的,而减少重复,以尽可能少的码来编排一段具有重复性的有效数据便是数据压缩的精髓[2]。
1.2数据压缩的分类
数据压缩的研究己有几十年的历史,其间,人们提出了许多压缩算法。
在分类上,也存在几种不同的方法,一般根据压缩过程是否可逆分为两种:
无失真压缩编码(NoiselessCoding)与有失真压缩编码(NoiseCoding);也有人按编码的建模不同将其分为:
模型基编码和波形基编码;还可按压缩技术所使用的方法进行分类,可分为预测编码(PredictiveCoding)、变换编码(TrannnsformCoding)和统计编码(StatisticalCoding)三大类。
其中第一类是最常用的分类方法[3]。
无失真压缩,也可称之为冗余度压缩(RedundancyCompression),原始数据可通过对压缩数据的解码完整的还原。
这种压缩方法的原理是除去或尽量除去数据中重复和冗余部分,而不丢失其中的信息,从而确保被压缩了的数据还原后与压缩前完全一致。
无失真压缩方法主要应用于不允许出现失真的场合例如对程序文件,文本文件的压缩等。
常用的无失真压缩技术有:
霍夫曼(Huffman)编码,算术(Arithmetic)编码,LZ编码,游程编码(RLE)等。
有失真压缩:
也可称为熵压缩(EntropyCompression),这是一种不可逆压缩。
它主要适用于允许数据出现失真的场合。
例如图像,视频等。
由于丢失的部分信息,所以这种压缩方法可以实现较高的压缩率。
在这些方法中,霍夫曼编码是一种无损压缩方法,霍夫曼编码是可变字长编码(VLC)的一种。
一般用来压缩文本文件,程序文件。
霍夫曼压缩属于可变代码长度算法一族。
意思是不同符号(例如,文本文件中的字符)用一个特定长度的位序列替代。
在文件中出现频率高的符号,使用较短的编码,而那些很少出现的符号,则用较长的编码。
在本文中将利用霍夫曼编码实现对文件的压缩与解压缩。
1.3本文的主要工作
本文的主要内容将分为三部分:
第一部分,将对Linux系统做简单的介绍,对Linux系统中常用的工具简做单的介绍。
第二部分,将对霍夫曼编码进行介绍,并研究利用霍夫曼编码实现对文件的压缩与解压缩。
第三部分,将在Linux系统中,利用霍夫曼编码实现对文件的压缩与解压缩。
并给出给出了具体的实现示例,通过截图的方式直观地表现在论文中。
第2章Linux编程环境概述
实现文本的压缩与解压缩,首先应找到一个非常利于编程的环境。
Linux环境下的C/C++语言程序设计与在其它环境中的C/C++程序设计一样,主要包括编辑器(vim)、编译链接器(gcc)、调试器(gdb)和项目管理工具(make)。
利用这些工具以及Linux开源的特点,在Linux下可以方便的进行C程序软件的开发。
2.1Linux系统的由来及发展现状
Linux系统的创始人是林纳斯·托瓦兹(LinusTorvalds)。
而Linux系统的出现则是无数自由软件运动爱好者智慧的结晶。
Linux是类UNIX操作系统,UNIX上的软件不需或经过小的改动就可以在Linux上运行。
1983年,托瓦兹创建了以创建一个自由的操作系统为目标的GNU计划。
在其后的几年中越来越多的开发者加入这个组织,致力于Linux内核的开发。
终于,在1992年,在GNUGPL下Linux内核被重新授权使用,产生了第一个“Linux发行版本”[4]。
在1994年3月,托瓦兹认为内核的所有组件已经完全成熟,同年,他发布了Linux的1.0版本,Linux内核版本的发展如表2-1所示。
XFree86项目组提供了一个图形化操作界面(GUI)。
同年redhat(红帽)公司和SUSE发行了他们各自的Linux1.0分发版本。
相比windows操作系统,Linux系统最大的特点是开源性。
程序员可以阅读到Linux系统中任何程序的源代码。
也正是这个特点使Linux系统迅速发展。
Linux的应用领域不断扩展,从最早的Web、FTP、邮件服务开始,逐步扩张到个人桌面应用、网络安全、远程教育、集群计算、网络计算、嵌入式系统等各个领域。
更是吸引了想IBM、SUN、惠普这样的IT巨头积极参与到Linux应用的开发和推广中去。
Linux之前主要应用于服务器及计算集群,未来应该该在个人计算机上有所发展,优化目前的图形化界面,以及加快桌应用的开发,以及在智能终端的应用。
表2-1Linux内核版本
版本号
发布时间
说明
0.00
1991.2
两个进程分别显示AAABBB
0.10
1991.9
第一个正式向外公布的Linux内核版本
0.02
1991.10
内部版本,目前已经无法找到
0.10
1991.10
由TedTs'o发布的Linux内核版本
0.11
1991.12
基本可以正常运行的内核版本
0.12
1992.1
主要加入对数学协处理器的软件模拟程序
0.95(0.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.2Linux下C/C++语言编程的主要工具
2.2.1编辑器vim
vim是Linux系统中常用的文本编辑器。
vim是在vi的基础上增加部分功能发展而来的。
安装好Linux操作系统后,一般已经默认安装完毕了vim编辑器。
使用vim可以方便是对程序进行编辑,vim提供了相当丰富的命令。
例如:
插入命令就有i,I,a,A;删除整行dd等。
正是vim提供的丰富的命令使得程序员的手不离开键盘的主键盘区便可以完成对程序的编辑修改。
vim的操作界面如图2-1所示,图中文字为vim常用设置。
图2-1vim工作界面
2.2.2编译链接器gcc
GNUCC(简称为gcc)是GNU项目中符合ANSIC标准的编译系统;gcc能够编译用C、C++和ObjectC等语言编写的程序。
gcc不仅功能强大,而且可以编译如C、C++、ObjectC、Java、Fortran、Pascal对交互式数据压缩、Modula-3和Ada等许多语言。
因此在用C/C++实现文件的压缩与解压缩过程中,强大的gcc是不可或缺的编译工具。
表2-2gcc支持的后缀名及解释
后缀名
对应语言
后缀名
对应语言
.c
C原始程序
.s/S
汇编原始程序
.C/cc/cxx
C++原始程序
.h
预处理文件(头文件)
.m
Objective-C原始程序
.o
目标文件
.i
预处理后C程序
.a/so
编译后的库文件
.ii
预处理后C++原始程序
gcc编译分为:
预处理阶段,编译阶段,汇编阶段,链接阶段。
gcc编译过程如图2-2所示。
图2-2gcc编译过程
预处理阶段,在该阶段,对包含的头文件(#include)和宏定义(#define、#ifdef等)进行处理。
可以使用gcc的选项“-E”让gcc在预处理结束后停止编译过程。
以程序“hello.c”为例,其命令为:
[root@localhostgcc]#gcc–Ehello.c–ohello.i。
接下来进行的是编译阶段,在这个阶段中,gcc首先要检查代码书写是否规范,是否含有语法错误,以确定代码接下来要做的工作。
检查结束后,gcc将把代码翻译成汇编语言。
此时,用户可以使用[root@localhostgcc]#gcc–Shello.i命令进行查看,该选项只是进行编译。
汇编阶段,汇编生成目标文件.o,但是没有经过链接,所以不是可执行文件。
在此可使用选项“-c”就可看到汇编代码已转化为“.o”的二进制目标代码了。
命令为:
[root@localhostgcc]#gcc–chello.s–ohello.o。
最后的链接阶段,如果没有特别说明,gcc会到系统默认的路径“/usr/lib”下查找,链接到libc.so.6库函数,也即实现了printf函数。
2.2.3调试器gdb
gdb是一款由GUN开发组织研究并发布的UNIX/Linux下的程序调试器。
它虽然没有图形界面,但是它拥有强大的功能不亚于VC等调试工具。
一般来说,gdb可以实现一下四个功能:
启动目标程序后,按照程序员意愿运行程序;设置断点,程序会在断点处停止;当程序被停住时,可以检查此时程序运行的现场,实时改变程序的运行环境[5]。
使用命令[root@localhostgcc]#gcc–ghello.c–ohello及[root@localhostgcc]#gdbhello来运行gdb。
此时可以看出,在gdb的启动画面中指出了gdb的版本号、使用的库文件等信息。
然后可以通过设置断点,单步运行等方法来调试程序。
图2-3工作环境相关命令
命令格式
含义
setargs运行时的参数
指定运行参数
showargs
查看运行参数
pathdir
设定程序运行路径
showpath
查看程序运行路径
setenvironmentvar[=value]
设置环境变量
showenvironment[var]
查看环境变量
cddir
进入dir路径
pwd
显示当前路径
shellcommand
运行shell中command命令
2.2.4工程管理器make
工程管理器就是管理较多文件的工具。
它能构根据文件时间戳自动发现更新过的文件,从而减少编译的工作量,同时,它通过读入makefile文件的内容来执行大量的编译工作[6]。
makefile是make读入的配置文件。
在一个makefile中通常包含如下内容:
需要由make工具创建的目标体(target),通常是目标文件或可执行文件;要创建的目标体所依赖的文件(dependency_file);创建每个目标体时需要运行的命令(command),这一行必须以制表符(tab键)开头。
例如对“hell.c”进行编译其makefile为:
$makehello.o
gcc–chello.c–ohello.o
$ls
hello.chello.hhello.omakefile
第3章霍夫曼编码原理
霍夫曼编码是熵编码中最常用的压缩与解压缩方法之一。
在熵编码中霍夫曼编码应用较为广泛,而且比较容易实现。
1952年David.A.Huffman提出了一种构造最佳码的方法称为霍夫曼码。
霍夫曼码非常适用于多元独立信源,对于多元独立信源来说是最佳码。
它充分利用了信源概率分布的特性进行编码,它是一种最佳的逐个符号的编码方法。
3.1霍夫曼编码的理论基础
1928年霍特莱首先提出了信息定量化的初步设想,他定义信息量为:
消息数的对数。
若信源含有m种消息,并且每个消息是以相等可能产生的,那么该信源的信息量为I=-log(m)。
一个事件集合x1,x2,……xn,处于一个基本概率空间,其相应概率为p1,p2,……pn,且p1,p2,……pn之和为1,每一个事件的信息量为I(xk)=-logn(pk),如定义在空间中的每一事件的概率不相等的平均不肯定程度或平均信息量叫做H,则H=E{I(xk)}=∑pkI(xk)=-∑pkloga(pk)。
对于图像来说,n=2m个灰度级xi,则p(xi)为各灰度级出现的概率,熵表示平均信息量为多少比特,熵是编码所需比特数的下限,即编码所需的最少比特[8]。
编码一定要用不比熵少的比特数编码才能完全保持原图像完整信息,这便是图像压缩的下限。
当a=2是,H的单位是比特。
霍夫曼编码是1952年为文本文件而建立,是一种统计编码。
霍夫曼编码是常用的无损编码方法,广泛应用于图像压缩技术。
JPEG标准中的基准模式采用的就是霍夫曼编码。
霍夫曼编码是不定长编码,即代表各元素的码字长度不等。
该编码是基于不同符号的概率分布,在信息源中出现概率越大的符号,相应的码越短;出现概率越小的符号,其码越长,从而达到用尽可能少的码符号表示源数据。
它在变长编码中是最佳的[9]。
在计算机信息处理中,“霍夫曼编码”是一种一致性编码法(又称"熵编码法")。
3.2霍夫曼编码
3.2.1霍夫曼编码步骤
霍夫曼编码一般分为一下几个步骤,设信息源空间为[A*P]:
{A:
a1a2……an}{P(A):
P(a1)P(a2)P(a3)……P(an)}其中P(ak)=1,先用r个码的号码符号集X:
{x1,x2,……xr}对信源A中的每一个符号ak进行编码。
1.把信源符号ai按照其出现的概率的大小顺序排列起来;
2.把最末两个具有最小概率的元素的概率加起来;
3.把该概率之和同其余概率由大到小排队,然后再把两个最小概率加起来,再排队;
4.重复第
(2)、(3)步骤,直到概率和达到1为止:
5.在每次合并消息时,将被合并的消息赋以1和0或0和1;
6.寻找从每个信源符号到概率为1处的路径,记录下路径上的1和0;
7.对每个符号写出"1"、"0"序列(从码数的根到终节点);
8.创建霍夫曼表;
9.压缩编码时,将码值用码字代替;
10.在解码时,将码字用码值代替。
3.2.2霍夫曼表
将所有码值和码字的关系整理成一张表,为了整字节输出码字,表中还含有各码字的长度。
这种表就称为霍夫曼表,如表3-1所示。
进行压缩编码时,只要将码值用码字代替即可。
所以源符码的编码为:
“010*********”。
表3-1霍夫曼表
码值
码字长度
码字
a4
2
00
a1
3
010
a2
3
011
a3
3
101
a5
3
110
a6
3
111
a7
4
1000
a8
4
1001
则平均码长:
B=0.1*3+0.1*3+0.15*3+0.2*2+0.15*30.15*3+0.1*4+0.05*4
=2.95(b)
熵H=2.9087
编码效率N=H/B=98.6%
如果概率统计十分不准确,则压缩效率会变得很低,甚至起不到压缩效果。
霍夫曼树平均码长是霍夫曼树的带权路径长度,由于霍夫曼树是最优二叉树,带权路径长度最小的二叉树,故其压缩效果最好[10]。
3.2.3霍夫曼树
霍夫曼编码实际上构造了一个码树,即最优二叉树。
码树从最上层的端点开始构造,直到树根结束,最后得到一个横放的码树即霍夫曼树。
这个霍夫曼树的建立遵循一个原则——概率大的字符尽量编码短。
反映在霍夫曼树上即从树根到概率大的叶子的路径短。
这里举个例子说明如何生成霍夫曼树。
假设对由a1、a2、a3、a4、a5、a6、a7、a8八个信源符号组成的源信息字符串:
“a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8”进行霍夫曼编码。
首先应对信息中各数字出现的次数进行统计,得出各数字出现的相对概率。
假设各数字出现的次数及概率如表3-2所示。
具体过程是这样的,先将所有符号排成一行构成8个最底层节点。
首先找到概率最小的码值相加即0.05+0.1=0.15,得到新的节点作为这两个节点的根,去掉那两个最小的概率值,同时添加新得到的概率值,然后此时的概率值为:
0.2,0.1,0.1,0.15,0.15,0.15,0.15。
找出此时两个最小的概率值,继续相加得到新的节点作为这两个节点的根。
以此类推知道使概率值相加为1[11]。
规定节点左侧分支为0,右侧分支为2。
若反过来规定亦可。
此时便得到霍夫曼树如图3-1所示。
表3-2各符号出现的次数与概率
码值
a1
a2
a3
a4
a5
a6
a7
a8
次数
2
2
3
4
3
3
3
1
概率
0.1
0.1
0.15
0.2
0.15
0.15
0.1
0.05
图3-1霍夫曼树
对于各值(码值)的代码(码字)就是从根节点出发到底层节点所经历的分支序列。
如a4的代码(码字)为00,a6的码字为111......通常a4和a6等称为码值,00和111等称为码字。
所有码值和码字对应关系如表2-2所示。
表3-3码值和码字对应关系
码值
a1
a2
a3
a4
a5
a6
a7
a8
码字
010
011
101
00
110
111
1000
1001
3.2.4霍夫曼树与压缩编码
在霍夫曼树与压缩编码的小节将举例说明利用霍夫曼编码实现对文本的压缩与解压缩。
在一则文本共1000个字符,分为8种字符(A…H),若不编码压缩文本的总比特数为:
8000bit。
每种字符出现的概率如表3-4所示。
通过此例子将介绍利用霍夫曼编码实现对文本文件压缩与解压缩的原理,以及与普通编码比较霍夫曼编码的压缩效率[12]。
表3-4各个字符出现的概率
字符
A
B
C
D
E
F
G
H
概率
0.05
0.29
0.07
0.08
0.14
0.23
0.03
0.11
若直接编码很容易得出八个字符的编码表3-5。
此时很容易的出通过编码后文章所占总比特数为:
3000bit。
表3-5编码表
A:
000
E:
100
B:
001
F:
101
C:
010
G:
110
D:
011
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Linux 下文 压缩 和解 分析研究 实现
![提示](https://static.bingdoc.com/images/bang_tan.gif)