随着计算机技术和物联网技术的发展,全球数据的数量正在以惊人的速度大幅增长,而且种类也越来越多,这些数据涉及人类生活的各个方面,包括物流业、零售业、医疗卫生、机场安全、交通运输,环境检测等,通过挖掘和分析这些数据,人们可以发现隐藏的洞见,揭示自然的奥秘,为世界带来巨大的好处。所以,对海量数据的相关研究已经成为学术界和工业界关注的重点,甚至升级为国家级发展战略,如欧洲的“e-Europe”、美国的“智慧地球”,以及我国的“感知中国”等。然而,在对这些海量数据进行处理并产生价值之前,需要对其进行暂时或长久的存储,可以说数据存储是基础工序,也是保存原始数据、中间结果和最终结果的大本营。不幸的是,目前的存储容量增长并没有像数据生产那样取得进展,这导致海量数据中的绝大多数都可能被丢弃。虽然存储设备的设备的售价一直在下降,但其要与指数级增长的数据形成速度竞争,是非常困难的。因此,存储理论和技术的进步和创新是克服海量数据信息丢失的关键途径。海量数据通常来源于多个异构感知设备阵列,是对现实世界状态的实时刻画。由于设备存在重复采样,造成大量冗余数据,进一步增加了对存储空间和网络流量的需求。差分压缩作为一项无损数据压缩技术,能更加智能化地对具有公共性的文件实施更为高效的压缩。具体地说,差分压缩通过找出数据间的匹配片段,并把它编辑成一个数据较之另一数据的增量编码序列,实现对数据的压缩,节省存储数据的空间和网络传输带宽。本文围绕差分压缩的基础理论和优化开展研究,主要的研究工作以及创新性成果简述如下:1、目前,差分压缩的相关研究主要集中在算法开发和技术应用,其基础理论方面的研究相对缺失,本文首先从差分压缩的概念入手,定义了增量编码序列,从构建方式考虑,提出了参考文件构造模型和空文件构造模型。接着,分别从重构空间、时空关系和对象类型对差分压缩进行分类,并由此引出了差分压缩的十二种可研究类型。最后,给出了由COPY和ADD操作编辑的差分压缩的定义和增量编码序列的两种表达方式。差分压缩的基础理论研究对后续工作具有一定的指导意义。2、针对文件间公共性检测时由于共享片段遗漏导致检测效果不理想的问题,首先,定义了共享片段集合,并根据其位置将共享片段分成相离、包含和重叠关系。然后,提出用所有分离的共享片段总长度评估文件间的公共性,并设计了共享片段集合构建（Sharing Fragment Set,SFS）算法,通过寻找级联序列并将其分离化得到一个较优的共享片段集合。理论分析和实验仿真表明,SFS算法生成的共享片段集合包含所有相离的共享片段,其公共性测量结果比贪心字符串匹配（Greedy String Tiling,GST）算法和Greedy算法高出约10%和4%,为差分压缩的实施提供了先决条件。3、目前的差分压缩算法要么仅关注较长的匹配片段而忽略了较短的匹配片段,要么只追求时间和空间复杂度直接丢弃匹配片段,导致其在节省存储空间方面表现不佳。针对以上弊端,本文从COPY和ADD操作在计算机系统中的存储方式考虑,首先,定义了差分压缩的一个新的成本模型,提出用匹配片段总长度和匹配片段数量两个指标来评估增量编码序列。然后,从匹配片段总长度最大化和总数量最小化考虑,构建了复制片段总长度最大化（Maximal Total Length of Copied Fragments,MTLC）算法,通过识别每个偏移处的最长匹配片段、对重叠部分进行合理拆分和用COPY和ADD操作进行编辑,得到一个增量编码序列。理论分析和实验结果表明,相比于Greedy和Hsadelta算法生成的增量编码序列,MTLC算法生成的增量编码序列实现了匹配片段总长度最大化,同时包含的COPY操作最少。4、针对增量编码序列不够高效和紧实的缺陷,沿用之前定义的成本模型,首先,提出用所有COPY和ADD操作的累加成本来评估增量编码序列。其次,根据包含的ADD操作的数量和位置将子序列分成四种类型,并推导出对应的合并规则。然后,采用“分而治之”的思想,设计了增量编码序列成本最小化（Minimum Delta Encoding Cost,MDC）算法,通过对增量编码序列的合理分解与合并,完成了增量编码序列的修正。理论分析和实验结果表明,经过MDC算法修正的增量编码序列实现了累加成本的最小化,并且包含的操作数量也更少,在节省存储空间方面更具有优势。同时,这种增量序列修正方法是一种通用的方法,可以后缀在任何COPY/ADD类差分压缩算法之后,实现二次压缩,进一步提高计算机系统存储数据的效率。