（微电子学与固体电子学专业论文）压缩算法在数据备份及恢复中的应用研究.pdf

摘要 数据备份是通过各种相应的手段对数据进行复制达到实现数据安全的目的， 它由储存设备、存储介质、储存方式三方面构成。数据备份技术的进步也由设备 的更新、介质材料的发展、压缩算法的改进共同决定。随着现代企业的运作日益 依赖于信息技术，信息数据的丢失和损坏将对企业造成难以估量的损失，数据恢 复努力的成败就是事关信息系统数据安全与否的最后生死线，其中数据备份技术 是解决数据损坏和丢失的唯一可行的有效途径。 研究国内外数据备份系统的应用现状，数据备份恢复类软件几乎很少考虑压 缩算法的优劣对备份系统效率的影响，为了提高数据存储和数据传输方面的效 率，降低数据的空间占有量，同时为了改善备份方式和提高系统的可用性，使其 具有自动、安全、可靠的特点，我们采用改进的字典压缩方法，将数据备份在单 次备份过程中的空间可压缩性与多次备份过程中数据的时空连续性相结合。对企 业信息数据的各种备份方式及采用本算法带来的优势进行了比较深入地探讨。 同时，针对现有压缩技术在各种特定的数据备份系统中的应用情况，本文主 要在以下几个方面进行了研究探索： 1 综述了各种压缩算法思想及其应用，详细介绍了h u f f m a n 编码算法和l z 系列算法。 2 针对特定的数据备份系统，采用三层模型架构方式对备份系统进行了重新 设计，将用户功能模块进行了详细功能区分及设定。 3 为特定数据备份系统定制设计新型的压缩算法，在单次压缩过程中引入连 续压缩思想带来的优化，以期实现在数据压缩率上的进一步提高。 经检测，不同类型、不同备份方式下采用该压缩算法进行的数据备份，体现 了该新压缩算法在特定条件下的优越性。 关键字：数据备份；数据恢复；数据压缩：压缩效率 a bs t r a c t d a t ab a c k u pi sd e v e l o p e dt oe n s u r ed a t as e c u r i t yb yc o p y i n gd a t av i a c o r r e s p o n d i n gw a y s i t sc o m p o s e do fs t o r a g ed e v i c e ，s t o r a g em e d i u ma n ds t o r a g e w a y t h ed e v e l o p m e n to f d a t ab a c k u pt e c h n o l o g yi sp r o m o t e db yr e n e w a lo fs t o r a g e d e v i c e ，d e v e l o p m e n to fs t o r a g em e d i u mm a t e r i a la n di m p r o v e m e n to fc o m p r e s s i o n a l g o r i t h m a st h em a n a g e m e n to fm o d e me n t e r p r i s ei si n c r e a s i n g l yd e p e n d e n to n i n f o r m a t i o nt e c h n o l o g y , a l le n t e r p r i s ew i l ls u f f e ru n p r e d i c t a b l el o s s e sa sar e s u l to ft h e l o s so rd a m a g eo fi n f o r m a t i o na n dd a t a t h es u c c e s so f d a t ar e c o v e r ye f f o r ti st h el a s t h o p et oe n s u r et h es e c u r i t yo fi n f o r m a t i o ns y s t e md a t aw h e ns u c hl o s s o rd a m a g e o c c t u 瞎t h eo n l yf e a s i b l ea n de f f i c i e n tw a yt od e a lw i t hd a t al o s sa n dd a m a g ei sd a t a b a c k u p i n v e s t i g a t i o no ft h ea p p l i c a t i o n s t a t u so fd a t ab a c k u ps y s t e mi nt h ew o r l d i n d i c a t e st h a tc u r r e n ts o f t w a r ea b o u td a t ab a c k u pa n dr e c o v e r yf o c u s e sl i t t l eo nt h e e f f e c t so fd a t ac o m p r e s s i o na l g o r i t h mo nb a c k u ps y s t e me f f i c i e n c y a ni m p r o v e d l z w c o m p r e s s i o na l g o r i t h mi sp r o p o s e di nt h i sd i s s e r t a t i o nt oi n c r e a s et h ee f f i c i e n c y o fd a t as t o r a g ea n dd a t at r a n s f e r , d e c r e a s es t o r a g es p a c e ，i m p r o v eb a c k u pw a ya n d e n h a n c et h ea p p l i c a t i o np o s s i b i l i t yo fas y s t e ms ot h a ti th a st h ef e a t u r eo fa u t o m a t i o n ， s e c u r i t ya n dr e l i a b i l i t y i tc o m b i n e st h es p a c ec o m p r e s s i b i l i t yi no n e t i m eb a c k u p p r o c e s sa n dt h ec o n t i n u i t yo ft i m ea n ds p a c eo fd a t ai nm u l t i t i m eb a c k u pp r o c e s s s o m et y p i c a lw a y st ob a c k u pt h ed a t aa n di n f o r m a t i o no fa ne n t e r p r i s ea n dt h e a d v a n t a g e so fa p p l y i n gt h i sa l g o r i t h mh a v ea l s ob e e ns t u d i e dd e t a i l e d l y c o n s i d e r i n gt h es t a t e o ft h ea r to fc o m p r e s s i o nt e c h n o l o g ya p p l i c a t i o ni n d i f f e r e n ts p e c i a ld a t ab a c k u ps y s t e m s ，t h i ss t u d yf o c u s e so nt h ep o i n t sa sb e l o w ： 1ar e v i e wo nv a r i o u sc o m p r e s s i o na l g o r i t h m sh a sb e e ns t u d i e dw i t he m p h a s i s o nh u f f m a na l g o r i t h ma n dl za l g o r i t h m s 2f o ras p e c i a ld a t ab a c k u ps y s t e m ，t h e3 - t i e ra r c h i t e c t u r em o d e li su s e dt o r e d e s i g nt h i ss y s t e m u s e rf u n c t i o nm o d u l e sa r ed e s i g n e db a s e do ni n d i v i d u a ls p e c i a l f u n c t i o n s 3an e wc o m p r e s s i o na l g o r i t h mh a sb e e nd e v e l o p e df o rs p e c i a ld a t ab a c k u p s y s t e m s t h ei d e a o fc o n t i n u o u sc o m p r e s s i o nh a sb e e ni n t r o d u c e di no n e - t i m e c o m p r e s s i o np r o c e s st of u r t h e ri m p r o v ec o m p r e s s i o ne f f i c i e n c y f o rd i f f e r e n tb a c k u pt y p e sa n d b a c k u pw a y s ，t h en e wc o m p r e s s i o na l g o r i t h mh a s b e e na p p l i e dt od e t e c ti t sp e r f o r m a n c e e x a m i n a t i o nr e s u l t ss h o wi t sd i s t i n g u i s h e d a d v a n t a g e si ns p e c i a lc a s e s k e yw o r d s ：d a t ab a c k u p ；d a t ar e c o v e r y ；d a t ac o m p r e s s i o n ；c o m p r e s s i o n e f f i c i e n c y 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 论文作者签名：支形 e tj ! i ： 汕7 年厂月弓o e l 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家有关部门 或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学校可以允许采用影 印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目的的前提下，学校可 以公开学位论文的部分或全部内容。( 保密论文在解密后遵守此规定) 作者签名： - 1 如4 霹 指导教师签名：窃r 黾、乞 日期： 日期： z 0 0 1 年 f r 月孑。日 第一章绪论 1 1 数据备份及恢复技术 1 1 1 数据备份 第一章绪论 1 1 1 1 数据备份的发展历史 从数据备份的发展过程而言，可以概括为一句话：备份的发展贯穿了计算机的发展 史，备份发展史是计算机发展史的缩n 3 。它经历了三个阶段： 计算机网络出现以前的单机备份。在此阶段是“单机处理，软盘交流 的个人行为， 想起来时才去备份，是典型的拍脑袋的举动，随机性很大，备份工作没有得到重视：备 份的形式通常就是对要备份的文件复制到硬盘的另一个位置或者软盘上，数据根本得不 到安全有效的保护。局域网环境的备份。这个时期由于网络的出现，数据共享显得日益 重要，数据备份得到了应有的重视，成为系统管理员或应用操作员日常工作的一部分： 备份的数据是网络中整个企业的数据，介质以磁带为主，不再是以前磁盘对磁盘的备份， 但依然是系统管理员的手工作业，通常是通过备份工具或是备份命令脚本进行人机交互 执行，效率不高，逐渐成为系统管理员工作领域中繁重的负担：还没有出现商业化备份 软件，研究性备份系统开始诞生。 基于i n t e m e t i n t r a n e t 的应用环境下的备份强1 。这期间的典型表现是企业的整个业务 流程依赖于i n t e m e t i n t r a n e t 网络环境；网络应用更加复杂化，计算模式由c s ，b s 到 p 2 p 复杂多变，数据种类增加，异种数据库、多种文件系统和操作平台呈现在异构的企 业计算机网络中；数据量剧增，存储空间增大；数据存储位置变得分散；出现n a s 和 s a n 存储机制，备份技术在结构上也得到了长足的发展，基本工作机制也逐步得到更新。 1 1 1 2 数据备份的概念 数据备份虽然出现了相当长的时间，到目前为止，仍然没有完全统一的定义，不同 的研究者给数据备份分别提出了不同的定义，在此简单列举有代表性的定义，分别从不 同的角度对数据备份概念进行了描述，有助于对数据备份的一些基本特征有一定的理 解。 在单机备份时期，数据备份就是指数据的复制1 ，进行数据拷贝，另外多存放一份 副本。随着计算机的发展，数据备份的内涵变得更得丰富起来。l y o n s 和a l a n 在1 9 9 6 年给出的定义为：数据备份就是仅仅对数据所作的副本存储，以便公司员工能够去灾难 湖北大学硕士学位论文 发生地点用曾经备份过的数据还原文件和应用软件，能够如什么也没发生过一样继续企 业活动：o r a c l e 公司给出的定义为：备份就是数据的一份复制，这份复制可以包括数据 库的多个重要部分如控制文件和数据文件等，备份是一种安全措施h 1 ，用来防止未预料 到的数据丢失和应用性错误，如果丢失了原来的数据，那么可以通过备份来重新构建 c u r t i sp r e s t o n 在描述数据备份时，强调一个全面灾难恢复计划中的备份和恢复同等重要 啼1 ，把数据备份的概念分解为若干个环节比如决定备份什么、何时进行备份及如何进行 备份来论述闭。从这些描述可知，数据备份的本质依然保持其原始含义，即数据的复制。 结合当今技术，可将数据备份定义描述为：为保护系统正常运行，不受各种数据灾难的 影响，对数据进行另外的复制，并存放在不同于原来的数据位置，以防发生数据丢失时 确保成功恢复数据，这一切所涉及的软件、硬件及管理过程的集合。这个定义从多个角 度来描述数据备份，体现了数据备份是个内涵丰富的概念1 。 一般认为，数据备份主要涉及三个技术领域：( 1 ) 备份硬件，包括系统、适配器、存 储技术及网络：( 2 ) 存储介质，通常指磁性磁带：( 3 ) 备份软件，包括数据备份、数据恢复 功能的软件。但在这三者之中，起主导作用的是备份软件，也可以完全这么说：数据备 份技术是存储领域中面向应用的数据保护的增值性软件技术。 1 1 1 3 数据备份的作用和分类 从数据备份的概念，可知数据备份对保护数据具有相当关键、相当重要的作用。但 其根本目的，是重新利用，这也就是说，备份工作的核心是恢复，一个无法恢复的备份， 对任何系统来说都是毫无意义的。所以说，数据备份的意义首先在于对数据以某种方式 加以额外的保留，以便在系统遭受破坏或其他特定情况下，能够成功重新加以利用，即 防止防范意外事件对系统破坏。 其次，数据备份是历史数据保存归档的最佳方式。换言之，即便系统正常工作，没 有任何数据丢失或破坏发生，数据备份仍然具有非常大的意义比如为我们进行历史数据 查询、统计和分析，以及重要信息的电子归档保存提供了可能性。 再次，数据备份是保护数据的重要方式之一。在当今技术环境下，它与服务器高可 用群集技术、远程容灾技术三者相互融合优势互补，共同承担着系统的数据保护任务。 在具有一定规模的系统中，备份技术、群集技术和容灾技术互相不可替代，并且稳定和 谐地协同工作，共同保证着系统的一常运转h 1 。数据备份在实现上有多种变化，由于各 种不同的原因，通常执行几类基本的备份操作，这主要依赖于数据的重要性、运行备份 的可使用时问和其他一些因素。由此，将数据备份分为以下四类基本的操作： 2 第一章绪论 1 、全量备份( f u l lb a c k u p ) ，指备份系统的全部内容。比如，磁盘卷当作备份对象， 则拷贝整个磁盘卷的内容。全量备份的主要好处是提供方便的全量恢复，但是资源浪费 严重，比如大量重复的数据被存储，运行期间会占用较长的时间。 2 、增量备份( i n c r e m e n t a lb a c k u p ) ，指备份自从上次备份操作以来新产生或更新的 数据。其最大优点是所要求的备份时间最短。当使用增量备份时，恢复过程需要使用全 量备份的数据，所有的增量备份都是在最近一次全量备份以后执行的。 3 、差量备份( d i f f e r e n t i a lb a c k u p ) ，是拷贝所有新产生的或更新的数据，这些数 据都是最近一次全量备份后产生的或更新的。差量备份与增量备份的区别是增量备份判 断数据更新标准是依据上一次备份检查点，而差量备份一定是依据全量备份检查点。如 没有全量备份，则就没有差量备份。差量备份的主要目的是限制完全恢复时使用的介质 数量。 4 、立即备份( i m m e d i a t e l yb a c k u p ) ，是指管理员人为地根据情形需要即时地备份 某些数据，表现为备份时间、数据对象有很大的随机性。在备份任务启动上，仅仅为人 工启动，而另外三类备份操作既可以人工操作备份，也可以由备份系统根据作业调度的 要求，按照定义的时间安排，自动地执行。 1 1 1 4 备份软件产品介绍 数据备份技术的发展，时刻推动着备份软件的进步，备份软件是软件技术领域发展 最快的软件产品之一。目前国外不少软硬件厂商都是备份软件的开发商和提供商。从本 地文件备份工具，如u n i x 平台上的d u m p 和r e s t o r e 、c p i o 、t a r 、d d 等，到标准数据库备 份工具，比如o r a c l e 的e b u 、r m a n 、s yb a s e 数据库的d u m p 、b c p ，i n f o r m i x 数据库的 o n t a p e 、o n b a r 等，到网络备份软件，比如马里兰大学开发的免费份网络备份软件 a m a n d a 。与此同时，为提供完整的数据保护机制解决方案，具有保护企业中从工作 组到企业级服务器的所有的数据的能力，解决操作系统平台不同、数据类型各异造成的 备份困难，出现了专业商业备份软件。比较有影响的有c a 公司的a r c s e r v e l t 系列和 b r i g h t s t o r 系列，v e r i t a s 公司的n e t b a c k u p 系列，l e g a t o 公司的n e t w o r k e r 数据存 储管理，i b m 公司的t i v o l i 存储管理器睛1 。这些商业产品体现了新的备份和恢复技术的 先进之处，比如自动备份、策略管理、支持异构平台、支持异种数据类型。国产的商业 化备份软件目前还没有，该领域近于空白状态。尽管在华中科技大学、清华大学、上海 交通大学等高校建立有存储实验室及s a n 实验室，但国内专注于网络备份软件的研发， 只有中山大学软件研究所的数据备份实验室，并已于2 0 0 3 年研发出v l b s 网络数据备 湖北大学硕士学位论文 份软件。 1 1 2 数据恢复 1 1 2 1 数据恢复概述 数据恢复是指由于各种原因导致数据损失时把保留在介质上的数据重新恢复的过 程田1 。从数据恢复的目的来看，它属于计算机安全，而恢复的手段又与计算机维护有着 紧密的联系，因此可以说数据恢复是从计算机安全与计算机维护发展起来的新领域。近 年来信息化建设高歌猛进，办公电子化已经是大势所趋、潮流所向，不仅仅是i t 企业， 传统企业以及政府机关也开始全方位启用信息化存储技术，随之而来的是数据恢复市场 迅速发展、空前繁荣。受市场鼓舞，数据恢复技术研究也不断深入，各种恢复方法层出 不穷。因此有必要对数据恢复技术进行分类，对数据恢复的原理和方法进行分析和讨论。 1 1 2 2 数据恢复技术分类 总观各种数据恢复技术可以归纳为三种主要的分类方法，按数据的存储介质来分， 按照数据的文件的格式来分和按照数据恢复的方法来分。 2 1 按数据的存储介质分类 数据恢复技术按按数据的存储介质来分类，则可以分为硬盘数据恢复技术、软 盘数据恢复技术、光盘数据恢复技术、u 盘( 闪存盘) 数据恢复技术、数码卡( 如：s d 、 c f 卡等) 数据恢复技术、r a i d ( 磁盘阵列) 数据恢复技术和网络存储设备( d a s 直接附 加存储、n a s 网络附加存储、s a n 存储区域网络) 数据恢复技术。 2 2 按数据的文件的格式分类 数据恢复技术按数据文件的格式来分类，可分为w i n d o w s 下的数据恢复技术、 u n i x l i n u x 系统的数据恢复技术、苹果m a co s 系统的数据恢复技术及数据库修复 技术。w i n d o w s 下只有f t a 与n t f s 两种文件格式，数据存储原理简单，数据恢复技 术成熟，恢复成功率高，m a co s 系统拥有量小，数据恢复量不大。 2 3 按数据恢复的方法分类 数据恢复技术按数据恢复的方法来分类，可分为软恢复法和物理恢复法。软恢 复法就是用数据恢复软件或手工编写恢复程序和更改某些设置达到恢复数据的方法。物 理恢复法是数据的存储介质硬件发生了物理损坏，必须更换或修复硬件才能达到恢复数 据的方法。 4 第一章绪论 1 1 2 3w i n d o w s 下的数据恢复 1 、硬盘的存储原理 硬盘是一种采用磁介质的数据存储设备，数据存储在密封于洁净的硬盘驱动器内腔 的若干个磁盘片上。这些盘片一般是在以铝或玻璃为主要成分的片基表面涂上磁性介质 所形成，在磁盘片的每一面上，以转动轴为轴心、以一定的磁密度为间隔的若干个同心 圆就被划分成磁道( t r a c k ) ，每个磁道又被划分为若干个扇区( s e c t o r ) ，数据就按扇区存 放在硬盘上。在每一面上都相应地有一个读写磁头( h e a d ) ，所以不同磁头的所有相同位 置的磁道就构成了所谓的柱面( c y l i n d e r ) 。传统的硬盘读写都是以柱面、磁头、扇区为寻 址方式的( c h s 寻址) 。硬盘在上电后保持高速旋转( 5 4 0 0 转m i n 以上) ，位于磁头臂上 的磁头悬浮在磁盘表面，可以通过步进电机在不同柱面之间移动，对不同的柱面进行读 写。 2 、f a t 文件系统 f a t 文件系统有f a t l 2 ，fa t l 6 和f a t 3 2 三种类型。f a t 文件系统一般由d o s 引导 扇区( d b r ) 、文件分配表区( f a t ) 、文件目录表区( f d t ) 和数据区组成。d b r 是操作 系统可以直接访问的第一个扇区，它包括一个引导程序和一个本分区参数记录块 ( b p b ) 。引导程序的主要任务是当m b r 将系统控制权交给它时，判断本分区根目录前 两个文件是不是操作系统的引导文件。如果是就将其读入内存，并把控制权交给该文件。 b p b 记录着本分区的起始扇区、结束扇区、文件存储格式、硬盘介质描述符、根目录大 小、f a t 个数、分配单元的大小等重要参数。 3 、n t f s 文件系统 n t f s 文件系统由b o o t 区、m f t 区、d a t a 区及m f t 部分记录的备份区所组成。 其b o o t 区功能与f a t 的引导区相似，在n t f s 中把一些由格式化形成的重要系统文 件称为元文件，而主文件表( m f t ) 是专门用来存储文件记录的一个元文件，在m f t 中 前1 6 个文件记录总是为系统最重要的元文件。系统通过m f t 来确定文件在磁盘上的位 置和属性。 4 、w i n d o w s 下数据恢复的原理与方法 w i n d o w s 下数据的恢复一般都是用手工、工具软件和人工分析相结合的软恢复，要 视具体情况灵活运用。 湖北大学硕士学位论文 1 2 数据压缩技术 1 2 1 数据压缩的概述 在计算机科学和信息论中，数据压缩或者源编码是按照特定的编码机制用比 未经编码少的数据位元( 或者其它信息相关的单位) 表示信息的过程n 们。例如， 如果我们将“c o m p r e s s i o n 编码为“c o m p ”那么这篇文章可以用较少的数据位表 示。一种流行的压缩实例是许多计算机都在使用的z i p 文件格式，它不仅仅提供 了压缩的功能，而且还作为归档工具( a r c h i v e r ) 使用，能够将许多文件存储到同 一个文件中。 对于任何形式的通信来说，只有当信息的发送方和接受方都能够理解编码机制的时 候压缩数据通信才能够工作。例如，只有当接受方知道这篇文章需要用英语字符解释的 时候这篇文章才有意义。同样，只有当接受方知道编码方法的时候他才能够理解压缩数 据。一些压缩算法利用了这个特性，在压缩过程中对数据进行加密，例如利用密码加密， 以保证只有得到授权的一方才能正确地得到数据。 数据压缩能够实现是因为多数现实世界的数据都有统计冗余。例如，字母“e ”在 英语中比字母“z 更加常用，字母“q 后面是“z 的可能性非常小。无损压缩算法 通常利用了统计冗余，这样就能更加简练地、但仍然是完整地表示发送方的数据。 如果允许一定程度的保真度损失，那么还可以实现进一步的压缩。例如，人们看图 画或者电视画面的时候可能并不会注意到一些细节并不完善。同样，两个音频录音采样 序列可能听起来一样，但实际上并不完全一样。有损压缩算法在带来微小差别的情况下 使用较少的位数表示图像、视频或者音频。 由于可以帮助减少如硬盘空间与连接带宽这样的昂贵资源的消耗n 1 1 ，所以压缩非常 重要，然而压缩需要消耗信息处理资源，这也可能是费用昂贵的。所以数据压缩机制的 设计需要在压缩能力、失真度、所需计算资源以及其它需要考虑的不同因素之间进行折 衷。 一些机制是可逆的，这样就可以恢复原始的数据，这种机制称为无损数据压缩；另 外一些机制为了实现更高的压缩率允许一定程度的数据损失，这种机制称为有损数据压 缩。 然而，经常有一些文件不能被无损数据压缩算法压缩，实际上对于不含可以辨别样 6 第一章绪论 式的数据任何压缩算法都不能压缩。试图压缩已经经过压缩的数据通常得到的结果实际 上是扩展数据，试图压缩经过加密的数据通常也会得到这种结果。 实际上，有损数据压缩也会最终达到不能工作的地步。我们来举一个极端的例子， 压缩算法每次去掉文件最后一个字节，那么经过这个算法不断的压缩直至文件变空，压 缩算法将不能继续工作。 1 2 2 数据压缩的意义 随着计算机技术的发展，数据压缩技术的研究受到人们越来越多的关注。数据的可 压缩性主要建立于数据的重复性，只有重复性的数据才有可能被压缩n 副。 在人类的文字世界里，一段音乐，一场电影，一篇文章等等，简单的说就是任何一 段有意义的数据都会包括相当一部分重复片断，甚者一而再、再而三的重复。比如说一 首流行歌曲，往往只有短短的几句，但是它不断的重复，致使整首歌所占据的时间很长。 在电脑中，符号的表现方法通常是存储体的最小单位。常见的方式是以一个字节 表示2 5 6 种符号。对于中文，一般是两个字节来表示上万个中文符号。而在一个程序中， 往往是由有限的指令集来组合出一个有实际意义的程序，因此重复的程序码也占了整个 程序相当的比例。 总之，以有限的符号来描述一段有意义的数据，必将产生许多重复，而减少重 复，以尽可能少的码来编排一段具有重复性的有效数据便是数据压缩的基本精神。 数据压缩最初是作为信息论研究中的一个重要课题，在信息论中被称为信源编码。 信息的传输可用图i - i 表示： 7 湖北大学硕士学位论文 图卜1 信息传输示意图 在上面的框图中，信源编码主要解决数据表示的有效性。通过对信源的压缩、扰乱、 加密等一系列处理，力求用最少的数据传递最大的信息量，使信号更易于传输。框图中 信道编码主要解决可靠性问题，即尽量使处理过的信号在传输过程中不出错或少出错， 即使有错也可纠正。因此，从信息论的角度看，信源编码的一个最主要目的，就是解决 数据的压缩问题。以尽可能少的数据表示信源所发出的信号，减少消息的冗余量，提高 消息的嫡，从而减少容纳给定消息集合的信号空间，减少数据所占据的存储空间和传输 时所需要的时间。例如，在通讯工程中为了能在存储设备容量、信道带宽、或通讯链路 容量等工作环境有限的情况下，通过采用相应的编码技术，可以大大减少数据所占的存 储空间，从而达到提高工作效率，或降低系统工作成本的目的。 1 2 3 数据压缩的发展 关于数据压缩的理论研究与实践，有些学者认为始于l8 世纪末w f s h e p p a n d s 所 做的“实数舍入为十进制数的研究。也有人认为1 9 世纪末研制的莫尔斯代码是数据 压缩的第一次尝试1 9 3 9 年，d u d e y 研制了声码器，他把声音频谱的能量划分为有限数 目的频带，并且在每个频带内传输相应的能级，因此能够达到较高的压缩。不过，比较 系统的研究始于4 0 年代初形成的信息论，早期信息论研究的主要内容之一就是己知消 息中各符号出现的频率，设法构造一种编码，使消息所占的空间尽可能少。尽管当时数 字计算机尚未出现，但所进行的研究与当今数字计算机所使用的压缩技术有着密切的联 系。许多算法的出现，如霍夫曼( h u f f m a n ) 编码等仍有很大的应用价值n 朝。 数据压缩的研究过程一直有两个发展方向：一个是许多数学家所致力于的建立信源 和数据压缩的数学模型，并从中找出衡量数据压缩质量的技术指标及最优压缩性能指标： 另一个则是众多的工程技术人员所进行的工作，他们的研究重点为建立一个能实现数据 压缩功能的系统，以服务于工程应用，或者对这些数据压缩系统进行分析或模拟，以确 8 第一章绪论 定它们的性能指标。但不论是理论研究还是工程实践，1 9 7 7 年以前，数据压缩作为信 息论研究中的一项内容，主要是有关信息嫡，数据压缩比和各种编码方法的研究，即按 某种方法对源数据流进行编码，使得经过编码的数据流比原数据流占用较少的空间。其 中基于符号频率统计的霍夫曼编码具有良好的压缩性能，一直占据重要的地位，不断有 基于霍夫曼编码的改进算法提出。 随着计算机技术的飞速发展，数据压缩作为解决海量信息存储和传输的支撑技术受 到人们的极大关注。1 9 7 7 年，两位以色列科学家j a c o bz i v 和a b r a h a ml e m p e l 发表了 论文”a u n i v e r s a la l g o r i t h mf o rs e q u e n t i a ld a t a c o m p r e s s i o n ”，提出了不同于以往的基于 字典的压缩算法l z 7 7 n 钔。1 9 7 8 年，又推出了改进算法l z 7 8 。他们的研究把无失真压 缩的研究推向了一个全新的阶段。目前，计算机文件常用的压缩工具如w i n z i p ，a r j 等 都是基于这种方法的 随着信号处理研究的不断的发展，数字图像信号、语音信号等都被大量的引入到有 关的领域中。由于图像信息占用较多的存储空间，而图像通信又是目前非话业务的主流， 因此数据压缩技术在图像通信中得到了最广泛的应用 1 5 o 在图像编码中，最早研究的是预测编码，曾作为经典理论而登载于各种专著，并得 到广泛的应用。近年来，随着神经网络理论的兴起，有人采用b p 网进行非线性预测的 尝试，并取得了较好的效果n 引。1 9 6 9 年，在美国举行首届“图形编码会议 ，表明图像 编码以独立的学科挤身于学术界。而变换编码在五年左右的时间内成为研究热点。变换 编码中的d c t 编码由于编码效果较好，运算复杂度适中等优点，已经发展成为目前国 际图像编码标准的核心算法。8 0 年代中后期，众多研究者相继提出了在多个分辨率下表 示图像的方案，主要的方法有：子代编码，金字塔编码，小波变换编码等。基于小波变换 的方法具有较高的压缩性能，己发展为j p e g2 0 0 0 的核心算法。在近年来的甚低码率 的编码研究中，有一种称之为模型基的编码方法颇引人注意，这种方法压缩比高，但适 用于场景比较简单的特定场合。在1 9 8 8 年左 右，有人提出了一种分形图像编码的压缩方案。这种方案思路新颖、压缩潜力大、 并具有解码分辨率无关性等优点，是一种很有潜力的编码方法。尽管用软件压缩方 法可以较好地实现数据压缩的目的，但由于压缩算法的运算量较大，需要很高的运算速 度和存储空间，这对现有系统来说是很大的负担。为了解决这个问题，人们在继续探索 数据压缩技术的同时，着手研制生产高性能的芯片和系统。一般在对时间要求不高的场 合采用软件压缩，而对运行速度有特殊要求的情况下，可使用硬件压缩。不过，目前硬 9 湖北大学硕士学位论文 件压缩的开销远远大于软件压缩的开销。 1 3 课题背景及主要研究内容 1 3 1 本文选题依据和意义 本论文的课题围绕数据备份及数据恢复的方法、策略，以及数据备份中的关键技术 数据压缩算法的研究。 信息化的高度发展同时也带来了更高的安全隐患和风险，在紧急情况下，数据能否 在尽短的时间内得到完整地恢复，已成为一个重要的课题。因此，不断优化备份与恢复 系统管理软件，实现网络数据备份与恢复的集中化、自动化和智能化，构筑网络运行安 全屏障，将显得尤为重要n 7 1 。 d a h u f f i n a n 于1 9 5 2 年第一次发表了他的论文“最小冗余度代码的构造方法( a m e t h o df o r t h ec o n s t r u c t i o no f m i n i m u m r e d u n d a n c yc o d e s ) 。从此，数据压缩开始在商业 程序中实现并被应用在许多技术领域。数据备份虽然出现了相当长的时间，到目前为止， 仍然没有完全统一的定义，不同的研究者给数据备份分别提出了不同的定义。在单机备 份时期，数据备份就是指数据的复制，进行数据拷贝，多存放一份副本。随着计算机的 发展，数据备份的内涵变得更得丰富起来。l y o n s 和a l a n 在1 9 9 6 年给出的定义为：数据 备份就是仅仅对数据所作的副本存储，以便公司员工能够去灾难发生地点用曾经备份过 的数据还原文件和应用软件，能够如什么也没发生过一样继续企业活动；o r a c l e 公司 给出的定义为：备份就是数据的一份复制，这份复制可以包括数据库的多个重要部分如 控制文件和数据文件等，备份是一种安全措施，用来防止未预料到的数据丢失和应用性 错误，如果丢失了原来的数据，那么可以通过备份来重新构建。从这些描述可知，数据 备份的本质依然保持其原始含义，即数据的复制。结合当今技术，可将数据备份定义描 述为：为保护系统正常运行，不受各种数据灾难的影响，对数据进行另外的复制，并存 放在不同于原来的数据位置，以防发生数据丢失时确保成功恢复数据，这一切所涉及的 软件、硬件及管理过程的集合。这个定义从多个角度来描述数据备份，体现了数据备份 是个内涵丰富的概念。而数据恢复主要指的是计算机硬盘数据被损坏后，采用相关技术 进行数据恢复的过程，而备份的目的也是为了在出现故障后能够以尽可能小的时间和代 价恢复系统。 数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度，达到增大 l o 第一章绪论 数据密度，最终使数据的存储空间减少的技术。我们常说的数据压缩技术就更加贴近信 息存储的本质，在信息数字化的过程中，数据压缩技术是起了非常大的作用。各种信息 的数字化的过程就是采样，量化和编码的过程，基于这些处理过程中产生的各种冗余， 如时间冗余，空间冗余，结构化冗余和知识冗余等，数字压缩技术可以有效的消除各种 冗余带来的容量的损失，将数据表现的方式优化。基本来说，压缩就是通过清除文件中 的冗余数据来减小文件的大小。数据压缩是整个数据存储的基础，是信息数字化的基本 处理方式，具有普遍的概念，也是数据备份过程中的核心和难点。 1 3 2 国内外研究现状和发展趋势 目前，国际上对电脑安全技术越来越重视，人们的安全意识越来越浓，体现在电脑 安全技术的应用从个别的特殊行业发展到各行各业；从对电脑设备的重视发展到对核心 数据的安全的重视，这已经是一个不可逆转的趋势。而企业和企业集团的电脑应用已经 非常广泛，而且深入到企业管理的各个环节，总经理查询系统、财务管理、人事管理、 进销存物流管理等子系统的数据都存放在服务器的数据库中，实时性要求非常高，所以， 除桌面数据备份外，服务器的备份、数据库的实时备份尤其必要和迫切。国外有许多软 件供应商提供数据备份管理软件，例如s y m a n t e c 公司的n e t b a c k u p 和b a c k u p e x e c 、e m c 2 公司的n e t w o r k e r 、b a c k b o n e 公司的n e t v a u l t 、c a 公司的b r i g h t s t o r 等，同时在桌面数 据备份技术上面国内也已经发展得比较成就，如g h o s t 、深度空间、北京和力记易：上 海数腾科技等。另外在服务器和数据库的备份方面，如数据库的热备份软件，国外已有 几种，国内还刚刚起步。在数据恢复方面，近几年来，灾难恢复技术有了突飞猛进的变 化，出现了很多技术先进的灾难恢复产品，同时已有产品的功能也更加完善，能够支持 和实现更多级别的灾难恢复。目前，国外主流灾难恢复技术基本可分为数据备份与恢复、 数据复制两大类。 1 3 3 本文主要研究内容 如上所述，由于现有压缩技术在数据备份系统中的应用还存在一些瓶颈问题，使得 在备份系统中压缩算法的改进有着很强的研究价值，本文主要针对特定的数据备份系 统，为其定制设计新型的压缩算法，以期实现在数据压缩率上的提高：并做大量的性能 测试，对数据压缩算法的可靠性和效率进行优化，以期实现高性能的数据压缩。 全文共分五章，各章内容安排如下： 湖北大学硕士学位论文 第一章绪论。介绍了论文的研究背景和意义，了解了目前国内外在数据备份及恢 复方面的研究现状，并提出了本论文的基本构架，同时说明了本论文研究课题的意义。 第二章压缩算法在数据备份中的应用。包括数据压缩的理论介绍，以及常用的数 压缩算法，分析了各自的优缺点，最后对数据压缩在数据备份系统中的应用进行了分析。 第三章备份系统的设计。对备份系统进行了理论分析，提出了详细设计方案，并 制定了相关备份策略，最后对系统的功能实现进行了演示。 第四章基于字典模型的自适应压缩算法在系统中的应用。对字典模型压缩算法的 思想进行了详细介绍，在基于对l z w 算法改进的思想上提出了一种新型压缩算法：动静 结合的实用改进压缩算法。 第五章模块实现与性能测试。主要将新型压缩算法应用到系统中后，备份系统中 数据压缩模块的实现，以及对于备份效率的测试。 第六章结束语，对本论文所做工作进行了总结，分析了取得的成果和存在的不足 并指明了今后的工作方向。 1 4 本章小结 现代企业的运作日益依赖于信息技术。信息已经成为公司拥有的最有价值的资产， 这些数据的丢失和损坏将对企业造成难以估量的损失。从现阶段来看，采用数据备份系 统备份关键数据是解决数据损坏和丢失的唯一可行的解决方案。研究国内外数据备份系 统的应用现状发现，如何克服现有技术中的不足，提供一种计算机网络数据恢复的方法， 使其能解决现有技术不能同时满足对恢复时间要求、存储空间要求、数据存储传输安全 性要求及正确恢复数据使之可用等诸多要求下进行数据恢复的技术问题，这样的自动、 安全、可靠的数据备份系统有着很高的理论价值和实用价值。 1 2 第二章压缩算法在数据备份中的应用 第二章压缩算法在数据备份中的应用 2 1 数据压缩理论 2 1 1 信息量的定义 通常一句话里所包含的数据“量 并不易以客观的方法来表示，因为我们很难用一 些单位( 如公里、公尺、磅、小时) 来描述一句话的数据量是多少n 引。 但主观上，我们能够很直观的了解到一句话对我们的重要性( 或者说是内含数据的 量) ，比如说，有人告诉你，“水是人类必须的。你可能不觉得它有什么重要意义，因 为你早就知道这一事实，所以这句话对你来说包含的数据量少。但如果有人突然告诉你， 明天会出游，你可能会兴奋地一跳而起，立马计划明天所需带的物品。这是因为你原先 并不知道这件事，或者说它所包含的信息量多。 上面所举的两个例子，一个是你早就知道的，一个是你原来不知道的，还有“水是 人类必须的 是一个已知的事实，且是必然的现象。即对于一个己知的事实和必然的现 象，它发生的概率为一。但是对于“明天会出游 这件事，一般而言发生的概率较低， 也不是必然现象。由这两个例子，我们可以观察到，一句话所包含的信息的多少与这句 话可能发生的概率与你是否己经知道有关，也就是说，越不可能发生的事情，越是使人 感到意外和惊奇的事情，所包含的信息量愈多。因此我们可以得到一个结论： 信息量是相加的，但相对应的信息概率是相乘的。 在信息论中用“熵”( e n t r o p y ) 来测量信息量的大小。对于单个事件( 如一个字符) 来 说，其熵定义为n 引： 日( f ) = 一1 0 9 2 ( r ) ( b it ) ( 2 1 ) 该式表示发生的概率为p i 的事件( 字符) i 所具有的信息量。度量信息量大小的单位 是“位 ( b i t