Deflate compression algorithm

摘要

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.

主权项

1. 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.