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(gdbandprojectmanagementtools(make.TheuseofthesetoolscanbeveryconvenientforthedevelopmentoftheCprogramtoimplementfilecompressiondecompression.ThepaperwillusetheoptimalbinarytheHuffmantreedatastructure,aswellasfilecompressionanddecompressionfileI/OoperationintheLinux.
KEYWORDS:compression,Decompression，Linux,Huffmancoding

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
目录
第1章绪论..................................................................................................................11.1数据压缩技术简介..............................................................................................11.2数据压缩的分类..................................................................................................11.3本文的主要工作..................................................................................................2第2章Linux编程环境概述.......................................................................................32.1Linux系统的由来及发展现状...........................................................................32.2Linux下C/C++语言编程的主要工具...............................................................42.2.1编辑器vim....................................................................................................42.2.2编译链接器gcc............................................................................................52.2.3调试器gdb...................................................................................................72.2.4工程管理器make.........................................................................................7第3章霍夫曼编码原理..............................................................................................93.1霍夫曼编码的理论基础.....................................................................................93.2霍夫曼编码.......................................................................................................103.2.1霍夫曼编码步骤........................................................................................103.2.2霍夫曼表....................................................................................................103.2.3霍夫曼树....................................................................................................113.2.4霍夫曼树与压缩编码................................................................................12第4章基于霍夫曼编码的文件压缩与解压缩的实现............................................154.1程序的设计思想...............................................................................................154.2编码程序设计...................................................................................................154.3译码程序设计...................................................................................................174.4软件的运行结果...............................................................................................19第5章结论................................................................................................................21致谢............................................................................................................................22参考文献......................................................................................................................23附录1：程序源代码...................................................................................................25附录2：英文原文.......................................................................................................38


附录3：中文译文.......................................................................................................47


北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现

第1章绪论

1.1数据压缩技术简介

随着计算机技术的发展，数据压缩技术有了越来越重要的作用[1]。只有数据有重复性，冗余性，才能够实现压缩。在我们的生活中，一部电影，一首歌曲等，这些数据都有着相当的重复部分。比如一篇英文文章，即使很长，它也是由26个英文字母组成的。如果我们对这些数据进行编码，将大大减少数据的存储空间。
总之，生活中的许多数据都是有重复性的，而减少重复，以尽可能少的码来编排一段具有重复性的有效数据便是数据压缩的精髓[2]。

1.2数据压缩的分类

数据压缩的研究己有几十年的历史，其间，人们提出了许多压缩算法。在分类上，也存在几种不同的方法，一般根据压缩过程是否可逆分为两种:无失真压缩编码(NoiselessCoding与有失真压缩编码(NoiseCoding;也有人按编码的建模不同将其分为：模型基编码和波形基编码；还可按压缩技术所使用的方法进行分类，可分为预测编码(PredictiveCoding、变换编码(TrannnsformCoding和统计编码(StatisticalCoding三大类。其中第一类是最常用的分类方法[3]。
无失真压缩，也可称之为冗余度压缩(RedundancyCompression，原始数据可通过对压缩数据的解码完整的还原。这种压缩方法的原理是除去或尽量除去数据中重复和冗余部分，而不丢失其中的信息，从而确保被压缩了的数据还原后与压缩前完全一致。无失真压缩方法主要应用于不允许出现失真的场合例如对程序文件，文本文件的压缩等。常用的无失真压缩技术有:霍夫曼(Huffman编码，算术(Arithmetic编码，LZ编码，游程编码(RLE等。
有失真压缩:也可称为熵压缩(EntropyCompression，这是一种不可逆压缩。
1

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
它主要适用于允许数据出现失真的场合。例如图像，视频等。由于丢失的部分信息，所以这种压缩方法可以实现较高的压缩率。
在这些方法中，霍夫曼编码是一种无损压缩方法，霍夫曼编码是可变字长编码(VLC的一种。一般用来压缩文本文件，程序文件。霍夫曼压缩属于可变代码长度算法一族。意思是不同符号（例如，文本文件中的字符）用一个特定长度的位序列替代。在文件中出现频率高的符号，使用较短的编码，而那些很少出现的符号，则用较长的编码。在本文中将利用霍夫曼编码实现对文件的压缩与解压缩。
1.3本文的主要工作

本文的主要内容将分为三部分：
第一部分，将对Linux系统做简单的介绍，对Linux系统中常用的工具简做单的介绍。
第二部分，将对霍夫曼编码进行介绍，并研究利用霍夫曼编码实现对文件的压缩与解压缩。
第三部分，将在Linux系统中，利用霍夫曼编码实现对文件的压缩与解压缩。并给出给出了具体的实现示例，通过截图的方式直观地表现在论文中。

2

北方民族大学学士学位论文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之前主要应用于服务器及计算集群，未来应该该在个人计算机上有所发展，优化目前的图形化界面，以及加快桌应用的开发，以及在智能终端的应用。
3

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
表2-1Linux内核版本
版本号0.000.100.020.100.110.120.95(0.130.960.970.980.991.0
发布时间1991.21991.91991.101991.101991.121992.11992.31992.51992.81992.91992.121994.3
说明
两个进程分别显示AAABBB
第一个正式向外公布的Linux内核版本内部版本，目前已经无法找到由TedTs'o发布的Linux内核版本基本可以正常运行的内核版本
主要加入对数学协处理器的软件模拟程序开始加入虚拟文件系统思想的内核版本开始加入网络支持和虚拟文件系统VFS增加了对SCSI驱动程序的支持改善了对TCP/IP网络的支持
从新设计内存分配，每个进程有4G空间第一个正式版本

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常用设置。
4

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现

图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/cc/cxx.m.i.ii
对应语言C原始程序C++原始程序Objective-C原始程序预处理后C程序预处理后C++原始程序
后缀名.s/S.h.o.a/so
对应语言汇编原始程序预处理文件（头文件）目标文件编译后的库文件
gcc编译分为：预处理阶段，编译阶段，汇编阶段，链接阶段。gcc编译过
5

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
程如图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‖
6

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
下查找，链接到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运行时的参数showargspathdirshowpath
setenvironmentvar[=value]showenvironment[var]cddirpwd
shellcommand
指定运行参数查看运行参数设定程序运行路径查看程序运行路径设置环境变量查看环境变量进入dir路径显示当前路径
运行shell中command命令
含义
2.2.4工程管理器make
工程管理器就是管理较多文件的工具。它能构根据文件时间戳自动发现更新过的文件，从而减少编译的工作量，同时，它通过读入makefile文件的内容来执行大量的编译工作[6]。
makefile是make读入的配置文件。在一个makefile中通常包含如下内容：需要由make工具创建的目标体（target），通常是目标文件或可执行文件；要创
7

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
建的目标体所依赖的文件（dependency_file）；创建每个目标体时需要运行的命令（command），这一行必须以制表符（tab键）开头。例如对―hell.c‖进行编译其makefile为：
$makehello.ogcc–chello.c–ohello.o$ls
hello.chello.hhello.omakefile

8

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
第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]。在计算机信息处理中，―霍夫曼编码‖是一种一致性编码法（又称"熵编码法"）。
9

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
3.2霍夫曼编码

3.2.1霍夫曼编码步骤
霍夫曼编码一般分为一下几个步骤，设信息源空间为[A*P]:{A:a1a2……an}{P(A:P(a1P(a2P(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所示。进行压缩编码时，只要将码值用码字代替即可。所以源符码的编码为：
“010010011011011010000000011011011010000100001001”。
10

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
表3-1霍夫曼表
码值a4a1a2a3a5a6a7a8
码字长度
23333344
码字0001001110111011110001001
则平均码长：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,
11

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
0.1,0.15,0.15,0.15,0.15。找出此时两个最小的概率值，继续相加得到新的节点作为这两个节点的根。以此类推知道使概率值相加为1[11]。规定节点左侧分支为0，右侧分支为2。若反过来规定亦可。此时便得到霍夫曼树如图3-1所示。
表3-2各符号出现的次数与概率
码值次数概率
a120.1
a220.1
a330.15
a440.2
a530.15
a630.15
a730.1
a810.05

图3-1霍夫曼树
对于各值（码值）的代码（码字）就是从根节点出发到底层节点所经历的分支序列。如a4的代码（码字）为00，a6的码字为111......通常a4和a6等称为码值，00和111等称为码字。所有码值和码字对应关系如表2-2所示。
表3-3码值和码字对应关系
码值码字
a1010
a2011
a3101
a400
a5110
a6111
a71000
a81001

3.2.4霍夫曼树与压缩编码

在霍夫曼树与压缩编码的小节将举例说明利用霍夫曼编码实现对文本的压
12

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
缩与解压缩。
在一则文本共1000个字符，分为8种字符(A…H,若不编码压缩文本的总比特数为：8000bit。每种字符出现的概率如表3-4所示。通过此例子将介绍利用霍夫曼编码实现对文本文件压缩与解压缩的原理，以及与普通编码比较霍夫曼编码的压缩效率[12]。
表3-4各个字符出现的概率
字符概率
A0.05
B0.29
C0.07
D0.08
E0.14
F0.23
G0.03
H0.11
若直接编码很容易得出八个字符的编码表3-5。此时很容易的出通过编码后文章所占总比特数为：3000bit。
表3-5编码表
A：000B：001C：010D：011
E：100F：101G：110H：111
若使用霍夫曼编码，以3.2.3介绍原理可以得出霍夫曼树如图3-2。此时规定左支为0，右支为1。便容易得出霍夫曼编码表如表3-6所示。此时得出总比特数为：4*50+2*290+4*70+4*80+3*140+4*30+2*230+3*110=2710bit。对比原文的8000bit以及普通编码的3000bit可以看出霍夫曼编码可以很好的实现对文本文件的压缩[13]。
综合本小节的叙述可以得出霍夫曼编码实现对数据进行压缩存储的步骤：对数据进行统计，统计每种符号发生的概率；根据符号概率的大小，生成霍夫曼树；根据霍夫曼树对每个符号编写(编码表；按照给定的码表对数据进行编码；解码时需要原编码方案[14]。译码时从根结点出发，按二进制位串中的0和1确定是进入左分支还是右分支，当到达叶子结点时译出该叶子对应的字符。然后重新从根节点出发重复上述步骤，直至结束。

13

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现

图3-2霍夫曼树表3-6霍夫曼编码表
A：0110B：11C：1000D：1001E：101F：0111G：00H：010
编码长度
42443423
频度50290708014030230110

14

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
第4章基于霍夫曼编码的文件压缩与解压缩的实现

本章将主要介绍利用C语言编程实现对文件的压缩与解压缩，编程环境为Linuxredhat5.5（虚拟机）。
4.1程序的设计思想

先是读取文件，统计文件中不同字符出现的次数，并存入数组中，然后将数组中不同的字符对应的ASCII值存入另外数组中，按照数组个ASCII及相应出现的频率的来建立霍夫曼编码，然后将码表存入压缩文件，再将各字符对应的霍夫曼编码写入压缩文件中，实现文件压缩。解压缩时也是先把文件整体读入，通过霍夫曼编码的长短，依次解码，从原来的位存储还原到字节存储[15]。


统计字符，得出统计出字符的权值n
生成霍夫曼树
建立霍夫曼树
根据霍夫曼树编码根据霍夫曼树解码

对编码进行压缩
对二进制文件进行
解码
生成二进制文件
生成对应文件
图4-1程序设计思想
4.2编码程序设计

首先运行的时候，用户主界面上有菜单提示该如何使用软件，如图4-2。根
15

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
据菜单提示选择所要执行的选项，依次进行，因为各个环节之间有先后顺序。第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩。若打不开，则继续输入。
文件将信息存放在字符数组中，计算每个字符出现的次数，申请一个结构体数组空间，用读取的字符减去字符结束符作为下标记录字符的频率[16]。将所记录的字符的频率作为权值来创建霍夫曼树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。根据创建的霍夫曼树来确定个字符的01编码，左侧结点0，侧结点为1。读取文件，依次将每个字符用他们的编码表示，即完成一次编码。

图4-2压缩软件界面
16

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现

开始
键入文件名
读文件操作
N
字符权值统计
文件是否读完
Y生成霍夫曼树
生成霍夫曼编码
生成编码文件
结束
图4-3编码程序流程图

4.3译码程序设计

读取编码文件，依据创建的霍夫曼树，定义一个指针指向根结点。从根结点开始，每读一个字符，指针变化一次（当读取的字符是‗1‘时，指针指向当前所指结点的右侧结点，当读取的字符是‗0‘时，指针指向当前所指结点的左侧结点），直至该指针所指结点为叶子结点时结束（即当结点的左右结点均为空时）。将当前叶子结点所代表的字符值输出到译码文件中，依次读取编码文件中的字符，按
17

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
照上述方法依次进行下去直至文件结束。
开始
键入文件名
读文件操作
文件是否读完
N
扫描霍夫曼树
Y
N
是否为叶节点
Y
译码写入新文件，并返回根节点
是否为根节点
N
Y输出错误编码
结束
图4-4译码流程图
18

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
4.4软件的运行结果

以压缩本文附录程序文件为例，验证软件的正确性。首先查看源代码文件属性，大小为11.3KB如图4-5所示。然后进行压缩，得到文件aa.hub大小为8.5KB如图4-6所示。

图4-5压缩前文件属性

图4-6压缩后文件属性
最后执行解压缩，对文件aa.hub进行解压缩操作得到文件c.cpp，类型与原文件a.cpp一致，即C++源代码。大小同位11.3KB。如图4-7所示。
19

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现

图4-7解压后文件属性
20

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
第5章结论
在当今信息时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，霍夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
在毕业设计过程中，我选择了《linux下文件压缩和解压缩分析研究与实现》这一课题。在这个完成这个课题的过程中。我通过书籍和网络等途径学习到了以前所未学到的知识。同时也加深了我对已学习知识的理解。对Linux系统，对C/C++语言有了根深的了解。理解了文件压缩与解压缩的意义。本次课程设计所实现的软件比较适用于文本文件。
由于知识水平的限制本文的程序利用的是静态的霍夫曼编码，有很大的局限性。相比自适应霍夫曼编码，静态霍夫曼编码所需时间较长，效率较低。在实际的运用中，对文件的压缩与解压缩一般采用的是自适应霍夫曼编码。
21

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
致谢
在这里我首先要感谢我的论文知道老师——XX教授。在我完成论文的过程中，是您给予了我巨大的帮助。您治学严谨，知识渊博，在课题的选定直到到论文撰写的最终完成的过程中，XX教授都始终给予我细心的指导。在此谨向您致以诚挚的谢意和崇高的敬意。
我要感谢我的父母，是你们，含辛茹苦养育了我；是你们，一直在背后默默支持着我；是你们，给了我所有的一切，给了我今天。
感谢我的大学，在这里，各位老师教会了我各种专业知识，教会了我做人的道理，感谢我的各位老师；在这里，我遇到了我的同学，我的挚友，在我遇到困难的时候，是你们陪在我的身边，和我一起共渡难关，我们一同嬉笑过、拼搏过，感谢我的朋友以及同学。
22

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
参考文献
[1]傅祖芸.信息论——基础理论与应用[M].北京：电子工业出版社，2007.[2]BrianWKernighan,DennisMRitche.C语言程序设计语言[M].北京：机械
工业出版社，2004.
[3]MarkAllenWeiss.数据结构与算法分析——C语言描述[M].北京：机械工业
出版社，2004.
[4]栾阳.关于数据压缩技术的研究[J].硅谷，2009.15(12：192-197.[5]曾玲.数据压缩技术在通信中的应用[D].四川：西南交通大学，2003.[6]张敬敬，朱永利，郝宁等.Huffman压缩算法在智能电网通信系统中的应用
[J].河北工业科技，2001，9(19A：123-130.
[7]赵晓莉.浅析多媒体数据压缩技术[J].科技信息，2003，2(10：23-31.[8]董雨西.无损音频编码算法研究[D].天津：天津大学，2011.[9]SayoodK.数据压缩导论[M].北京：人民邮电出版社，2009.[10]吴乐南.数据压缩[M].北京：电子工业出版社，2012.
[11]金子一.图像信源压缩编码及信道传输理论与新技术[M].北京：北京工业大
学出版社，2006.
[12]鸟哥.鸟哥的Linux私房菜——基础学习篇[M].北京：人民邮电出版社，2010.[13]刘忆智.Linux从入门到精通[M].北京：清华大学出版社，2010.
[14]杨宗德，吕光宏，刘雍.Linux高级程序设计[M].北京：清华大学出版社，2009.[15]邢国庆.RedHatEnterpriseLinux6从入门到精通[M].北京：电子工业出版
社，2011.
[16]霍顿.C语言入门经典[M].北京：清华大学出版社，2008.
23

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
[17]曾俊.无损压缩技术在姿态数据采集系统中的应用研究[D].南京：南京理工
大学，2009.
[18]庄明强.基于数据压缩与GPRS的配变数据采集与监控系统研究[D].杭州:
浙江大学，2008.
[19]王敬生,罗家融,李俊照.Linux和Unix编译链接配置文件分析[J].皖西学院学
报，2009，10(5：18-22.
[20]刘燕清,龚声蓉.基于一次排序动态编码的Huffman编码算法[J].计算机应
用与软件,2009,8(9A:55-62.
[22]折小利.抽样数字图像压缩方法的改进[D].西安：西安电子科技大学，2009.[23]路淼，周卫东.基于嵌入式零树编码(EZW的脑电信号压缩算法[J].航天医
学与医学工程,2004,12(9:59-72.
[24]韩菲.基于雷达视频的Huffman编码研究[J].舰船电子工程，2004，
13(15:110-124.
24

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
附录1：程序源代码
#include
#include#include#include#include#include
structhuofuman{
unsignedcharb;//记录字符在数组中的位置longcount;//字符出现频率（权值）longparent,lch,rch;//定义霍夫曼树指针变量charbits[256];//定义存储霍夫曼编码的数组}
header[512],tmp;
//压缩函数voidcompress({
charfilename[255],outputfile[255],buf[512];unsignedcharc;longi,j,m,n,f,lh=0;
longmin1,pt1,flength,length1,length2;
doublediv;
FILE*readfile,*writefile;


25

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
cout<<"请输入要压缩的文件名：";cin>>filename;
readfile=fopen(filename,"rb";if(readfile==NULL
cout<<"输入压缩之后的文件名：";
{cout<<"文件打开失败！！,请检查该文件是否存在，或遇到未知文件"<;return;}
cin>>outputfile;
writefile=fopen(strcat(outputfile,".hub","wb";if(writefile==NULL
{
cout<<"文件压缩失败!"<
return;
while(!feof(readfile
{
fread(&c,1,1,readfile;}
flength=0;
header[c].count++;//字符重复出现频率+1flength++;//字符出现原文件长度+1
}
lh=flength;
flength--;
length1=flength;//原文件长度用作求压缩率的分母header[c].count--;for(i=0;i<512;i++
26

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现

{
if(header[i].count!=0header[i].b=(unsignedchari;
/*将每个霍夫曼码值及其对应的ASCII码存放在一维数组header[i]中，且编码表中的下标和ASCII码满足顺序存放关系*/
elseheader[i].b=0;
header[i].parent=-1;header[i].lch=header[i].rch=-1;//对结点进行初始化
}
for(i=0;i<256;i++//根据频率（权值）大小，对结点进行排序，选择较小的结点进树
{
for(j=i+1;j<256;j++{
if(header[i].count{
tmp=header[i];
header[i]=header[j];header[j]=tmp;
}
for(i=0;i<256;i++
if(header[i].count==0break;}
}
n=i;//外部叶子结点数为n个时，内部结点数为n-1，整个霍夫曼树的需要的结点数为2*n-1.m=2*n-1;
for(i=n;i//构建霍夫曼树
{
27

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
min1=999999999;//预设的最大权值，即结点出现的最大次数
for(j=0;j

{
if(header[j].parent!=-1continue;
/*parent!=-1说明该结点已存在霍夫曼树中，跳出循环重新选择新结点*/if(min1>header[j].count{



pt1=j;
min1=header[j].count;continue;}
}


header[i].count=header[pt1].count;
header[pt1].parent=i;树中结点之间的关系
header[i].lch=pt1;min1=999999999;for(j=0;j{


if(header[j].parent!=-1continue;if(min1>header[j].count{



pt1=j;
min1=header[j].count;continue;}
}


header[i].count+=header[pt1].count;header[i].rch=pt1;header[pt1].parent=i;
28
//依据parent域值（结点层数）确定//计算左分支权值大小//计算右分支权值大小


北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现

}
for(i=0;i//霍夫曼无重复前缀编码{
f=i;
header[i].bits[0]=0;//根结点编码0while(header[f].parent!=-1

{
j=f;
f=header[f].parent;
if(header[f].lch==j//置左分支编码0


{
j=strlen(header[i].bits;
memmove(header[i].bits+1,header[i].bits,j+1;//依次存储连接―0‖―1‖编码
header[i].bits[0]='0';


}
else//置右分支编码1{
j=strlen(header[i].bits;
memmove(header[i].bits+1,header[i].bits,j+1;header[i].bits[0]='1';
}
fseek(readfile,0,SEEK_SET;//从文件开始位置向前移动0字节，即定位到
}
}
文件开始位置
fwrite(&flength,sizeof(int,1,writefile;
/*用来将数据写入文件流中，参数flength指向欲写入的数据地址，总共写入的字符数以参数size*int来决定，返回实际写入的int数目1*/fseek(writefile,8,SEEK_SET;
29

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
buf[0]=0;//定义缓冲区,它的二进制表示00000000f=0;pt1=8;
/*假设原文件第一个字符是"A"，8位2进制为01000001，编码后为0110识
别编码第一个'0'，那么我们就可以将其左移一位，看起来没什么变化。下一个是'1'，应该|1，结果00000001同理4位都做完，应该是00000110，由于字节中的8位并没有全部用完，我们应该继续读下一个字符，
根据编码表继续拼
完剩下的4位，如果字符的编码不足4位，还要继续读一个字符，如果字符编码超过4位，那么我们将把剩下的位信息拼接到一个新的字节里*/while(!feof(readfile
{
c=fgetc(readfile;
f++;
for(i=0;i

{}
strcat(buf,header[i].bits;
if(c==header[i].bbreak;
j=strlen(buf;c=0;储

{
for(i=0;i<8;i++{
if(buf[i]=='1'c=(c<<1|1;

while(j>=8//对霍夫曼编码位操作进行压缩存
elsec=c<<1;


}
fwrite(&c,1,1,writefile;
30

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
pt1++;//统计压缩后文件的长度strcpy(buf,buf+8;//一个字节一个字节拼接j=strlen(buf;}
if(f==flengthbreak;
}

if(j>0存储{

strcat(buf,"00000000";
for(i=0;i<8;i++{


if(buf[i]=='1'c=(c<<1|1;
elsec=c<<1;}


fwrite(&c,1,1,writefile;
pt1++;}

fseek(writefile,4,SEEK_SET;
fwrite(&pt1,sizeof(long,1,writefile;fseek(writefile,pt1,SEEK_SET;fwrite(&n,sizeof(long,1,writefile;for(i=0;i{

fwrite(&(header[i].b,1,1,writefile;c=strlen(header[i].bits;fwrite(&c,1,1,writefile;j=strlen(header[i].bits;
if(j%8!=00
31
//对霍夫曼编码位操作进行压缩
//若存储的位数不是8的倍数，则补

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现


{
for(f=j%8;f<8;f++
strcat(header[i].bits,"0";

}
while(header[i].bits[0]!=0{
c=0;
for(j=0;j<8;j++/*字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接*/


{
if(header[i].bits[j]=='1'c=(c<<1|1;//|1不改变原位置上的
―0‖―1‖值
elsec=c<<1;


}
strcpy(header[i].bits,header[i].bits+8;//把字符的编码按原先存
储顺序连接
fwrite(&c,1,1,writefile;
cout<<"文件压缩成功!"<length2=pt1--;
div=((doublelength1-(doublelength2/(doublelength1;//计算文件的压}
}
缩率
fclose(readfile;fclose(writefile;
cout<<"压缩率为："<return;}
32

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
//解压
voiddecompression({
charfilename[255],outputfile[255],buf[255],bx[255];
unsignedcharc;longi,j,m,n,f,p,l;longflength;
doublelh;
FILE*readfile,*writefile;
readfile=fopen(strcat(filename,".hub","rb";if(readfile==NULL
{
cout<<"文件打开失败！！,请检查该文件是否存在，或遇到未知文件cout<<"请输入要解压文件名:";cin>>filename;
"<
return;
}
cout<<"输入解压后的文件名：";cin>>outputfile;
writefile=fopen(outputfile,"wb";if(writefile==NULL
{
cout<<"文件解压失败！"<

return;
}

fread(&flength,sizeof(long,1,readfile;//读取原文件长度，对文件进行
33

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
定位
lh=flength;
fread(&f,sizeof(long,1,readfile;fseek(readfile,f,SEEK_SET;fread(&n,sizeof(long,1,readfile;for(i=0;i
{
fread(&header[i].b,1,1,readfile;
fread(&c,1,1,readfile;
p=(longc;//读取原文件字符的权值header[i].count=p;header[i].bits[0]=0;if(p%8>0m=p/8+1;elsem=p/8;for(j=0;j

{
fread(&c,1,1,readfile;
f=c;
itoa(f,buf,2;//将f转换为二进制表示的字符串f=strlen(buf;for(l=8;l>f;l--

}
{}
strcat(header[i].bits,buf;
strcat(header[i].bits,"0";
header[i].bits[p]=0;
}
for(i=0;i//根据霍夫曼编码的长短，对结点进行排序
{
34

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现


for(j=i+1;j{
if(strlen(header[i].bits>strlen(header[j].bits{
tmp=header[i];
header[i]=header[j];header[j]=tmp;
}
}
}
p=strlen(header[n-1].bits;fseek(readfile,8,SEEK_SET;m=0;bx[0]=0;
while(1//通过霍夫曼编码的长短，依次解码，从原来的位存储还原到字节存储
{
while(strlen(bx<(unsignedintp{
fread(&c,1,1,readfile;
f=c;itoa(f,buf,2;f=strlen(buf;
for(l=8;l>f;l--//在单字节内对相应位置补0

}
35
{}
strcat(bx,buf;
strcat(bx,"0";

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现


for(i=0;i{}
strcpy(bx,bx+header[i].count;
if(memcmp(header[i].bits,bx,header[i].count==0break;
/*从压缩文件中的按位存储还原到按字节存储字符，字符位置不改变*/

c=header[i].b;
fwrite(&c,1,1,writefile;
m++;//统计解压缩后文件的长度if(m==flengthbreak;//flength是原文件长度
fclose(readfile;fclose(writefile;
cout<<"文件解压成功!"<}/*主函数*/voidmain({
cout<<"--------霍夫曼解、压文件系统---------"<cout<<"1.对文件进行压缩"<cout<<"2.对文件进行解压"<cout<<"0.退出系统"<

cout<<"注意：压缩输入1，解压输入2，退出选择0"<

}
while(1{
inta;cout<<"请选择项目:";cin>>a;



36
while(a!=0&&a!=1&&a!=2

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
{


cout<<"输入错误，请核对后再输入"<
cout<<"请选择项目:";cin>>a;}
switch(a{
case1:compress(;break;case2:decompression(;break;case0:exit(0;}}
system("pause";system("cls";}
//任意键继续//清屏37

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
附录2：英文原文
From：www.mdpi.com/1999-4893/3/1/63Authors:R.M.Capocelli

InteractiveCompressionofDigitalData

Abstract:Ifwecanusepreviousknowledgeofthesource(ortheknowledgeofa
source.thatiscorrelatedtotheonewewanttocompresstoexploitthecompressionprocessthenwecanhavesignificantgainsincompression.Bydoingthisinthefundamentalsource.codingtheoremwecansubstituteentropywithconditionalentropyandwehaveanewtheoreticallimitthatallowsforbettercompression.Todothis,whendatacompressionisusedfordatatransmission,wecanassumesomedegreeofinteractionbetweenthecompressorandthedecompressorthatcanallowamoreefficientusageofthepreviousknowledgetheybothhaveofthesource.Inthispaperwereviewpreviousworkthatappliesinteractiveapproachestodatacompressionanddiscussthispossibility.
Keywords:datacompression,entropy,conditionalcompression
1Introduction

DataCompressioniscrucialforthetransmissionandstorageofdigitaldata.Itispossibletoimprovethecompressionperformancewhenwecanusepreviousknowledgeoftheemittingsourceinthecompressionprocess.Inthiscaseinthefundamentalsourcecodingtheoremwecansubstituteentropywithconditionalentropyandwehaveanewtheoreticallimitthatallowsforbettercompression.
Whendatacompressionisusedfordatatransmissionwemightassumesomedegreeofinteractionbetweenthecompressorandthedecompressorthatallowsamoreefficientusageofthepreviousknowledgeofthesourcetheybothmighthave.Thepriceweaccepttopay,insomecases,isanegligibleprobabilityoferrors.
38

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
Inthispaperwereviewrecentworkthatappliespreviousknowledgeoftheemittingsourcetodatacompressionandinteractiveapproachesanddiscussthesepossibilities.Wewillconcentrateonlossless,dictionarybased,compressionalgorithms.
Inthenextsectionwereviewrelevantconceptsaboutthetheoreticallimitsofdatacompressionand
aboutthedictionarybasedcompressionmethods.Section3discusseshowtousethepreviousknowledgeofthesourcewhenthesharedknowledgeisrepresentedbycommon,identicalfilesthatbothsideshaveavailablebutthereisnopossibilityofinteractionbetweentheSenderandtheReceiverthatneedtocommunicate.Section4reviewsthesituationinwhichbothSenderandReceiverhaveknowledgeofthesource,butdonotsharenecessarilythesame,identical,files.Inthiscase,bytakingadvantageoftheinteractionbetweenthetwocommunicationsides,SenderandReceivercanimprovethecompressionprocessbyusingthesharedknowledgeiftheyacceptasmallpossibilityofcommunicationerrors.Section5presentsourconclusionsandpointstonewresearchdirections.
2Compression,EntropyandDictionaries

Dataandinformationtodayaredigital.Weneeddatacompressiontodealwithdigitaldata:withoutcompressionwecannotstoreand/ortransmitthehugeamountofdatawetreateveryday.Thetheoreticalbackgroundofdatacompressiontechniquesisstrongandwellestablished.ItdatesbacktotheseminalworkofClaudeElwoodShannon(see.Inthelate1940s,hegaveaformaldefinitionofthenotionofinformationcontentorrandomnessofasource,whichhecalledentropy.Thistheoreticalbackgroundgivespreciselimitsontheperformanceofacompressionalgorithm.
Anyprocessthatgeneratesinformationcanbeviewedasasourcethatemitsasequenceofsymbolsfromafinitealphabet.Thesourceoutputcanbeseenasasequenceofwords:i.e.,finitelengthsequencesofalphabetsymbols.Fromthepracticalpointofviewtodividethesourceoutputsintowordsmightinvolveasemanticanalysisthatdependsonthesourceandthatitispossibleonlyiftheoutputofthesourceisinterpretedinadeterminatecontext.Forexample,awordofasource
39

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
thatemitsEnglishsentencescanbeasequenceofoneormorecommonEnglishwords,includingblanks,punctuationmarks,etc.Ifweconsiderafirst-ordersourceS,inwhichsuccessivesymbolsarestatisticallyindependent,ShannonandWeaverin[1]showedthat,giventhesetofprobabilitiesP={p1,p2,...,pnforthesourcesymbols,theoptimalexpectednumberofcodebitsis:

aquantitywhichtheycalledtheEntropyofthesourceS,usuallydenotedbyH(S.ConditionalentropyH(S1|S2isthenaturalanalogueoftheentropyH(Sbutitisbasedontheconditionalprobability.Itcanbeshownthat:H(S1|S2≤H(S1.
Entropyisameasureofuncertaintyaboutanevent:ithasazerovalueifandonlyifthereisabsolutecertaintyanditismaximalwhenalltheeventsareequiprobable:i.e.,thereisabsoluteuncertainty.The―fundamentalsource-codingtheorem‖canbestatedasinStorer:―LetSbeafirst-ordersourceoveranalphabetletbeanalphabetofr>1characters.ThenencodingthecharactersofSwithcharactersofrequiresanaverageofHr(scharactersofpercharacterofFurthermore,foranyrealnumber>0thereexistsacodingschemethatusesanaverageofHr(s+ofpercharacterofBecauseofthefundamentalsourcecodingtheorementropyisalimittothelengthofthestringthatwecanusetolosslesscodeamessage.
Todaylosslesscompressorsareveryefficient.Whileitisnotpossibletoprovethattheyalwaysachievethetheoreticallimit,theperformancesofthestateoftheartcompressorsforspecifictypesofdata,likenaturallanguagetext,arecertainlyveryclosetothistheoreticallimit.Currentresearchonlosslesscompressionfocusesondevelopingcompressorsfornewtypesofdigitaldataoronimproving,oftenonlybysmallamounts,existingcompressorsforaspecificclassofdata.Evenasmallimprovementisanimportantachievement,giventheeconomicalimpactitcanhaveondatatransmissionandstorage.Manydatacompressionmethodsarebasedonthenotionof―dictionary‖.Inthispaperwewillprimarilyconsiderdictionarybasedcompressionmethods.
Dictionariescanbestatic,i.e.,builtatthebeginningofthecompression/communicationprocessandneverupdatedandinthiscasethecompressionmethodiscalledstaticdictionarymethod.Otherwise,ifthedictionariesareconsistentlyandindependentlybuilt,maintained,andupdatedbybothcompressor
40

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
anddecompressor,thenthecompressionmethodiscalleddynamicdictionarymethod.Wecanusestaticdictionarymethodswhenthesourceisknowninadvance.Whenweusedatacompressiontocommunicate,theSenderandtheReceiverusethesame(staticdictionaryandeventually,atthebeginningofthecommunication,theSenderneedstosendthedictionarytotheReceiver.forexample,invectorquantizationalgorithmsthecompressorbuildsupadictionaryonatrainingsetofimagesanditusesthisdictionarytocompressthenewdata.Thedecompressorneedsthesamedictionarytodecompress;thereforethecompressorshalltransmitthisdictionarytothedecompressor.
Thecostofmakingthisdictionaryavailabledependsonitsdimensions.Generallythiscostisnotconsideredintheanalysisofastaticdictionarycompressionmethodbyusingtheargumentthattheconstantcostcanbeamortizedovertimebycompressingalargeamountofdata.Inreallifesituationsthisisnotalwaystrue.Frequentlywehaveascompressiontargetonlysmallormediumsizefiles,thatrepresentcomputerprograms,images,textdata,music,videos,etc.Forexampleitisoftennecessarytosendonlyafewcomputerprogramsorafewimagesfromasourcetoadestination,possiblyviaatelephonelinebyusingamodemorviaafastinternetconnection.Inthesecasesthecostofsendingthedictionarymighthaveanimportantimpactonthetotalcostofthecommunication,makingstaticcompressionmethodsunpractical.
3ConditionalCompression

OneoptionwehavetoincreasecompressionistousetheknowledgeofsimilarmessagesthatSenderandReceiverhavecompressedinthepastfromthesamesourceandtodesignalgorithmsthatefficientlycompressanddecompressgiventhispreviousknowledge:bydoingthistheconditionalentropyisthenewtheoreticallimitanditallowsforbettercompression.
Figure1(from[3]showstheresultsofthisapproachforMacNS6FullInstaller.sea.bin.Wehaveplottedonthex-axisthenumberof2,000bytessegmentsonwhichweapplythedifferenceoperator(betweenthisfileandMacNS6FullInstaller2.sea.binandonthey-axisthesizeofthecompressedfile.For
41

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
conveniencewehavealsoreportedthesizeofthegzipcompressedversionofMacNS6FullInstaller.sea.bin(thestraightline.
Figure1.Applyingthedifferenceoperatorbetweenfile1

Weseeinthefigurethatthefirstpartofthefirstfileandthefirstpartofthesecondfile(uptoaboutthefirsttwohundreds2,000bytessegmentsarestrictlycorrelated.Byoperatingadifferencebetweentheactualdistributionofthesoftwareandthepreviousversionwehaveusedpreviousknowledgeofthesource(ortheknowledgeofasourcethatiscorrelatedtotheonewewanttocompresstoexploitthecompressionprocess.Thesavingswehaveobtainedarelimitedbecauseoftheoriginalnatureandcorrelationofthefilesweareexperimenting,butitissignificantthatevenwiththistypeofdataandatleastinthiscase,thisapproachworks.theexperimentwehaveusedasegmentationofthetwofilesinfixedsizesegments.Thisimpliesasortofalignmentofthetwofileswearecomparing.Whileithasbeenproventhattherelated―optimalvectoralignmentproblem‖isNPcomplete(seeCarpentieriandStorer[4],wecanexpecttobeabletofindheuristicallygoodapproximationsofthisoptimalalignmentandthereforetofurtherimprovethecompressionobtainedinsimilarexperimentsbyacarefulalignmentofthefiles.
Cilibrasiin[10]andCilibrasiandVitanyin[11]studiedtheNormalizedCompressionDistance(NCDaparameter-free,universal,similaritymeasurebasedonadatacompressor.NCDisanon-negativenumberrepresentinghowdifferenttwofilesare.NCDisanewwayoflookingatdatacompressionthatallowsustousecompressionprogramsforawidevarietyofproblems,suchaslearning,clusteringandclassification,datamining,etc.
42

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
NCDgivesadifferentwayoflookingattheproblemwedealwithinthispaper,theintuitionisthatiftwofilesareclose(intheNCDsensethenprobablywecandoabetterjobinsendingoneofthemtoadestinationthatalreadyhastheotherfileifwecanuseinteraction.
4InteractiveCompression

Ifweassumesomedegreeofinteractionbetweenthecompressorandthedecompressorthenwecanexploitthepreviousknowledgetheybothhaveofthesourcewhendatacompressionisusedfordataransmission.Thepriceweaccepttopay,insomecases,isalowprobabilityofcommunicationerrors.
Thesolutionofthecommunicationproblem,inthiscase,isaninteractiveprotocolthatallowsSenderandReceivertotakeadvantageoftheknowledgetheyhaveofthesourceandthatexploitstheinteractiontominimizethecommunicationcost.Inreallifethiscouldbeusedinsituationsinwhichfinitesizefilesaretransmittedoverabidirectionalcommunicationline,likeatelephoneline,internet,asatellitelinkoranyotherlinebetweentwosystemsthathavealreadyavailablealargenumberoffilesofthesametype.
Asanexampleconsideraninternetuserthathastofrequentlydownloadthesamekindoffile(anewsletter,animage,areport,etc.fromthesamesource,orasystemmanagerthathastodownloadrepetitivelyanupdatefileforaprogramorforanantivirus,oranftpmirroringsitethathastobeperiodicallybroughtuptodate,etc.Thecompressionalgorithmsinvolvedinthecommunicationmightbestaticordynamicdictionarymethodsor,inthecaseofimages,VectorQuantization.
4.1Interactivedatacompression

AnefficientcommunicationprotocolthatallowsaSenderandaReceivertocommunicateviadictionariesthatarebuiltindependentlyfromprevious(andmaybediscordantexamplesofcommunicationmessagesthateachofthetwosideshasavailableispresentedbyCarpentieriin[8].Thiscommunicationprotocolresultsinanimprovementincompressionpaidwithanegligibleoralmostnullpossibilityofcommunicationerrors.
43

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现
4.2Aninteractivecommunicationprotocol

ConsideraninformationsourceUthatemitswordsoveracertainalphabetandforwhichitispossibletopartitionthewordsemittedbythesourceintotwosets:oneDofcardinalitymthathasprobabilityP(D=1−αandanotherDcompwithprobabilityP(Dcomp=α,whereα<<1/2,andthewordswDhaveprobabilitypwsuchthat|(1−α/m−pw|<εforanappropriatelychosenε.ThesetDmightbeviewedastheideal―Dictionary‖forthesource.
Itispossibletorecognizethispropertyinmanyreallifesituations.Asanexampleconsiderasourcethatoutputsprograms.ForthissourceanidealsetDmightincludeallthekeywordsandreservedwordsoftheprogramminglanguageandthesetofthemostcommonidentifiers.
ConsidernowasituationinwhichSenderandReceiverhaveaccesstodifferentcorporaofthesamelanguage:forexampledifferentsetsofbooksand/orwebpagesand/ornewspapers,etc.Theycanusethesedifferentcorporatoindependentlyconstructtheirowndictionaries.
IftheSenderandtheReceiverhavebothknowledgeofthesourceintheformofalargenumberofmessagesthatarerecordedintwofilesoflengthapproximatelyn,ifnisbigenoughandnwisthenumberofoccurrencesofwinthefileandδisanopportunelychosennumberin[0,1/2],thenwehavethatforeachwordw,(P|nw/n−pw|<ε>(1−δ.
TheSenderandtheReceiverbuildup,respectively,dictionariesDSandDRofsizem.Theycanestimatetheprobabilityofeachwordwbycountingthenumberofitsappearancesinthefileoflengthn.NowconsiderthepossibilitythatawordisinDSbutnotinDR.ThiscouldhappenifthefrequencycountofwdonebytheSenderdoesnotreflecttheprobabilitypw,andthereforewbelongstoDSincorrectlyandwdoesnotbelongtoDRcorrectly,oriftheReceiverhasawrongestimateofpwandthereforewbelongstoDScorrectlybutincorrectlydoesnotbelongtoDRor,finally,ifbothSenderandReceiverhaveawrongestimateofpw.Therefore,ifnisbigenoughtheprobabilityofawordwinDSbutnotinDRis:P(wbelongstoDSbutdoesnotbelongtoDR<2δ−δ2.
44

北方民族大学学士学位论文Linux下文件压缩和解压缩分析研究与实现

5ConclusionsandFutureWork
TheinteractionbetweenaSenderandaReceiverthathavetocommunicateoverabidirectionallinecanimprovethetransmissionprocessifbothSenderandReceiversharepreviousknowledgeaboutthedatatheywanttocommunicate.
Bydoingthisinthefundamentalsourcecodingtheoremwecansubstituteentropywithconditionalentropyandthereforewehaveanewtheoreticallimitthatallowsforbettercompression.Inthispaperwehavereviewedrecentworkthatappliesinteractiveapproachestodatacompressionanddiscussedthispossibility.Futureworkwillfocusontheimprovementofthealgorithmspresentedandonawidertestingoftheapproachesdescribed.
Therearepointsofcontactsbetweenpartoftheworkdescribedinthispaperandthetransferlearningtechniquesstudiedinmachinelearninganddatamining.FutureworkmightalsoincludeawideranalysisofthisrelationshipbetweenthetechniquesthataredescribedinthispapertoimprovetheinteractionbetweentheSenderandtheReceiverandthetransferlearningtechniques.
Acknowledgements

IwouldliketothankJamesA.Storerforfruitfuldiscussionswehadoninteractivedatacompression,andmystudentsMarioImmobileMolaroandVincenzoViolaforcarryingoutsomeoftheexperimentalworkdescribedinthispaper.Thanksalsototheanonymousreviewersthat,withtheirconstructivecomments,havehelped
45

Linux下文件压缩和解压缩分析研究与实现

推荐内容

相关推荐