Back to results
US 6,650,261 B2Granted
Sliding window compression method utilizing defined match locations
AssigneeXerox Corporation
InventorsWilliam E. Nelson, James M. Sweet, Norman W. Zeck, Ronald E. Rider
Life of this patent
Estimating the term…
Abstract
An improved sliding window dictionary-based compression method limits the data within the sliding window searched to data strings occurring at each discrete match location within a plurality of predefined discrete match locations, the plurality of predefined discrete match locations comprising a set of non-continuous data positions within the window of data.
Claims16
A method of compressing data, comprising:
- receiving an input stream of data, the input stream including a sequence of data elements to be compressed;
- identifying a coding position;
- identifying a compress string within the input stream, the compress string including a set of data elements occurring at the coding position;
- comparing the compress string with a string of data elements at each match location within a plurality of predefined match locations to determine if a match exists at the respective match location, the plurality of predefined match locations defining a set of discrete, non-continuous data elements form the input stream;
- identifying a best match location, the best match location having the longest string of continuous data elements matching a compress string comprising a corresponding number data elements;
- and
- providing a pointer, the pointer identifying the best match location and the length of the compress string.
4 more elements
A method of compressing data, comprising:
- receiving an input stream of data, the input stream including a sequence of data elements to be compressed;
- selecting a compress string within the input stream, the compress string including at least one data element occurring at a coding position;
- identifying a plurality of match locations associated with the coding position;
- setting a status for each match location with the plurality of match locations, the status identifying whether the corresponding match location is active or inactive;
- simultaneously comparing the compress string with data elements match locations having an active status to determine if a match exists at the respective match location, and updating the status of the match location based on the comparison;
- increasing the length of the compress string by adding at least one data element to the compress string;
- repeating the steps of simultaneously comparing and increasing the length of the compress string until all match locations within the plurality of match locations have an inactive status;
- providing a pointer, the pointer identifying a match location which matches the compress string and the length of the compress string.
5 more elements
A method of compressing data, comprising:
- receiving an input stream of data, the input stream including a sequence of data elements to be compressed, wherein the input stream of data includes raster ordered image data comprising a plurality of scan lines with each scan line having a plurality of pixels;
- converting the raster ordered image data into block ordered data;
- identifying a coding position;
- identifying a compress string within the block ordered data, the compress string including a set of data elements occurring at the coding position;
- comparing the compress string with a string of data elements at each match location within a plurality of predefined match locations to determine if a match exists at the respective match location, the plurality of predefined match locations defining a set of discrete, non-continuous data elements from the input stream;
- and
- providing a pointer, the pointer identifying a match location which matches the compress string and the length of the compress string.
4 more elements
Dependencies are inferred from the claim text.