CN1997011B - 数据分割方法和数据分割装置 - Google Patents

Abstract

本发明提供了一种数据分割方法，包括：用一个预设长度的窗口从待编码的数据流中选取部分待编码的数据；从窗口内的数据中随机选取一个数据段，或者从待编码的数据流中顺序选取部分待编码的数据作为一个数据段，所述数据段大于第一预定长度；以及，用所述数据段到第一数据库中匹配相应的记录，如果匹配成功，确定数据分割点，将所述窗口顺序向后移动相应的长度；否则，将所述窗口顺序向后移动第二预定长度。可以避免数据段找到以前进行的大量重复的比较运算，尤其是采用窗口的动态调整移动步长，更能够快速在数据库中定位所述数据段以及提高数据流的分割速度，本发明还提供了一种数据分割装置。

Description

数据分割方法和数据分割装置

技术领域

本发明涉及一种将数据流中的数据分割为数据段的数据分割方法和数据分割装置。

背景技术

在数据传输过程中，通常的手段是对要传输的数据进行编码压缩，编码压缩的实质，是减少数据流中重复数据的传输，在数据接收的端点，再对减少传输的重复的数据进行必要的重复恢复以复原数据流。例如，如果要传输的数据串为011000110101011，其中，可以划分出需要重复传输的数据子串“011”，显然，如果“011”只传输一次，就可以减少实际传输的数据量，实现数据的压缩。

要找到重复传输的数据，需要解决如下的问题：首先要知道哪些数据段是重复的，其次要知道预传输的数据流中哪些数据段是重复的，这样才能实现重复数据的替代传输，即将位数较长的重复数据段用位数较少的替代符号传输，从而大大减少实际需要传输的数据量。例如，专利号为US20060061495的美国专利公开了一种用于处理输入数据的设备，在设备中输入的数据被分割成多数的数据段，这个设备能够判断数据流中的一个或多个数据段是否是可以被引用的数据段；然后，对于每一个或多个被引用的数据段，逻辑上被设定为用一个引用标签来替代。更进一步，对于每一个未出现在固定数据段存储器中的被引用的数据段，可以为其分配一个引用标签，并且将所述引用标签和所述数据段绑定后存储入一个数据库。

按照上述专利的说法，只要能够分割出在数据流中重复概率较大的数据段，就可以通过与其绑定的标签代替数据段进行数据传输，从而实现数据的编码压缩。这里所说的数据重复有两种含义，一种是历史性重复，即与存储在数据库中的数据段的重复，只有这种重复可以通过引用标签的替代作用实现数据的压缩；另一种是临时性重复，即本次传输的数据流中的重复次数较多或重复概率较大的数据段。无论什么样的重复数据，按照上述专利的指示，要么通过数据训练预先存储在数据库中，要么在即时的数据流传输过程中被发现并取出，然后为其分配引用标签并绑定后存入数据库。问题的关键在于，如何确定一个数据段是可以被引用的数据段，以及，如何进行数据的分割能够才能发便地找到这样的数据段。

按照本申请人的名称为，可以按照数据应用领域的数据特性设置包括满足所述数据特性要求的数据段及引用标签，所述引用标签与所述数据段绑定后存入数据库。对于某个特定的数据应用领域，例美国如金融领域，往往会有明显的数据特性，指示重复概率较大的数据或数据段，如通常的词语、短句和表格数据等等。可以按照US20060061495号专利所说的方式或按照“数据传输方法”的专利申请的指示通过数据训练获得这些重复概率较大的数据。剩下的问题是，如何进行有效的数据分割才能在一个数据流中找到这些可能的重复数据？一种常用的方法是，首先将数据流按照预先设置的窗口进行分割，然后按照数据库的具体记录中存储的数据段的指示，到窗口中匹配所述数据段，如果成功，则认为找到了可以用引用标签代替的数据段。由于这种方法需要遍历数据库中的所有数据段，用每一个数据段到窗口中进行匹配操作，而匹配到的数据段也可能有多个，还要在一组数据段中通过判决找到最佳的数据段，因此该方法的计算量大而效率低下。一个改进的方法是，在窗口中首先从数据的起点起选择一个最小的数据段，然后顺序增加数据段的长度，计算每一个新长度数据串的散列值，然后利用该散列值到数据库中匹配相应的记录，如果匹配成功，则认为找到了可以用引用标签代替的数据段。由于这种方法固定了数据的起点，每找到一个数据段，都要到数据库中进行多次匹配猜可能完成，所述次数与数据段的长度相等。因此这种方法仍然要消耗大量的计算资源，导致编码效率较低。

发明方案

本发明要解决的技术问题在于，提供一种效率高、易于找到最佳重复数据段的数据分割方法和装置。

本发明提供的数据分割方法，包括：

用一个预设长度的窗口从待编码的数据流中选取部分待编码的数据；

从窗口内的数据中随机选取一个数据段；

用所述数据段到第一数据库中匹配相应的记录，如果匹配成功，确定数据分割点，将所述窗口顺序向后移动相应的长度；否则，将所述窗口顺序向后移动第二预定长度；

所述相应的长度为等于数据段的长度或大于数据段的长度。

其中，从窗口内的数据中随机选取大于第一预定长度的数据段。

其中，用一个预设长度的窗口从待编码的数据流的起点连续选取待编码的数据。

按照下述步骤随机选取大于第一预定长度的数据段：

从窗口内的当前数据起点开始连续扫描数据，记录扫描到的特定字符的个数；

如果所述特定字符的个数值大于所述第一预定长度值，将扫描到的连续字符构成的字符串作为分割的数据段。

也可以按照下述步骤随机选取大于第一预定长度的数据段：

从窗口内的数据起点开始连续扫描数据，查找所述窗口后部紧邻所述窗口的连续的最长字符串并记录所述字符串；

如果所述字符串的字符个数值大于所述第一预定长度值，将扫描到的字符串作为分割的数据段。

所述方法还包括，计算所述数据段的散列值，以及，用所述散列值到数据库中匹配相应的记录。

所述第二预定长度等于1或大于1。

所述方法还包括，当用所述散列值到数据库中匹配相应的记录没有成功时，判断所述数据段是否为高概率重复字符串，如果是，为该字符串分配引用标签，计算所述字符串的散列值，将所述散列值与所述引用标签、字符串绑定后存储入所述数据库。

当用所述数据段到数据库中匹配相应的记录没有成功，调整窗口内的当前数据起点后继续随机选取数据段，直到所述窗口的调整不满足设定的条件时，将所述窗口顺序向后移动第二预定长度。

所述方法还包括，设置一个第二数据库作为备用数据库，用于存储重复概率较低的数据段和其重复次数，以及，将第二数据库中重复次数大于指定阈值的数据段存储入所述第一数据库。

所述方法还包括，将第一数据库中被引用次数小于指定阈值的数据段移动到所述第二数据库。

本发明提供的数据分割装置，包括存储数据段和与其绑定的引用标签的第一数据库，以及一个用于存储数据分割结果的第二数据库，还包括：

数据段选择单元，用一个预设长度的窗口从待编码的数据流中选取部分待编码的数据，以及，从窗口内的数据中随机选取一个数据段；

数据段匹配单元，用所述数据段选择单元提供的数据段到第一数据库中匹配相应的记录；

窗口移动单元，用于将所述窗口顺序向后移动相应的长度，或者，将所述窗口顺序向后移动第二预定长度；所述相应的长度为等于数据段的长度或大于数据段的长度。

其中，所述数据段选择单元从窗口内的当前数据起点开始连续扫描数据，记录扫描到的特定字符的个数；

如果所述特定字符的个数值大于第一预定长度值，将扫描到的连续字符构成的字符串作为分割的数据段。

或者，所述数据段选择单元从窗口内的数据起点开始连续扫描数据，查找所述窗口后部紧邻所述窗口的连续的最长字符串并记录所述字符串；

如果所述字符串的字符个数值大于第一预定长度值，将扫描到的字符串作为分割的数据段。

更进一步，所述数据段匹配单元计算所述数据段的散列值，以及，用所述散列值到数据库中匹配相应的记录。

所述装置还包括，

第一处理单元，用于当用所述散列值到数据库中匹配相应的记录没有成功时，判断所述数据段是否为高概率重复字符串，如果是，为该字符串分配引用标签，计算所述字符串的散列值，将所述散列值与所述引用标签、字符串绑定后存储入所述数据库。

所述装置还包括，

第二数据库，用于存储重复概率较低的数据段和其重复次数。

所述装置还包括，

第二处理单元，用于将第二数据库中重复次数大于指定阈值的数据段存储入所述第一数据库，以及，将第一数据库中被引用次数小于指定阈值的数据段移动到所述第二数据库。

本发明通过在预设长度的窗口中随机选取一个数据段，以及用所述数据段到数据库中匹配相应记录的方式，可以避免数据段找到以前进行的大量重复的比较运算，尤其是，采用散列值查找的方式，以及窗口的动态调整移动步长，更能够快速在数据库中定位所述数据段以及提高数据流的分割速度，与现有的方法相比，具有更高的数据分割效率。

附图说明

图1是本发明所述方法的第一个实施例流程图；

图2是图1所述实施例采用的数据库示例图；

图3是本发明所述方法的第二个实施例流程图；

图4是本发明所述方法的第三个实施例流程图；

图5本发明所述实施例采用的随机选取数据段的实施例流程图；

图6(1)是本发明实施例采用的窗口初始状态示意图；

图6(2)是本发明实施例采用的窗口移动后的状态示意图；

图7是本发明所述装置的第一个实施例框图；

图8是本发明所述装置的第二个实施例框图。

具体实施方式

图1是本发明所述方法的第一个实施例流程图。图1所示实施例应用于具有引用标签和与之绑定的数据段的多个记录，同时，为了方便数据库内容的检索，所述数据库还有散列值或其它有利于检索数据库的字段及其对应的数据，这些数据也与引用标签和数据段绑定在一起。所述数据库的例子参考图2。

按照图1的指示，由于数据流是一个已经取出的长度确定且长度较大的字符串，或者是一个正在动态输入的数据流，使得直接处理数据流变得比较困难，而实际中长度确定但长度值较小的数据段更容易处理。因此，首先要预先设定一个用于从数据流中选择部分数据的窗口，所述窗口的长度要满足一定的要求，例如要大于需要选择的最大长度的数据段，且要有一定的数据冗余，因此，窗口的长度要预先确定。例如，如果图2所述数据库的数据内容的字段长度为8K字节，则窗口的长度要大于8K字节，例如16K字节。

其次，在步骤11用一个所述预设长度的窗口从待编码的数据流中选取部分数据。最好是用一个所述预设长度的窗口从待编码的数据流的当前起点，连续选取部分待编码的数据。对于第一次选择数据，所述当前起点就是数据流的起点。而在本发明另外的实施例中，只要求顺序、连续选择，对起点没有要求，可以向后跨越一个偏移量。

所述窗口内的数据确定后，就可以从窗口内的数据中随机选取一个数据段(步骤12)。所述随机选取，是指从窗口内的数据中尽可能选择一个数据段能够与数据库中的数据段匹配，这个数据段如果存在，则该数据段在窗口中的位置就难以是固定的，具有随机的成分，这导致数据段的选择是随机的。

如果找到了所述数据段，就可以到数据库中匹配，看是否为可以用引用标签代替的高重复概率数据段。然而如果按照通常的顺序查找的匹配方式，需要数据段字符串直接到数据库中与每一个记录中的数据段字符串精确比较，消耗的计算资源较多，速度慢，因此需要选择一种快速的匹配方式，例如，折半查找的匹配方式。在本实施例中，利用数据库中的散列值字段，实现快速匹配。因此，要在步骤13计算所述所述数据段的散列值，用所述散列值到数据库中进行记录的匹配。

接着在步骤14判断所述匹配是否成功，如果没有匹配成功，可以认为所述数据段不是高重复概率数据段，应当移动窗口继续查找，因此在步骤16将所述窗口向数据流的后部方向移动一个指定的偏移量后返回步骤12继续选择数据段。所述偏移量也是一个预定的长度，最好等于1，使所述窗口向后移动1个数据单位，例如1个字节，这样就会实现数据流的不间断匹配查找。在本发明的另外实施例中，为了提高数据流的处理速度，使所述窗口向后移动的偏移举例大于1个数据单位，例如使所述窗口向后移动5个字节。

如果在步骤14匹配成功，说明所述数据段就是高重复概率数据段，可以在数据传输时用引用标签代替。因此要在步骤15以所述数据段在窗口中的位置为依据确定数据分割点，还可以进一步为后续的数据传输做一些必要的准备，例如，将所述分割点用另外一个数据表存储起来，或者用数据库中的相应的引用标签标识所述数据段，然后直接存储所述标签，从而形成一个按顺序存储标签和剩余数据的数据表，所述标签也可能是更高级的标签。然后在步骤17将所述窗口顺序向后移动相应的长度，所述相应的长度为数据段的长度或大于数据段的长度。所述窗口移动的长度可以灵活决定，窗口向后移动的长度可以大于或等于数据段的长度，但小于可能引起数据段的重复从而导致数据传输的混乱或失败。最好所述相应的长度等于数据段的长度，这样作是为了避免遗漏作为判断起点的字符。但是，当一个字符串被分割出来，后续的字符构成的字符串重复的概率可能较小，此时，所述窗口后移的长度大一些，不但不会影响高概率字符串的查找，还会提高查找的速度。

经过步骤16或步骤17后，都要在步骤18判断整个数据流的分割是否完毕，如果完毕，在步骤19结束数据分割操作，否则都要返回到步骤12继续数据段的查找和分割。步骤18可以有多种方式实现，例如，当所述窗口向后移动后超出了数据流的范围就可以确定数据流分割完毕。

在一个极限的例子中，所述引用标签和散列值用一个值表示。

需要说明的是，在图1所示的例子中，可能有多个记录具有相同的散列值，如果选择到多个具有相同散列值的数据段，还要精确匹配才能确定准确的记录。

在本发明的另一个实施例中，对从窗口内的数据中随机选取的数据段的长度是有一定要求的，要求其大于一个预定的长度值。因此该实施例在步骤12、13之间增加一个判断步骤，判断所述随机选取的数据段的长度是否大于预定的长度，如果大于，转步骤13进行后续操作，否则转到步骤16此向后移动所述窗口后重新查找新的符合条件的数据段。

主要考虑的数据分割的效率而要求一个数据段大于一个指定值。一个数据段的压缩效率可以用引用标签的长度除以被替代的数据段的长度得到的比值标识，该值越小，压缩率越大。当选取的数据段长度太短时，会增大该比值，从而降低数据段的压缩率，因此，需要设置一个具体的长度值，即第一预定长度，用于控制数据段的压缩效率。这种思想在设置图2所示数据库的数据内容字段时也同样有所应用。例如，考虑了数据的压缩率，数据库中往往尽可能存储较长位数的重复数据。

图3是本发明所述方法的第二个实施例流程图。图3所述实施例与图1所述实施例的区别是在步骤14和步骤16之间增加了判断步骤1A和步骤1B。其中，在经过步骤13判断数据段匹配不成功时，可能不能说明该数据段的重复概率。数据段重复概率的大小，是由客观的标准提供判断依据的，如果一个重复概率较高的字符串没有被预先存储入所述数据库，找到并将其补充存储入所述数据库，能够提高系统数据压缩的效率。判断一个字符串是否具有较高的重复概率有两个标准，一是符合某种来自实际的判断准则，例如一种统计概率，另一个是在当前传输的数据流中出现的高重复概率的数据；尤其当在数据流中出现的最长的重复字符串且符合所述判断准则，更具有较高的重复概率。

在经过步骤13判断数据段匹配不成功时，在步骤1A判断所述数据段中的字符串是否为高概率重复字符串，如果是，在步骤1B为该字符串分配引用标签，计算所述字符串的散列值，将所述散列值与所述引用标签、字符串绑定后存储入所述数据库；否则直接进入步骤16。

步骤1A、1B使本实施例具有了学习的功能，还需要设置在步骤13和步骤1A之间的步骤S1(图中未绘出)，更有利于数据的分割。在本实施例中，对于每一个从窗口中随机找到的字符串，首先将其存储在内存中，并为其设置一个记录重复次数的计数器，内存中存储有许多这样的数据段和对应的计数器。当在经过步骤13判断数据段匹配不成功时，首先在内存中与这些数据段进行匹配，如果匹配成功，未相应的数据段的计数器增加1个单位，然后再在步骤1A通过所述计数器的值对该数据段是否高重复概率进行判断；如果匹配不成功，仅在内存中存储这些数据段，并为其分配计数器，所述计数器可以用存储单元或寄存器实现。

更具体地说，可以在一个内存的数据表中的一个数据域中存储上述数据段，在另一个数据域中存储重复次数的计数值，每一个记录中的数据段都有一个重复的次数与其对应，比如一个数据段的字符串“abccdecc”(实际中字符串会长很多)在学习的过程中重复了30次(假设的阈值)，那么就认为它是一个重复概率较高的热数据，用一个指纹函数F(X)为其生成标签，存入数据库中，作为匹配时的标本如果abccdecc的重复次数少于30次则认为它是冷数据不生成标签，仍然存储在原来的数据表中(也可以称为备用数据表或备用数据库)，当冷数据达到一定的条件，也就是说单位时间内达到阈值成为热数据才会为其生成标签写入热数据库。在实际匹配时，可以将热数据组成的数据库加载到内存使用，而冷数据是放在硬盘上备用(在内存资源不足时使用)。之所以这样处理是为了在使用时达到比较好的性能，把常用的数据放在内存中，不常用的放在硬盘上，可以最大限度地利用内存进行数据段的匹配操作，因此能够提高系统整体的性能。但是数据的热和冷是不断变化的，通过自动调整热数据库(存储引用标签、数据段和其散列值大数据库，例如图2)中的数据，使得热数据库中的数据利用率更高。将备用数据库中重复次数大于指定阈值的数据段存储入所述热数据库。以及，将热数据库中被引用次数小于指定阈值的数据段移动到所述第二数据库(包括删除热数据库中的相应数据段的记录的操作)。由于这种实现及其简单，在此不再赘述。

需要说明，在本发明的另一个实施例中，步骤S1可以在步骤1A、1B的后面，步骤16的前面。

图4是本发明所述方法的第三个实施例流程图。图4所述实施例与图1所述实施例的区别是在步骤14和步骤16之间增加了判断步骤2A和步骤2B。

其中，在经过步骤13判断数据段匹配不成功时，可能不能说明在所述窗口中不存在重复概率较高的数据段，可能由于起点字符的选择不当而导致。因此，在步骤2A调整窗口内的当前数据起点。实际可以通过当前数据的起点从原起点向后移动一个或若干个字符实现。然后在步骤2B判断所述窗口的调整是否满足设定的条件，如果满足条件，转步骤12继续数据段的随机选择操作。所述条件以从窗口当前字符到窗口结束的字符数量大于一定的长度，以及不影响数据段的查找为标准，例如，如果图2所述数据库的数据内容的字段长度为8K字节，则窗口内从当前字符到窗口结束的字符数量要大于8K字节，例如10K字节。如果不满足条件，转步骤16完成窗口后移动预定长度的调整操作。

对步骤2A调整窗口内的当前数据起点的理解可以参考图6(1)和图6(2)。图6(1)所示，一个数据流被串口分为三个部分，分别为部分61、62、63，在窗口内，选择的数据段的起点为字符64，终点为字符65。图6(2)示例当前数据起点向后移动了一个字符，即选择的数据段的起点字符64，终点字符65都向后移动了一个字符。

图5本发明所述实施例采用的随机选取数据段的实施例流程图。按照图5，首先在步骤51从窗口内的当前数据起点开始连续扫描数据，并记录扫描到的特定字符的个数；对于一个新窗口，即刚移动完毕的窗口，当前起点为第一个字符的位置；所述特定字符，是为了随机选择一个数据段，而在所传送的数据流中随机选择的一个字符，例如，在一个由ASCII码组成的数据流中选择字符A作为特定的字符。记录扫描到的特定字符的个数可以随机选择到一个数据段。如前所述，这个随机选择的数据段的长度要大于一个预定的长度，这首先要求扫描到的特定字符的个数要大于和等于一个设定的长度，才能保证随机选择的数据段的长度满足要求。因此在步骤52，判断所述特定字符的个数值是否大于或等于所述一个预定的长度阈值，如果大于或等于，在所述窗口中扫描到的连续字符构成的字符串就可以在步骤53作为分割得到的数据段；否则要回到步骤51继续特定字符的扫描。

在本发明的另一个实施例中，步骤51采用下述步骤实现：从窗口内的数据起点开始连续扫描数据，查找所述窗口后部紧邻所述窗口的连续的最长字符串并记录所述字符串，在步骤52，判断所述预定字符串长度是否大于或等于所述一个预定的长度阈值，如果大于或等于，在所述窗口中扫描到的字符串就可以在步骤53作为分割得到的数据段。

步骤51的具体实现可以参考下述描述。在本实施例中，需要借助一个预读缓冲器，对应的窗口为动态窗口，是个历史缓冲器。一个动态窗口的数据范围可以根据实际需要调整。先用窗口从数据流的开始取出一串数据，预读缓冲器是与动态窗口相对应的，它被用来存放数据流的前n个字节，预读缓冲器的大小n也可以根据需要动态调整，例如256字节。若能后用窗口后面的n个字节填充预读缓存器，再在动态窗口中寻找与预读缓冲器中的最匹配的数据，如果匹配的数据长度大于最小匹配长度(通常取决于编码器，以及动态窗口的大小，比如一个4K的动态窗口，它的最小匹配长度就是2)，那么就输出一对<长度(length)，距离(distance)>数组。长度(length)是匹配的数据长度，而距离(distance)说明了在输入流中向后多少字节这个匹配数据可以被找到。

例如：假设一个10个字节的动态窗口，以及一个5个字节的预读缓冲器，要传输的数据流为：A A A A A A A A A从B A B A A A A A，假设数据流的方向是从左到右。则动态窗口、预读缓存器中的内容分别为：动态窗口中包含10个A，这就是数据流左侧(前面)读取的10个字节。预读缓冲器包含了B A B A A，即窗口后面的字符。

第一步，寻找动态窗口与预读缓存器相似长度大于2的字节部分。在动态窗口中找不到B A B A A，所以B就被按照字面输出。然后动态窗口向后滑过1个字节，现在暂时输出了一个B。(此时动态窗口中的内容为“AAAAAAAAAB”，预读缓冲器的内容“A B A A A”(此时预读缓冲器中最左侧的B输出了，而在最右侧又读了一个字符A)。

第二步，用预读缓存器中的内容再和动态窗口中的内容进行比较。这时，在动态窗口找到了相似长度为2的A B，因此一对<长度，距离>就被输出了。长度(length)是2并且向后距离也是2，所以输出为<2，2>，这里的距离是从窗口最右侧字符起计算的距离，然后动态窗口向后(右)滑过2个字节(2个字符)。

现在已经输出了B<2，2>。此时动态窗口中为“AAAAAAABAB”？而预读缓冲器中为“AAAAA”。

第三步：继续上面的方法得到输出结果<5，8>，因为距离指的是这个字符串距离动态窗口最右边的距离也就是从右边数A A A A A B A B然后取前五位就是A A A A A了，所以是<5，8>。现在已经输出了B<2，2><5，8>。

最终的数据段查找结果是：A A A A A A A A A A B<2，2><5，8>，这些数据可以利用一个数据表管理起来，以便进行数据的编码操作。其中，根据数组<2，2>、<5，8>，就能够以初始窗口的数据为基础，得到的数据分割点和分割出的具体数据段。

在上述过程中，每得到一个数据段，即是确定了一个分割出的数据段，都要进行图1实施例的步骤13、14等，用于查找引用标签。当检查到AB重复时如果判断为不经常出现则依然以AB的形式输出，同时存入备用数据库中。当检查到A A A AA在热数据库中存在，则用F(AAAAA)这个标签来替代A A A A A。

可以通过散列值定位，在数据库中检查F(AAAAA)是否存在，如果存在则输出F(AAAAA)，如果不存在，但如果其在备用数据库中，并且认为其重复率达到了指标(大于或等于制定的阈值)，则将其移动到热数据库中。即，如果指纹函数F(AAAAA)得到的值F(X)在热数据库中无记载，而从学习时判断得知AAAAA重复的概率很大，则将F(X)和AAAAA绑定后存储入所述热数据库。所以A A A A A A A A A A AB A B A A A A A为例的字符串的压缩之后的编码是：A A A A A A A A A A AB A B F(AAAAA)。

如前所述的方法实际上描述了内容引导分割的方案，例如，从窗口内的数据起点开始连续扫描数据，查找所述窗口后部紧邻所述窗口的连续的最长字符串并记录所述字符串，实际上就是一种内容引导分割的方法，这种方法的特点是随着数据流的输入而不断完成数据分割的操作，在数据流输入完毕后，数据流的分割点就已经确定，不需要数据全部输入就可以启动数据段的分割操作。这里所述的动态窗口、预读缓存器，以及计算查找重复数据段的指纹函数F(X)共同作用完成数据段的分割。一个确定的指纹函数还可以引发返回一个逻辑值，标识是否在热数据库中找到一个高重复概率的数据段，根据该值以及动态窗口可以用来确定一个可以分割的数据段的边界，这个所述的边界的序列，就是利用一个指纹函数，在输入数据流上确定的一系列的分割点，利用所述分割点就可以得到分割的数据段和长度。例如，如果指纹函数以及具备一个给定的偏移量的数据及其长度，加上动态窗口以及一个确定的指纹值时，例如该指纹函数的值为1时，就可以确定一个分割出的数据段。

很多时候，窗口的大小即偏移量并不总能处于理想状态，因此，可能经常调整窗口的偏移量和大小，即动态确定窗口的大小和位置，这样也会消耗一些数据，形成剩余数据，但是这样的收益是可能获得更多或更长的重复数据段。

图7是本发明所述装置的第一个实施例框图；图7所示数据分割装置，包括存储数据段和与其绑定的引用标签的第一数据库75，以及一个用于存储数据分割结果的第二数据库74，还包括一个数据段选择单元71，它用一个预设长度的窗口从待编码的数据流中选取部分待编码的数据，并且，所述单元71还用于从窗口内的数据中随机选取一个数据段；还包括一个数据段匹配单元72，用所述数据段选择单元提供的数据段到第一数据库中匹配相应的记录；还包括一个窗口移动单元，用于将所述窗口顺序向后移动相应的长度，或者，将所述窗口顺序向后移动第二预定长度。

输入分数据流或者一段从输入缓冲区中取出的数据，顺序流入数据段选择单元71，所述单元71用一个所述预设长度的窗口从流入的待编码的数据流中选取部分数据，待所述窗口内的数据确定后，就从窗口内的数据中随机选取一个数据段用于到所述第一数据库中去比较，以找到对应的引用标签。所述数据段选择单元71从窗口内的当前数据起点开始连续扫描数据，记录扫描到的特定字符的个数，如果所述预定字符的个数值大于所述第一预定长度值，将扫描到的连续字符构成的字符串作为分割的数据段。

所述数据段选择单元71还可以这样选择数据段：从窗口内的数据起点开始连续扫描数据，查找所述窗口后部紧邻所述窗口的连续的最长字符串并记录所述字符串，如果所述字符串的字符个数值大于所述第一预定长度值，将扫描到的字符串作为分割的数据段。

前面所述字符串就是找到的数据段，如果找到了所述数据段，将该数据段交给数据段匹配单元72，由单元72到第一数据库75中匹配，更具体地说，所述数据段匹配单元72通过计算所述数据段的散列值，用所述散列值到第一数据库中匹配相应的记录，看该数据段是否为可以用引用标签代替的高重复概率数据段。因此单元72判断所述匹配是否成功，如果没有匹配成功，可以认为所述数据段不是高重复概率数据段，应当移动窗口继续查找，因此指示窗口移动单元73将所述窗口向数据流的后部方向移动一个指定的偏移量后继续选择数据段。所述偏移量也是一个预定的长度，最好等于1，使所述窗口向后移动1个数据单位，例如1个字节，这样就会实现数据流的不间断匹配查找。在本发明的另外实施例中，为了提高数据流的处理速度，使所述窗口向后移动的偏移举例大于1个数据单位，例如使所述窗口向后移动5个字节。

如果单元72的匹配成功，说明所述数据段就是高重复概率数据段，可以在数据传输时用引用标签代替。因此以所述数据段在窗口中的位置为依据确定数据分割点，还可以进一步为后续的数据传输做一些必要的准备，例如，将所述分割点存储在第二数据库74中，或者用数据库中的相应的引用标签标识所述数据段，然后直接存储所述标签在第二数据库74中，从而形成一个按顺序存储标签和剩余数据的数据表，所述标签也可能是更高级的标签。

然后指示窗口移动单元73将所述窗口顺序向后移动相应的长度，所述相应的长度为数据段的长度或大于数据段的长度。所述窗口移动的长度可以灵活决定，窗口向后移动的长度可以大于或等于数据段的长度，但小于可能引起数据段的重复从而导致数据传输的混乱或失败。最好所述相应的长度等于数据段的长度，这样作是为了避免遗漏作为判断起点的字符。

图8是本发明所述装置的第二个实施例框图。图8所示装置在图7的基础上增加了第一处理单元78，所述单元78用于当用所述散列值到数据库中匹配相应的记录没有成功时，判断所述数据段是否为高概率重复字符串，如果是，为该字符串分配引用标签，计算所述字符串的散列值，将所述散列值与所述引用标签、字符串绑定后存储入所述第一数据库75。

图8所示装置还包括第三数据库76，用于存储重复概率较低的数据段和其重复次数。所述第三数据库就是前文所说的冷数据库。还包括第二处理单元77，用于将第三数据库中重复次数大于指定阈值的数据段存储入所述第一数据库，以及，将第一数据库中被引用次数小于指定阈值的数据段移动到所述第三数据库。

在本发明的其它实施例中，在图7所示装置基础上，增加第一处理单元78，就可以使所述装置增加学习功能；增加第三数据库76，可以辅助学习功能使之进一步改善；而增加第二处理单元77，则会使学习功能效果最佳。从而，在所述第一数据库75的内容较少时，本发明也能很好地工作，具有较佳的性能。

Claims (18)

1.一种数据分割方法，其特征在于包括：

用一个预设长度的窗口从待编码的数据流中选取部分待编码的数据；

从窗口内的数据中随机选取一个数据段；

用所述数据段到第一数据库中匹配相应的记录，如果匹配成功，确定数据分割点，将所述窗口顺序向后移动相应的长度；否则，将所述窗口顺序向后移动第二预定长度；

所述相应的长度为等于数据段的长度或大于数据段的长度。

2.如权利要求1所述的数据分割方法，其特征在于，从窗口内的数据中随机选取大于第一预定长度的数据段。

3.如权利要求2所述的数据分割方法，其特征在于，用一个预设长度的窗口从待编码的数据流的起点连续选取待编码的数据。

4.如权利要求3所述的数据分割方法，其特征在于，按照下述步骤随机选取大于第一预定长度的数据段：

从窗口内的当前数据起点开始连续扫描数据，记录扫描到的特定字符的个数；

如果所述特定字符的个数值大于所述第一预定长度值，将扫描到的连续字符构成的字符串作为分割的数据段。

5.如权利要求3所述的数据分割方法，其特征在于，按照下述步骤随机选取大于第一预定长度的数据段：

从窗口内的数据起点开始连续扫描数据，查找所述窗口后部紧邻所述窗口的连续的最长字符串并记录所述字符串；

如果所述字符串的字符个数值大于所述第一预定长度值，将扫描到的字符串作为分割的数据段。

6.如权利要求1、2、3、4或5所述的数据分割方法，其特征在于还包括，计算所述数据段的散列值，以及，用所述散列值到数据库中匹配相应的记录。

7.如权利要求6所述的数据分割方法，其特征在于，所述第二预定长度等于1或大于1。

8.如权利要求7所述的数据分割方法，其特征在于还包括，当用所述散列值到数据库中匹配相应的记录没有成功时，判断所述数据段是否为高概率重复字符串，如果是，为该字符串分配引用标签，计算所述字符串的散列值，将所述散列值与所述引用标签、字符串绑定后存储入所述数据库。

9.如权利要求4所述的数据分割方法，其特征在于，当用所述数据段到数据库中匹配相应的记录没有成功，调整窗口内的当前数据起点后继续随机选取数据段，直到所述窗口的调整不满足设定的条件时，将所述窗口顺序向后移动第二预定长度。

10.如权利要求8所述的数据分割方法，其特征在于还包括，设置一个第二数据库作为备用数据库，用于存储重复概率较低的数据段和其重复次数，以及，将第二数据库中重复次数大于指定阈值的数据段存储入所述第一数据库。

11.如权利要求10所述的数据分割方法，其特征在于还包括，将第一数据库中被引用次数小于指定阈值的数据段移动到所述第二数据库。

12.一种数据分割装置，包括存储数据段和与其绑定的引用标签的第一数据库，以及一个用于存储数据分割结果的第二数据库，其特征在于还包括：

数据段选择单元，用一个预设长度的窗口从待编码的数据流中选取部分待编码的数据，以及，从窗口内的数据中随机选取一个数据段；

数据段匹配单元，用所述数据段选择单元提供的数据段到第一数据库中匹配相应的记录；

窗口移动单元，用于将所述窗口顺序向后移动相应的长度，或者，将所述窗口顺序向后移动第二预定长度；

所述相应的长度为等于数据段的长度或大于数据段的长度。

13.如权利要求12所述的数据分割装置，其特征在于，所述数据段选择单元从窗口内的当前数据起点开始连续扫描数据，记录扫描到的特定字符的个数；

如果所述特定字符的个数值大于第一预定长度值，将扫描到的连续字符构成的字符串作为分割的数据段。

14.如权利要求12所述的数据分割装置，其特征在于，所述数据段选择单元从窗口内的数据起点开始连续扫描数据，查找所述窗口后部紧邻所述窗口的连续的最长字符串并记录所述字符串；

如果所述字符串的字符个数值大于第一预定长度值，将扫描到的字符串作为分割的数据段。

15.如权利要求12、13或14所述的数据分割装置，其特征在于还包括，所述数据段匹配单元计算所述数据段的散列值，以及，用所述散列值到数据库中匹配相应的记录。

16.如权利要求15所述的数据分割装置，其特征在于还包括，

第一处理单元，用于当用所述散列值到数据库中匹配相应的记录没有成功时，判断所述数据段是否为高概率重复字符串，如果是，为该字符串分配引用标签，计算所述字符串的散列值，将所述散列值与所述引用标签、字符串绑定后存储入所述数据库。

17.如权利要求16所述的数据分割装置，其特征在于还包括，

第二数据库，用于存储重复概率较低的数据段和其重复次数。

18.如权利要求17所述的数据分割装置，其特征在于还包括，

第二处理单元，用于将第二数据库中重复次数大于指定阈值的数据段存储入所述第一数据库，以及，将第一数据库中被引用次数小于指定阈值的数据段移动到所述第二数据库。

Images