Method and apparatus for switching between data compression modes

• US 6,008,743 A
• Filed: 11/19/1997
• Issued: 12/28/1999
• Est. Priority Date: 11/19/1997
• Status: Expired due to Term

• Current Assignee: Uniloc 2017 LLC (SoftBank Group Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Jaquette, Glen Alan
• Primary Examiner(s): THAI, XUAN MARIAN
• Application Number:
  US08/974,199
• Time in Patent Office: 769 Days
• Field of Search: 710/68, 395/888, 341/50, 341/51, 341/55, 341/56, 341/60, 341/59, 341/63, 341/65, 341/67, 341/87, 341/90, 341/106
• US Class Current: 341/51
• 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
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

Disclosed are a method and apparatus for switching between lossless data compression modes, and the switching indicated by at least one multibit mode switch character. The binary format input data is received and a FIFO determination of the compression efficiency of the input data under each mode is made on an ongoing basis. The ongoing basis may be for each compressed code word or more. A FIFO comparison of the compression efficiencies under each mode are made, and the modes for compressing the input data are switched only upon the comparison, or accumulated comparisons, indicating the compression efficiency of the present mode is less than the compression efficiency of the other mode by a threshold value, the threshold value directly related to the number of bits in the multibit mode switch character. One or both of the data compression modes may comprise a Lempel-Ziv compression, such as ALDC (LZ-1 derivative) or DCLZ (LZ-2 derivative), for compressing the input data into variable sized tokens, and the FIFO compression efficiency may be determined based on the bit length of each variable sized token.

Claims

1. A method for switching between lossless data compression modes, from the one of said modes which is presently used for preceding binary format input data (present mode) to the other of said modes (other mode) for present binary format input data, said switching indicated by at least one multibit mode switch character having a number of bits, comprising the steps of:

receiving said present binary format input data;

FIFO determining compression efficiency of said present input data under each of said modes on an ongoing basis;

FIFO comparing said compression efficiencies for said present input data under each of said modes; and

switching from said present mode to said other mode for compressing said present input data for which said compression efficiency is determined in said FIFO determining step only upon said FIFO comparing step indicating said compression efficiency of said present mode being less than said compression efficiency of said other mode by a threshold value, said threshold value directly related to said number of bits in said multibit mode switch character.

2. The method of claim 1, wherein one of said data compression modes comprises a Lempel-Ziv based compression for compressing said input data into variable sized tokens;

and wherein said FIFO compression efficiency determination step comprises determining a bit length of each of said variable sized tokens.

3. The method of claim 1, wherein said FIFO comparison step comprises accumulating said comparisons of compression efficiencies;

and wherein said switching step comprises switching from said present mode to said other mode upon said accumulated compression efficiencies of said present mode being less than said accumulated compression efficiencies of said other mode by said threshold value.

4. The method of claim 3, wherein said FIFO comparison step comprises resetting said accumulated comparisons to zero in response to said switching step switching between modes.

5. The method of claim 3, wherein said data compression modes each provides an output word or token and wherein said FIFO comparison step is conducted for each said word or token of said data compression modes, and said comparisons are accumulated.

6. The method of claim 5, wherein said threshold value comprises two values, a first higher threshold value for efficiency comparisons for present input data of length less than a string length of a FIFO buffer, and a second lower threshold value for efficiency comparisons for present input data equal to said string length.

7. The method of claim 6, wherein said first higher threshold value is equal to a sum of the number of bits in said multibit mode switch characters to switch back and forth, and said second lower threshold value is equal to half (rounded up) the number of bits in said multibit mode switch character.

8. The method of claim 3, wherein one of said data compression modes comprises a Lempel-Ziv compression for compressing said input data into variable sized tokens;

and wherein said FIFO compression efficiency determination step comprises determining a bit length of each of said variable sized tokens.

9. The method of claim 8, wherein the other of said data compression modes comprises a passthrough mode.

10. The method of claim 9, wherein said passthrough mode excludes one control code symbol from literal passthrough to provide said at least one multibit mode switch character.

11. The method of claim 9, wherein said FIFO compression efficiency determination step of said Lempel-Ziv data compression is conducted by table lookup.

12. The method of claim 8, wherein said Lempel-Ziv data compression mode provides said output tokens and said passthrough mode provides output words, and wherein said FIFO comparison step is conducted for each said word or token of said data compression modes, and said comparisons are accumulated.

13. The method of claim 12, wherein said threshold value comprises two values, a first higher threshold value for efficiency comparisons for present input data of length less than or equal to a string length of a FIFO buffer, and a second lower threshold value for efficiency comparisons for present input data equal to said string length.

14. The method of claim 13, wherein said first higher threshold value is equal to a sum of the number of bits in said multibit mode switch characters to switch back and forth, and said second lower threshold value is equal to half (rounded up) the number of bits in said multibit mode switch character.

15. A data compression apparatus for switching between lossless data compression modes, from the one of said modes which is presently used on preceding binary format input data (present compression mode) to the other of said modes (other compression mode) for present binary format input data, indicating said switching with at least one multibit mode switch character having a number of bits, comprising:

an input for receiving said present binary format input data;

a first lossless data compressor coupled to said input for providing a first data compression of said present input data according to a first compression mode and providing an output of said present input data in said first compression mode;

a second lossless data compressor coupled to said input for providing a second data, compression of said input data according to a second compression mode and providing an output of said present input data in said second compression mode;

comparison logic coupled to said first and said second compressors, said comparison logic compares on an ongoing FIFO basis compression efficiency between said first and said second lossless data compressors in compressing said present input data, providing an efficiency comparison output, and wherein said comparison logic additionally compares said efficiency comparison output between said present compression mode and said other compression mode with a threshold value, said threshold value directly related to said number of bits in said multibit mode switch character, and wherein said comparison logic additionally providing a signal upon said efficiency comparisons exceeding said threshold value; and

a compression output selector coupled to said comparison logic and said first and said second compressors for selecting said output from one of said first and said second compressors at a time, and, upon said comparison logic providing said signal, switching between the one of said first and said second compressors in said present compression mode to the one of said first and said second compressors of said other compression mode, for said output of said present input data for which said comparison was made, and signaling said switch between said first and said second compressors by outputting said at least one multibit mode switch character.

16. The data compression apparatus of claim 15, wherein said comparison logic additionally comprises an accumulator for accumulating each said efficiency comparison and provides said efficiency comparison output, and wherein said comparison logic compares said accumulated efficiency comparison output with said threshold value.

17. The data compression apparatus of claim 16, wherein said accumulator is reset to zero upon said comparison logic providing said signal.

18. The data compression apparatus of claim 16, wherein said first lossless data compressor is a Lempel-Ziv based compressor for compressing said present input data into variable sized tokens;

and wherein said comparison logic efficiency comparison compares a bit length of each of said variable sized tokens to a corresponding bit length of said second lossless data compressor compression.

19. The data compression apparatus of claim 16, wherein said data compression modes each provides an output word or token and wherein said comparison logic conducts said FIFO comparison for each said word or token of said data compression modes, and said accumulator accumulates the results of said FIFO comparisons.

20. The data compression apparatus of claim 19, wherein said threshold comprises two threshold values, a first higher threshold value for efficiency comparisons for present input data having a string length less than or equal to that identified by a FIFO buffer, and a second lower threshold value for efficiency comparisons for present input data having a string length greater than that identified by said FIFO buffer.

21. The data compression apparatus of claim 20, wherein said first higher threshold value is equal to a sum of the number of bits in said multibit mode switch characters to switch back and forth, and said second lower threshold value is equal to half (rounded up) the number of bits in said multibit mode switch character.

22. The data compression apparatus of claim 20, wherein said first lossless data compressor is a Lempel-Ziv compressor for compressing said present input data into variable sized tokens;

and wherein said comparison logic efficiency comparison compares a bit length of each said variable sized token to a corresponding bit length of said second lossless data compressor compression.

23. The data compression apparatus of claim 22, wherein the other of said data compression modes comprises a passthrough mode.

24. The data compression apparatus of claim 23, wherein said passthrough data compression excludes one control code symbol from literal passthrough to provide said at least one multibit mode switch character.