Method and apparatus for compressing data

• US 5,563,595 A
• Filed: 12/23/1993
• Issued: 10/08/1996
• Est. Priority Date: 12/23/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Strohacker, Oscar C.
• Primary Examiner(s): Gaffin, Jeffrey A.
• Assistant Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US08/173,738
• Time in Patent Office: 1,020 Days
• Field of Search: 341/50, 341/51, 341/106, 341/87, 341/95
• 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 apparatus for compressing data including apparatus for using a received data element as an address to a location in a memory, an apparatus for determining whether the addressed memory location contains a first record of a first matching data element, and an apparatus for generating a pointer to the first matching data element. In addition, a method for compressing data including the steps of using a received data element as an address to a location in a memory, determining whether the addressed memory location contains a first record of a first matching data element, and generating a pointer to the first matching data element.

Claims

1. An apparatus for compressing data comprising:

means for using a received data element as an address to a location in a memory;

means for determining whether the addressed memory location contains a first record of a first matching data element; and

means for generating a pointer to the first matching data element.

2. The apparatus of claim 1 wherein the means for using a received data element further includes using a second received data element as a second address to a second location in the memory.

3. The apparatus of claim 2 wherein the means for determining includes determining whether the second addressed location of the memory includes a second record of a second matching data element contiguous to the first matching data element.

4. The apparatus of claim 3 wherein the means for generating includes generating a pointer to the first and second matching data elements.

5. The apparatus of claim 4 wherein the means for using a received data element as an address to a location in a memory includes using a received data element as an address to one of a plurality of shift registers.

6. A data processing system comprising:

a memory for storing data;

a processor for processing data;

means for using a received data element as an address to a location in the memory;

means for determining whether the addressed memory location contains a first record of a first matching data element; and

means for generating a pointer to the first matching data element.

7. The data processing system of claim 6 wherein the means for using a received data element further includes using a second received data element as a second address to a second location in the memory.

8. The data processing system of claim 7 wherein the means for determining includes determining whether the second addressed location of the memory includes a second record of a second matching data element contiguous to the first matching data element.

9. The data processing system of claim 8 wherein the means for generating includes generating a pointer to the first and second matching data elements.

10. The data processing system of claim 9 wherein the means for using a received data element as an address to a location in a memory includes using a received data element as an address to one of a plurality of shift registers.

11. A method for compressing data comprising the steps of:

using a received data element as an address to a location in a memory;

determining whether the addressed memory location contains a first record of a first matching data element; and

generating a pointer to the first matching data element.

12. The method of claim 11 wherein the step of using a received data element further includes using a second received data element as a second address to a second location in the memory.

13. The method of claim 12 wherein the step of determining includes determining whether the second addressed location of the memory includes a second record of a second matching data element contiguous to the first matching data element.

14. The method of claim 13 wherein the step of generating includes generating a pointer to the first and second matching data elements.

15. The method of claim 14 wherein the step of using a received data element as an address to a location in a memory includes using a received data element as an address to one of a plurality of shift registers.

16. A computer program product executable by a processor and stored in memory for compressing data comprising:

means for using a received data element as an address to a location in a memory;

means for determining whether the addressed memory location contains a first record of a first matching data element; and

means for generating a pointer to the first matching data element.

17. The computer program product of claim 16 wherein the means for using a received data element further includes using a second received data element as a second address to a second location in the memory.

18. The computer program product of claim 17 wherein the means for determining includes determining whether the second addressed location of the memory includes a second record of a second matching data element contiguous to the first matching data element.

19. The computer program product of claim 18 wherein the means for generating includes generating a pointer to the first and second matching data elements.

20. The computer program product of claim 19 wherein the means for using a received data element as an address to a location in a memory includes using a received data element as an address to one of a plurality of shift registers.