Manipulating the actual or effective window size in a data-dependant variable-length sub-block parser
View Patent ↗Example systems and methods concern a sub-block parser that is configured with a variable sized window whose size varies as a function of the actual or expected entropy of data to be parsed by the sub-block parser. Example systems and methods also concern a sub-block parser configured to compress a data sequence to be parsed before parsing the data sequence. One example method facilitates either actually changing the window size or effectively changing the window size by manipulating the data before it is parsed. The example method includes selectively reconfiguring a data set to be parsed by a data-dependent parser based, at least in part, on the entropy level of the data set, selectively reconfiguring the data-dependent parser, based, at least in part, on the entropy level of the data set, and parsing the data set.
1. A sub-block parser configured with a variable sized window,
where the variable sized window is used by the parser to parse a block of data into smaller sub-blocks of data by passing the variable sized window over the block of data to identify sub-block boundary locations,
where the smaller sub-blocks of data are mutually exclusive subsets of the block of data,
where a window location is defined by b[k−A+1 . . . k+B], b being the block of data, k being an integer, A being an integer, and B being and integer greater than A,
and where a sub-block is defined by the location of two boundaries placed by the parser at two different window locations, where A and B vary as a function of an attribute of the block of data being parsed.
2. The sub-block parser of claim 1 , where the sub-block parser increases the information density of the data block to be parsed before parsing the data block.
3. An apparatus, comprising:
a processor;
a memory;
a set of logics; and
an interface connecting the processor, the memory, and the set of logics, the set of logics comprising:
a window alteration logic that changes the actual size of a window or the effective size of the window, the window being used by a data-dependent deduplication parser to identify sub-block boundary locations in a set of data to be deduplicated, where the window is used by the data-dependent deduplication parser to parse the set of data into smaller sub-blocks of data, where the sub-blocks of data are subsets of the set of data, and where the size of the window varies as a function of an attribute of the set of data.
4. The apparatus of claim 3 , where the window alteration logic changes the actual size of the window by:
determining a desired length for the window, where the desired length is a function of the entropy level of the data set, and where the desired length is selected to facilitate the parser parsing the data set into a set of sub-blocks having a desired distribution of sub-block sizes; and
setting the window length to the desired length.
5. The apparatus of claim 3 , where the window alteration logic changes the effective size of the window by:
increasing the information density of the data set by performing run length coding on the data set, identifying a known common byte sequence in the data set and replacing the known common byte sequence with replacement data in the data set, identifying a known common byte sequence in the data set and removing the known common byte sequence from the data set, performing a Huffman coding on the data set, or performing an arithmetic coding on the data set.
6. The apparatus of claim 3 , where the window alteration logic changes the effective size of the window by:
selectively replacing a patterned sequence in the data set with an iterative sequence.