Sliding window compression method utilizing defined match locations

• US 6,650,261 B2
• Filed: 06/18/2002
• Issued: 11/18/2003
• Est. Priority Date: 09/06/2001
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Nelson, William E., Sweet, James M., Zeck, Norman W., Rider, Ronald E.
• Primary Examiner(s): Tokar, Michael
• Assistant Examiner(s): Mai, Lam T.
• Application Number:
  US10/175,242
• Publication Number:
  US 20030048207A1
• Time in Patent Office: 518 Days
• Field of Search: 341/51, 341/50, 341/84, 341/106, 709/247, 709/218, 358/1.15, 382/232, 382/236
• US Class Current: 341/106
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

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.

Claims

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

2. The method of compressing data according to claim 1, further comprising using a predefined table based for entropy coding of the match locations.

3. The method of compressing data according to claim 1, wherein the predefined match locations are identified as an offset from the coding position.

4. The method of compressing data according to claim 1, wherein each match location within the plurality of predefined match locations is defined as an absolute position within the input stream.

5. The method of compressing data according to claim 1, wherein the step of receiving an input stream of data includes:

receiving raster ordered image data, the raster ordered image data comprising a plurality of scan lines with each scan line having a plurality of pixels; and

converting the raster ordered image data into block ordered data.

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

7. The method according to claim 6, further comprising using a predefined table based for entropy coding of the match locations.

8. The method according to claim 6, further comprising:

updating a match length indicator for at least one match location based on a result of the step of simultaneously comparing.

9. The method according to claim 8, wherein the step of providing a pointer, includes identifying a match location having a match length indicator greater than a minimum match length.

10. The method according to claim 8, wherein the step of providing a pointer, includes identifying a match location having the longest match length indicator.

11. The method of compressing data according to claim 6, wherein the step of receiving an input stream of data includes:

receiving raster ordered image data, the raster ordered image data comprising a plurality of scan lines with each scan line having a plurality of pixels; and

converting the raster ordered image data into block ordered data.

12. The method according to claim 6, wherein the plurality of match locations define a set of discrete, non-continuous data elements from the input stream.

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

14. The method of compressing data according to claim 13, further comprising using a predefined table based for entropy coding of the match locations.

15. The method of compressing data according to claim 13, wherein the predefined match locations are identified as an offset from the coding position.

16. The method of compressing data according to claim 13, wherein each match location within the plurality of predefined match locations is defined as an absolute position within the input stream.