Method and apparatus for providing improved data compression efficiency for an adaptive data compressor

• US 5,874,907 A
• Filed: 09/19/1997
• Issued: 02/23/1999
• Est. Priority Date: 09/19/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Craft, David John
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US08/934,335
• Time in Patent Office: 522 Days
• Field of Search: 341/50, 341/51, 341/58, 341/59, 341/63
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

A method for providing improved data compression efficiency to a data compressor unit is disclosed. Before sending the uncompressed data stream to the data compressor unit, an incoming data byte from the uncompressed data stream is first compared with a preceding data byte from the uncompressed data stream. A first counter value is incremented in response to a match between the incoming data byte and the preceding data byte. A second counter value is then incremented in response to subsequent matches between an incoming data byte and its preceding data byte after the first counter value has reached a preset value. The second counter value is finally sent to the data compressor unit at the completion of a run of the incoming data byte in substitution of a portion of the run, such that the data compressor unit can quickly resume its optimal compression ratio after an occurrence of the run within the uncompressed data stream.

Claims

1. A method for providing improved data compression efficiency to a data compressor unit, said method comprising the steps of:

comparing an incoming data byte and a previous data byte from an uncompressed data stream, wherein said uncompressed data stream is to be received by said data compressor unit;

incrementing a first counter value in response to a match between said incoming data byte and said previous data byte;

incrementing a second counter value in response to said first counter value reaches a preset value to indicate a run within said uncompressed data stream;

substituting said run within said uncompressed data stream with said second counter value; and

transmitting said uncompressed data stream to said data compressor unit such that said data compressor can quickly resume an optimal compression ratio after an occurrence of said run within said uncompressed data stream.

2. The method for providing improved data compression efficiency to a data compressor unit according to claim 1, wherein said method further includes a step of resetting said first counter in response to a mismatch between said incoming data byte and said previous data byte.

3. The method for providing improved data compression efficiency to a data compressor unit according to claim 1, wherein said step of incrementing a second counter value further includes a step of incrementing a second counter value in response to a subsequent match between an incoming data byte and a previous data byte.

4. The method for providing improved data compression efficiency to a data compressor unit according to claim 3, wherein said method further includes a step of discarding said incoming data byte.

5. The method for providing improved data compression efficiency to a data compressor unit according to claim 1, wherein said completion of a run is indicated by a mismatch between an incoming data byte and a previous data byte.

6. A method for providing improved data compression efficiency to a data compressor unit, said method comprising the steps of:

preprocessing an uncompressed data stream by comparing an incoming data byte and a previous data byte from said uncompressed data stream, wherein said uncompressed data stream is to be received by said data compressor unit;

incrementing a first counter value in response to a match between said incoming data byte and said previous data byte to indicate a beginning of a run within said uncompressed data stream;

incrementing a second counter value in response to a subsequent match between an incoming data byte and a previous data byte after said first counter value has reached a preset value to indicate a remaining portion of said run within said uncompressed data stream;

substituting said remaining portion of said run within said uncompressed data stream with said second counter value; and

transmitting said uncompressed data stream embedded with said second counter value to said data compressor unit such that said data compressor can quickly resume an optimal compression efficiency despite an occurrence of said run within said uncompressed data stream.

7. The method for providing improved data compression efficiency to a data compressor unit according to claim 6, wherein said method further includes a step of resetting said first counter in response to a mismatch between said incoming data byte and said previous data byte.

8. The method for providing improved data compression efficiency to a data compressor unit according to claim 6, wherein said method further includes a step of discarding said incoming data byte.

9. The method for providing improved data compression efficiency to a data compressor unit according to claim 6, wherein said completion of a run is indicated by a mismatch between an incoming data byte and a previous data byte.

10. A pre-compressor for providing improved data compression efficiency to a data compressor unit, comprising:

a comparator for comparing an incoming data byte and a previous data byte from an uncompressed data stream, wherein said uncompressed data stream is to be received by said data compressor unit;

a first counter for counting a number of matches between said incoming data byte and said previous data byte, wherein said first counter is coupled with said comparator;

a second counter for counting a number of matches between said incoming data byte and said previous data byte after said first counter reaches a preset value, wherein said second counter is coupled said comparator; and

a transmitter for sending a value of said second counter to said data compressor unit at a completion of a run of said incoming data byte such that said data compressor can quickly resume back to its optimal compression ratio after an occurrence of said run within said uncompressed data stream.

11. The pre-compressor according to claim 10, wherein said pre-compressor further includes a reset for resetting said first counter in response to a mismatch between said incoming data byte and said previous data byte.

12. The pre-compressor according to claim 10, wherein said pre-compressor further includes a means for discarding said incoming data byte during the increment of said second counter.

13. The pre-compressor according to claim 10, wherein said completion of a run is indicated by a mismatch between an incoming data byte and a previous data byte.

14. The pre-compressor according to claim 10, wherein said pre-compressor further includes a means for substituting said run within said uncompressed data stream with said second counter value.