一种基于滑动窗口的数据差异分析方法

1.一种基于滑动窗口的数据差异分析方法，应用于数据压缩领域，其特征在于包括以下步骤：
1)将原始数据划分成大小相等的数据子块；
2)计算原始数据中每个数据子块的hash值；
3)设置当前处理位置等于目标数据的开始位置；
4)如果当前处理位置到目标数据结束位置之间的数据大小小于原始数据的数据子块的大小，转10)；
5)从当前处理位置处取一个大小与原始数据的数据子块大小相等的数据块作为数据窗口；
6)根据数据窗口确定原始数据和目标数据的匹配范围；
7)如果没找到匹配范围，设置当前处理位置等于原来当前处理位置的下一个位置，转
4)；
8)将数据匹配情况写入差异数据；
9)设置当前处理位置等于匹配范围的下一个位置，转4)；
10)将剩余的数据匹配情况写入差异数据。
2.根据权利要求1所述的一种基于滑动窗口的数据差异分析方法，其特征在于步骤6)根据数据窗口确定原始数据和目标数据的匹配范围，其步骤如下：
2a).从原始数据的数据子块中找hash值与数据窗口的hash值相等的数据子块；
2b).如果hash函数不是强抗冲突性的，从hash值相等的数据子块中进一步找数据内容与数据窗口的数据内容相同的数据子块；
2c).对于每一个数据内容与数据窗口的数据内容相同的数据子块，都可以确定一个匹配范围；选择一个合适的匹配范围，返回该匹配范围，如果不存在合适的匹配范围，则没找到匹配范围，返回。
3.根据权利要求2所述的一种基于滑动窗口的数据差异分析方法，其特征在于步骤
2c)，对于每一个数据内容与数据窗口的数据内容相同的数据子块，都可以确定一个匹配范围，确定匹配范围可以有两种方法：
3a).直接把数据窗口的范围作为匹配范围；
3b).将数据窗口与数据子块周围对应位置内容相同并且还没有被记录到差异数据中的数据也纳入匹配范围。
4.根据权利要求2所述的一种基于滑动窗口的数据差异分析方法，其特征在于步骤
2c)选择一个合适的匹配范围，其中选择合适匹配范围的策略为：
4a).选择第一个匹配范围；或
4b).选择范围最大的一个匹配范围；或
4c).选择第一个范围不小于预定值的匹配范围。

一种基于滑动窗口的数据差异分析方法\n技术领域\n[0001] 本发明属于数据压缩领域，具体涉及到一种采用滑动窗口进行数据差异分析的方法。\n背景技术\n[0002] 在计算机系统中，通讯和存储过程中经常存在大量彼此之间只存在轻微差别的数据。比如，一个用户可能对一个文档进行多次修改，在修改过程中多次保存为不同的文件，[0003] 在这些不同的文件之间，彼此之间的差异非常之小，但是计算机系统必须为每个文件保存一个副本，这样就浪费了大量的存储空间。如果这样的文件在网络上面传输，网络上每次传输的都是差异非常小的数据，同样也浪费了网络的带宽。\n[0004] 如果我们能够将不同数据之间的差异部分分离出来，只对差异的部分进行处理，这将大幅度提高计算机的处理效率。例如，对于一个将文件存储在远程服务器上的系统，用户每次在客户端将文件修改以后，都需要把整个文件重新传输到服务器上，在这种处理方式中，需要在网络上面传输整个文件的数据；如果能够将修改前后的数据差异分析出来，则只需要将被修改的部分传输给服务器。通常情况下，差异部分只占文件很小的比例，因此将大量节约网络的带宽。\n[0005] 为了便于说明，下面将处理过程所涉及的源数据称为原始数据；将处理过程中需要被分析的数据称为目标数据；描述目标数据和原始数据之间差异的数据称为差异数据。\n[0006] 在传统的方法中，通常将原始数据和目标数据都分成为大小相等的数据块，然后在原始数据和目标数据中查找内容相同的数据块，这种方法分析的准确率较低。以数据块大小为2为例，原始数据为abcdef，目标数据为kabcde，分块的结果为：ab|cd|ef|(原始数据)，ka|bc|de(目标数据)；显然，采用这种分块方法，原始数据和目标数据中没有相同的数据块，而实际上，这两个数据中存在大量相同的数据(abcde)。\n发明内容\n[0007] 本发明的目的是提供一种技术，快速有效分析不同数据间的差异，从而达到降低数据冗余的效果，提高计算机的在存储和传输等方面的效率。\n[0008] 为了达到以上目标，本发明采用的技术方案是，一种基于滑动窗口的数据差异分析方法，应用于数据压缩领域，包括以下步骤：\n[0009] 1)将原始数据划分成大小相等的数据子块；\n[0010] 2)计算原始数据中每个数据子块的hash值；\n[0011] 3)设置当前处理位置等于目标数据的开始位置；\n[0012] 4)如果当前处理位置到目标数据结束位置之间的数据大小小于原始数据的数据子块的大小，转10)；\n[0013] 5)从当前处理位置处取一个大小与原始数据的数据子块大小相等的数据块作为数据窗口；\n[0014] 6)根据数据窗口确定原始数据和目标数据的匹配范围；\n[0015] 7)如果没找到匹配范围，设置当前处理位置等于原来当前处理位置的下一个位置，转4)；\n[0016] 8)将数据匹配情况写入差异数据；\n[0017] 9)设置当前处理位置等于匹配范围的下一个位置，转4)；\n[0018] 10)将剩余的数据匹配情况写入差异数据。\n[0019] 上述步骤6)根据数据窗口确定原始数据和目标数据的匹配范围，其详细步骤如下：\n[0020] 2a).从原始数据的数据子块中找hash值与数据窗口的hash值相等的数据子块；\n[0021] 2b).如果hash函数不是强抗冲突性的，从hash值相等的数据子块中进一步找数据内容与数据窗口的数据内容相同的数据子块；\n[0022] 2c).对于每一个数据内容与数据窗口的数据内容相同的数据子块，都可以确定一个匹配范围；选择一个合适的匹配范围，返回该匹配范围，如果不存在合适的匹配范围，则没找到匹配范围，返回。\n[0023] 上述步骤2c)，对于每一个数据内容与数据窗口的数据内容相同的数据子块，都可以确定一个匹配范围，确定匹配范围可以有两种方法：\n[0024] 3a).直接把数据窗口的范围作为匹配范围；\n[0025] 3b).将数据窗口与数据子块周围对应位置内容相同并且还没有被记录到差异数据中的数据也纳入匹配范围。\n[0026] 上述2c)选择一个合适的匹配范围，其特征在于如果存在多个匹配范围，只需要选择其中的一个即可，选择的策略可以有多种，但是并不影响本发明的本质，选择的策略包括但不仅限于：\n[0027] 4a).选择第一个匹配范围；\n[0028] 4b).选择范围最大的一个匹配范围；\n[0029] 4c).选择第一个范围不小于预定值的匹配范围。\n[0030] 本发明的效果在于采用本发明所介绍的方法，能够快速准确找到不同数据之间的差异和相同部分，从而达到降低数据冗余的效果。\n附图说明\n[0031] 图1是计算数据差异流程；\n[0032] 图2是差异数据的示例图；\n[0033] 图3是查找目标数据和原始数据的匹配范围；\n[0034] 图4是原始数据和目标数据示例；\n[0035] 图5是将原始数据分成大小为4的数据块；\n[0036] 图6是分别计算每个数据块的hash值；\n[0037] 图7是使用滑动窗口定位原始数据中的匹配块；\n[0038] 图8是匹配块位置处的匹配范围。\n具体实施方式\n[0039] 下面结合说明书附图，对本发明做进一步举例描述。\n[0040] 如图1所示，图1是计算数据差异流程图，说明了计算数据差异的步骤：\n[0041] 1)将原始数据划分成大小相等的数据子块；\n[0042] 2)并且分别计算原始数据中每个数据子块的hash值；\n[0043] 3)设置当前处理位置等于目标数据的开始位置；\n[0044] 4)如果剩余数据的大小小于原始数据的数据子块的大小，转10)；\n[0045] 5)从当前处理位置处取一个大小与原始数据的数据子块大小相等的数据块作为数据窗口；\n[0046] 6)根据数据窗口确定原始数据和目标数据的匹配范围。\n[0047] 7)如果没找到匹配范围，设置当前处理位置等于原来当前处理位置的下一个位置，转4)；\n[0048] 8)将数据匹配情况写入差异数据；\n[0049] 9)设置当前处理位置等于匹配范围的下一个位置，转4)；\n[0050] 10)将剩余数据匹配情况写入差异数据。\n[0051] 如图2所示，图2是将数据匹配情况写入差异数据的一个示例。将匹配数据写入差异数据的方法可以有多种，但是并不影响本发明的本质，这里仅举一种以示例。匹配情况分两种，一种是能够在原始数据中找到相同数据的部分，如示例图里面的加 数据部分另外一种情况是没有从原始数据里面找到匹配的部分，如示例图里面\n的k p和m l。在示例图中的记录方法是：以0xff表示后面的数据是没有找到匹配的数据，\n0xff后面紧接着是数据长度，数据长度后面是没有找到匹配数据的拷贝；以0x00表示后面的数据是找到匹配的部分，0x00后面紧接着是匹配的长度，再接下来是匹配数据在原始数据中的位置。详细说明如下：\n[0052] 2a).目标数据里面的kp是一个长度为2的数据，该数据没有在原始数据里面找到相同的数据。因此，这部分数据是没法从原始数据里面找到匹配的部分。对于这种数据，写入差异数据时采用以下方法：往差异数据里面写入0xff，接着写入数据长度2，紧接着写入数据本身kp，因此，差异数据里面的结果是0xff|2|kp|\n[0053] 2b).目标数据 是一个长度为5的数据，该数据可以在原始数据\n中找到相同数据(与原始数据的第二个位置开始长度为5的数据相同)，因此，这部分数据是能够在原始数据中找到相同数据的部分。对于这种数据，写入差异数据时采用以下方法：\n往差异数据里面写入0x00，紧接着写入数据长度5，紧接着写入原始数据中相同数据所在的位置1(第一个数据的位置为0，第二个数据的位置为1，依次类推)，因此，差异数据里面的结果是0x00|5|1|。\n[0054] 2c).目标数据里面的ml同2a)类似，写入的结果是：0xff|2|ml|[0055] 2d).综上，差异数据的结果如图2中所示。\n[0056] 如图3所示，图3是查找目标数据和原始数据的匹配范围的流程，进一步描述了图\n1说明中步骤6)根据数据窗口查找原始数据和目标数据的匹配范围的详细过程：\n[0057] 3a).从原始数据的数据子块中找hash值与数据窗口的hash值相等的数据子块；\n[0058] 3b).从hash值相等的数据子块中进一步找数据内容与数据窗口的数据内容相同的数据子块。本步骤只有当hash函数不是强抗冲突性的时候才需要。所谓的hash函数不是强抗冲突性是指：hash函数计算出来的hash值相同只表明数据内容可能相同，但是在实际应用中不能保证数据内容相同。因此，当hash函数不是强抗冲突性的时候，需要进一步检查数据内容是否相同。\n[0059] 3c).选择一个合适的匹配范围，返回该匹配范围。如果不存在合适的匹配范围，则没找到匹配范围，返回。\n[0060] 上述步骤中，如果找到了一个匹配范围，那么目标数据中该匹配范围与上一次找到匹配范围之间的数据，是无法在原始数据里面找到匹配的数据。\n[0061] 对于上述3c)中，选择一个合适的匹配范围，详细说明如下：对于目标数据中的数据窗口，原始数据中可能存在多个与该数据窗口的数据相同的数据子块，因此，可能存在多个匹配范围，从中选择一个作为结果即可。至于选择的策略，可以有多种，但是并不影响本发明的本质，举例如下：\n[0062] 4a).选择第一个匹配范围，即返回在计算过程中找到的第一个匹配范围；\n[0063] 4b).选择范围最大的一个匹配范围，即返回所有匹配范围中数据长度最大的范围；\n[0064] 4c).选择第一个范围不小于预定值的匹配范围。比如选择一个匹配范围中的数据不少于16个字符的匹配范围。\n[0065] 对于上述3c)中所述的选择一个合适的匹配范围，其详细说明如下：对于每一个数据内容与数据窗口的数据内容相同的数据子块，都可以确定一个匹配范围，其确定匹配范围的方法可以有：\n[0066] 5a).直接把数据窗口的范围作为匹配范围；\n[0067] 5b).将数据窗口与数据子块周围对应位置内容相同并且还没有被记录到差异数据中的数据也纳入匹配范围。\n[0068] 如图4所示，图4说明了用于示例的原始数据和目标数据的内容。\n[0069] 如图5所示，将原始数据分为blocksize大小(在示例说明中blocksize为4)的数据块。\n[0070] 如图6所示，分别计算原始数据中每个数据块的hash值。\n[0071] 如图7所示，使用滑动窗口定位目标数据和原始数据中的匹配数据块，其具体步骤如下：\n[0072] 7a).从目标数据的开始位置，取一个大小为4的数据块KKBC，计算该数据块的hash值，通过该hash值找与原始数据中相匹配的数据块，没有找到相同的数据块，匹配失败；\n[0073] 7b).移动目标数据中的数据窗口，取下一个数据块KBCD，计算该数据块的hash值，通过该hash值找与原始数据中相匹配的数据块，没有找到相同的数据块，匹配失败；\n[0074] 7c).移动目标数据中的数据窗口，取下一个数据块BCDE，计算该数据块的hash值，通过该hash值找与原始数据中相匹配的数据块，没有找到相同的数据块，匹配失败；\n[0075] 7d).移动目标数据中的数据窗口，取下一个数据块CDEF，计算该数据块的hash值，通过该hash值找与原始数据中相匹配的数据块，没有找到相同的数据块，匹配失败；\n[0076] 7e).移动目标数据中的数据窗口，取下一个数据块DEFG，计算该数据块的hash值，通过该hash值找与原始数据中相匹配的数据块，没有找到相同的数据块，匹配失败；\n[0077] 7f).移动目标数据中的数据窗口，取下一个数据块EFGH，计算该数据块的hash值，通过该hash值找与原始数据中相匹配的数据块，找到该数据块与原始数据中的数据块\n2匹配，匹配成功；\n[0078] 如图8所示，确定匹配块附近的匹配范围，其方法如下\n[0079] 8a).第一种方法，即上述5a)中所述的方法：直接把数据窗口的范围作为匹配范围；即原始数据中与目标数据的数据窗口相同的数据子块。图中加 的部分的数据即为采用该方法得到的匹配范围；\n[0080] 8b).第二种方法：即上述5b中所述的方法：将数据窗口与数据子块周围对应位置内容相同并且还没有被记录到差异数据中的数据也纳入匹配范围。图中加 的部分即为采用该方法得到的匹配范围。