Deflate compression algorithm
AssigneeMicron Technology, Inc.
InventorYingquan Wu
Life of this patent
Estimating the term…
Abstract
A compression algorithm replaces duplicative strings with a copy pair indicating a location and length of a preceding identical string that is within a window from the duplicative string. Rather than a replacing a longest matching string within a window from a given point with a copy pair, the longest matching string may be used provide it is at least two bytes larger than the next longest matching string or is at a distance that is less than some multiple of a distance to the next longest matching string. In another aspect, the length of the window in which a matching string may be found is dependent on a length of the matching string. In yet another aspect, rather than labeling each literal and copy pair to indicate what it is, strings of non-duplicative literals are represented by a label and a length of the string.
Claims21
An apparatus for compression comprising one or more processors and one or more memory devices operably coupled to the one or more processors, the one or more memory devices storing executable code effective to cause the one or more processors to:
- provide a distance multiple A and a minimum length parameter B, both being integers;
- evaluate a plurality of bytes in a data file to identify duplicative strings by, at each point of a plurality of points in the data file:
- identifying a longest candidate string starting at the each point for which a preceding matching string in the file is identical to the longest candidate string and for which at least one of (a) the preceding matching string has at least one of a length meeting a length threshold defined by B and an length difference with respect to a next longest matching string meeting a length difference threshold defined by B, the next-longest matching string preceding the each point and matching a portion of the longest candidate string beginning at the each point and (b) the preceding matching string begins at a distance Di from the each point that is less than A times a distance Dmax to a beginning of the next-longest matching string;
- and
- replacing the longest candidate string with a copy pair including the distance Di and a length of the candidate string.
An apparatus for compression comprising one or more processors and one or more memory devices operably coupled to the one or more processors, the one or more memory devices storing executable code effective to cause the one or more processors to:
- identify, among a plurality of literals of a data file, duplicative strings Si, i=1 to P, P being a number of the duplicative strings, each duplicative string Si having a length Li and being identical to a preceding string located before the duplicative string located a distance Di before the each duplicative string Si;
- identify, among the plurality of bytes of the data file, literal strings Lj, j=1 to M, M being a number of the literal strings, each literal string being a string of contiguous literals in the data file, each literal string Lj not being preceded by an identical string in the data file that meets at least one of a length and a distance criteria with respect to the literal string;
- generate a first portion of the output file wherein:
- before each literal string Li of a first portion of the literal strings Li located in an initial portion of the data file are inserted a literal label and N bits encoding a length of the literal string;
- and
- each duplicative string Si is replaced by a copy pair indicating a length of the duplicative string and the distance Di corresponding thereto;
- and
- generate a second portion of the output file wherein:
- a literal label is inserted before each literal of each literal string Li;
- and
- each duplicative string Si is replaced by a copy label and a copy pair indicating a length of the duplicative string and the distance Di corresponding thereto.
An apparatus for compression comprising one or more processors and one or more memory devices operably coupled to the one or more processors, the one or more memory devices storing executable code effective to cause the one or more processors to:
- sequentially evaluate a plurality of bytes in a data file to identify duplicative strings by, at each point of a plurality of points in the data file:
- identifying a longest candidate string having a length and starting at the each point for which a matching preceding string is found before the each point and within a maximum distance corresponding to the length;
- and
- replacing the longest candidate string with a copy pair including the distance Di and a length of the longest candidate string.
Dependencies are inferred from the claim text.