一种利用数据差异算法生成多版本文件的方法

摘要

本申请公开了一种利用数据差异算法生成多版本文件的方法，包括：A、按照预先确定的数据块长度，对参照版本从头至尾依次计算每个数据块的数据摘要值；B、计算在各个偏移量下，与参照版本相同长度的差异版本的数据块的摘要值，将计算得到的差异版本的数据块的摘要值与参照版本的数据块的摘要值进行对比，根据对比结果提取出差异版本中的差异数据，并生成用于存储所述差异数据的差异记录文件。本申请方案可以有效节约多版本文件的存储空间。

主权项

一种利用数据差异算法生成多版本文件的方法，其特征在于，包括：A、按照预先确定的数据块长度，对参照版本从头至尾依次计算每个数据块的数据摘要值；包括：对每一个数据块，计算一个长度为N1的快速摘要，以及计算一个长度为N2的慢速摘要，其中N1<N2；快速摘要值相同是数据块相同的必要非充分条件，慢速摘要值相同是数据块相同的充分必要条件；B、计算在各个偏移量下，与参照版本相同长度的差异版本的数据块的摘要值，将计算得到的差异版本的数据块的摘要值与参照版本的数据块的摘要值进行对比，根据对比结果提取出差异版本中的差异数据，并生成用于存储所述差异数据的差异记录文件，所述参照版本和差异版本作为多版本文件中的不同版本，所述差异记录文件用于作为多版本文件中，从基准版本得到差异版本的依据；步骤B具体包括：B1、生成用于存储参照版本的数据块摘要对的哈希数组H，创建一个空白的差异记录文件，然后向这个文件写入16字节的空内容；然后创建一个链表结构K，用于记录差异数据块的比较结果；B2、将差异版本的文件偏移设置为0；B3、判断从差异版本当前偏移处开始向后的数据长度是否小于L，若是，执行步骤B4，否则执行步骤B5；B4、将从差异版本当前偏移处开始向后的数据记录到差异记录文件中，提取差异记录文件当前大小以及链表元素的个数后，将链表K写入到差异记录文件的末尾；然后将文件大小及元素个数写入到差异记录文件中开头的预留字节中，并结束步骤B；B5、从差异版本当前偏移处开始向后读取长度L的数据块，计算该数据块的快速摘要；B6、判断是否在哈希数组H中查找与之相同的快速摘要，若找到，执行步骤B8，否则执行步骤B7；B7、将差异版本的偏移向后移动一个字节，并返回步骤B3；B8、计算该数据块的慢速摘要，在已经找到快速摘要的哈希数组中的链表中查找是否有相同的慢速摘要，如果找到，执行步骤B9，否则，执行步骤B7；B9、将该数据块之前已经滑过的数据作为差异数据写入到差异记录文件中，并且生成一个数据块记录项，其类型为“不同”，所述数据块记录项记录这一差异数据在差异记录文件中的偏移，以及数据块的长度，并将记录项插入到链表K的末尾；B10、将这一个相同数据块的信息，生成一个数据块记录项，其类型为“相同”，所述数据块记录项记录本块数据在参照版本中的偏移以及块长度L，然后将该数据块记录项插入到链表K的末尾；B11、将差异版本的偏移向后移动L，然后转至步骤B3。