Method and apparatus for adaptive data compression

• US 4,881,075 A
• Filed: 10/15/1987
• Issued: 11/14/1989
• Est. Priority Date: 10/15/1987
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Weng, Lih-Jyh
• Primary Examiner(s): Shoop, Jr., William M.
• Assistant Examiner(s): YOUNG, BRIAN K
• Application Number:
  US07/108,892
• Time in Patent Office: 761 Days
• Field of Search: 340/347 DD, 235/310, 235/311, 364/200, 364/900, 358/260, 358/261, 382/56, 341/50, 341/51, 341/67, 341/87, 341/95, 341/106, 341/107
• US Class Current: 341/87
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

Data compression/decompression apparatus and methods are provided which exhibit significant data compression improvement over prior art methods and apparatus. This is achieved by providing an adaptive characteristic in which a pair of data compression/decompression translation tables are constructed based on the data which is to be compressed or decompressed. One table is used to compress or decompress while the other is being rebuilt, thus reflecting the characteristics of the most recent input data.

Claims

1. A method for compressing input data symbol signals to generate a stream of code value signals constituting a compressed form of the input data symbol signals, the method comprising:

a first step of loading a first translation table in memory with data symbol signals;

a second step of loading a second translation table in memory with input data symbol signals according to a predetermined table construction procedure;

a third step of generating a stream of the code value signals representative of input data symbols according to a predetermined data compression procedure using the contents of the first table;

a fourth step of loading the first table with the input data symbol signals according to the same predetermined table construction procedure as used in the second step;

a fifth step of generating a stream of the code value signals representative of input data symbols according to the same predetermined data compression procedure as used in the third step using the contents of the second table; and

a sixth step of repeatedly performing the second through fifth steps.

2. A method as recited in claim 1 wherein the first step comprises loading the first table with input data symbol signals according to the same predetermined table construction procedure as used in the second and fourth steps.

3. A method as recited in claim 1 wherein the first step comprises loading the first table with a predetermined set of data symbol signals.

4. A method as recited in claim 3 wherein the predetermined set of data symbol signals comprises data symbol signals other than the input data symbol signals.

5. A method as recited in claim 1 wherein the second and third steps are performed concurrently, and the fourth and fifth steps are performed concurrently.

6. A method as recited in claim 1 comprising a first intermediate step, between the first and second steps, of generating a first predetermined number of the code value signals from the first table according to the predetermined data compression procedure and a second intermediate step, between the third and fourth steps, of generating a second predetermined number of code value signals from the first table according to the predetermined data compression procedure.

7. A method as recited in claim 1 comprising a third intermediary step, between the first and second steps, of loading a first buffer with input data symbols.

8. A method as recited in claim 1 wherein the predetermined table construction procedure comprises:

a first substep of filling a second buffer in memory with input data symbol signals to be compressed;

a second substep of finding the longest string of data symbol signals in the second buffer which also appear in the table;

a third substep of incrementing the table size;

a fourth substep of concatenating the longest string of data symbol signals in the second buffer which also appears in the table with the next data symbol signal following in the second buffer and storing the concatenated string as the next table entry;

a fifth substep of deleting the concatenated string from the second buffer; and

a sixth step of repeatedly performing the second through fifth substeps.

9. A method as recited in claim 1 wherein the predetermined data compression procedure comprises:

a first substep of sequentially searching the translation table for the table entry consisting of the longest consecutive string of input data symbol signals, beginning with the first input data symbol signal;

a second substep of outputting the location in the translation table for the table entry consisting of the longest consecutive string of input symbols as the code value signal of the longest consecutive string;

a third substep of sequentially searching the translation table for the table entry consisting of the longest subsequent consecutive string or input data symbol signals, begining with the symbol after the last symbol in the string found as a result of the first substep;

a fourth substep of outputting the location in the translation table of the table entry consisting of the longest subsequent consecutive string of input symbols as the code of the longest subsequent consecutive string; and

a fifth substep of repeatedly performing the third and fourth substeps.

10. A method of generating a stream of data symbol signals from a stream of code value signals representing compressed data symbol signals, the method comprising:

a first step of loading data symbol signals in a first translation table in memory;

a second step of processing the code value signals using the first table according to a predetermined decompression procedure to generate a stream of data symbol signals;

a third step of loading data symbol signals in a second translation table in memory according to a predetermined table construction procedure;

a fourth step of processing the code value signals using the second table according to the same predetermined decompression procedure as used in the second step to generate a stream of data symbol signals;

a fifth step of loading the first table with data symbol signals according to the same predetermined table construction procedure as used in the third step; and

a sixth step of sequentially repeating the second through fifth steps.

11. A method as recited in claim 10 comprising a first intermediate step, between the first and second steps, of generating a first predetermined number of the code value signals from the first table according to the predetermined decompression procedure and a second intermediate step, between the third and fourth steps, of generating a second predetermined number of code value signals from the first table according to the predetermined decompression procedure.

12. A method as recited in claim 10 wherein the second and third steps are performed concurrently, and the fourth and fifth steps are performed concurrently.

13. A method as recited in claim 10 wherein the predetermined table construction procedure comprises:

a first substep of establishing a table size, inputting a first code value signal, setting a current index equal to the first code value signal, and setting an old index equal to the current index;

a second substep of terminating the procedure if there are no more code value signals to process;

a third substep of inputting the next code value signal and setting the current index equal to the next code value signal;

a fourth substep, performed if the current index is less than the table size, of incrementing the table size, adding a new entry to the end of the table which is equal to the first data symbol signal of the current index table entry concatenated to the old index table entry, and setting the old index equal to the current index;

a fifth substep, performed if the current index is not less than the table size, of incrementing the table size, adding a new entry to the end of the table which is equal to the first data symbol signal of the old index table entry concentrated to the old index table entry, and setting the old index equal to the table size; and

a sixth substep of repeatedly performing the second through fifth substeps.

14. A method as recited in claim 10 wherein the predetermined decompression procedure comprises:

a first substep of inputting a code value signal to be decompressed;

a second substep of setting the code value signal as an index to a translation table; and

a third substep of outputting the table entry specified by the index.

15. A method as recited in claim 10, wherein the first step comprises the step of loading data symbol signals in the first translation table using the predetermined table construction procedure.

16. A method of generating an output stream of decompressed data symbol signals from an input stream of code value signals representing compressed data symbol signals, the method comprising:

a first step of preloading a first translation table in memory with a predetermined set of data symbol signals;

a second step of processing the code value signals using the data symbols stored in the first table according to a predetermined decompression procedure to obtain a stream of decompressed data symbol signals;

a third step of loading a second translation table in memory with the decompressed data symbol signals obtained in the second step according to a predetermined table construction procedure;

a fourth step of repeatedly performing the second and third steps until the second table is full;

a fifth step of processing the code value signals using data symbol signals stored in the second table according to the same predetermined decompresssion procedure as used in the second step to supply decompresssed data symbol signals to the output stream;

a sixth step of loading the first table with the decompressed data symbol signals obtained in the fifth step according to the same predetermined table construction procedure as used in the third step;

a seventh step of repeatedly performing the fifth and sixth steps until the first table is full; and

an eighth step of repeatedly performing the second through seventh steps.

17. A method as recited in claim 16 comprising a first intermediate step, between said fourth and fifth step, of processing the code value signals using the data symbol signals stored in the first table according to the predetermined decompression procedure to supply a predetermined number of decompressed data symbol signals to the output stream.

18. A method as recited in claim 16 wherein the predetermined table construction procedure comprises:

a first substep of filling a buffer in memory with input data symbol signals to be compressed;

a second substep of finding the longest string of data symbol signals in the buffer which also appear in the table;

a third substep of incrementing the longest string of data symbol signals in the buffer which also appears in the table with the next data symbol signal following in the buffer and storing the concatenated string as the next table entry;

a fifth substep of deleting the concatenated string from the buffer; and

a sixth substep of repeatedly executing the second through fifth substeps.

19. Apparatus for compressing input data symbol signals to generate a stream of code value signals consisting of a compressed form of the input data symbol signals, the apparatus comprising:

first memory means for storing a plurality of data symbol signals as strings in a first translation table, each of the strings being associated with a code value signal;

second memory means for storing a plurality of input data symbol signals as strings in a second translation table, each of the strings being associated with a code value signal;

control means for initially loading the first table with data symbol signals, and for alternatingly generating a stream of the code value signals representive of input data symbol signals according to a predetermined data compression procedure using the contents of the first table while loading the second table with the input data symbol signals according to a predetermined table construction procedure until the second table is full and generating a stream of the code value sigals representative of input data symbol signals according to the same predetermined data compression procedure as used in generating the code value stream using the contents of the second table while loading the first table with the input data symbol signals according to the same predetermined table construction procedure as used in loading the second table until the first table is full.

20. An apparatus as recited in claim 19 wherein the control means comprises means for initially loading the first table with input data symbol signals according to the same predetermined table construction procedure as used in loading the second table.

21. An apparatus as recited in claim 19 wherein the control means comprises means for initially loading the first table with a predetermined set of data symbol signals.

22. An apparatus as recited in claim 21 wherein the control means comprises means for loading the first table with a predetermined set of data symbol signals other than the input data symbol signals.

23. An apparatus as recited in claim 19 wherein the control means comprises means for generating, after initially loading the first translation table intput data symbol signals, a first predetermined number of the code value signals from the first table according to the predetermined data compression procedure.

24. An apparatus as recited in claim 23 wherein the control means comprises means for generating, after alternatingly loading one of the first and second tables, a second predetermined number of code value signals from the respective alternatingly loaded table according to the predetermined data compression procedure.

25. Apparatus for generating a stream of data symbol signals from a stream of input code value signals representing compressed data symbol signals, the apparatus comprising:

first memory means for storing a plurality of data symbol signals as strings in a first translation table, each of the strings being associated with a code value signal;

second memory means for storing a plurality of input data symbol signals as strings in a second translation table, each of the strings being associated with a code value signal; and

control means for initially loading the first table with data symbol signals using input code values according to a predetermined decompression table construction procedure, and for alternatingly processing the code value signals using the first table according to a predetermined decompression procedure to generate a stream of data symbol signals while loading data symbol signals in the second translation table according to a predetermined table construction procedure and processing the code value signals using the second table according to the same predetermined decompression procedure as used in processing the code value signals from the first table to generate a stream of data symbol signals while loading the first table with data symbol signals according to the same predetermined table construction procedure as used in loading the first table.

26. Apparatus for generating an output stream of decompressed data symbol signals from an input stream of code value signals representing compressed data symbol signals, the apparatus comprising:

first memory means for storing a plurality of data symbol signals as strings in a first translation table, each of the strings being associated with a code value signal, the table containing preloaded data symbol signals;

second memory means for storing a plurality of input data symbol signals as strings in a second translation table, each of the strings being associated with a code value signal; and

control means for generating a stream of data symbol signals according to a predetermined table decompresssion procedure using preloaded data symbol signals in the first table, and for alternatingly processing the code value signals using the first table according to the same predetermined decompression procedure to generate a stream of data symbol signals while loading data symbol signals in the second translation table according to a predetermined table construction procedure using the generated data symbol signals and processing the code value signals using the second table according to the same predetermined decompression procedure to generate a stream of data symbol signals while loading data symbol signals in the first table according to the same predetermined table construction procedure using the generated data symbol signals.

27. Apparatus as recited in claim 26 wherein the control means comprises means for generating, after alternatingly loading one of the first and second tables, a predetermined number of data symbol signals from input code value signals using the respective alternatingly loaded table according to the predetermined data compression procedure.

28. Apparatus as recited in claim 26 comprising buffer means for storing a plurality of the generated data symbol signals for use in alternatingly loading the tables.