一种基于极值的数据去重分块方法

摘要

本发明公开了一种基于极值的数据去重分块方法，其特征在于，包括：本发明是现有分块方法的改进，与现有分块方法的不同之处在于：1、本方法在局部非对称区域而不是对称区域内寻找局部极值来解决边界偏移问题；2、本发明将拥有局部极值的位置(即极值点)放在数据块的中间而不是作为数据块的边界；3、本发明在遇到相等的极值时将最先出现的极值所在的位置作为极值点。前两个不同点使得本发明在判断切点时所需的操作极少，因此可获得远高于现有分块方法的吞吐量；第三个不同点使本发明能够检测并消除掉部分低熵字符串中的重复数据。此外，本发明生成的数据块的块长方差较小且无需强制块长限制，因此能获得与传统分块方法相当或更高的去重率。

主权项

一种基于极大值的数据去重分块方法，其特征在于，所述方法包括以下步骤：(1)将滑动窗口置于数据流尚未分块的起始位置，设置该窗口的位置P为0，并根据窗口内容计算出该窗口的值V，将此窗口的V和P分别赋值给临时最大值V_max和V_max所在的位置P_max；(2)将滑动窗口向前滑动一个字节，设置当前窗口的位置P_curr为前一个窗口的位置P加1，计算当前窗口的值V_curr，并将V_curr与V_max进行比较:(2.1)如果V_curr＞V_max，则将V_curr和P_curr分别赋值给V_max和P_max，执行步骤(2)；(2.2)如果V_curr≤V_max，则检查P_curr与P_max的距离，如果距离小于预设值W，执行步骤(2)；如果距离等于预设值W，则V_max拥有局部区域内的最大值，其所在位置P_max为极值点，当前位置P_curr为切点；输出该切点，执行步骤(1)进行下一轮分块。