Data compression method and apparatus utilizing an adaptive dictionary

• US 5,298,895 A
• Filed: 11/19/1991
• Issued: 03/29/1994
• Est. Priority Date: 01/19/1990
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Van Maren, David J.
• Primary Examiner(s): Young, Brian K.
• Application Number:
  US07/761,783
• Time in Patent Office: 861 Days
• Field of Search: 341/51, 341/50, 341/59, 341/67, 341/87, 341/89, 341/90, 341/106, 341/65, 341/55, 360/39, 364/939, 364/939.3, 364/952.6
• US Class Current: 341/51
• CPC Class Codes: G11B 20/00007 Time or data compression or expansion audio compression based on psychoacoustics G10L19/00; data processing for reproducing audio data at different playback speeds G10L21/04; video compression H04N19/00; data compression per se H03M7/30
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

The present invention provides a method and apparatus for compressing user data and for storing the user data on magnetic tape. The user data is accepted and organized into a plurality of records. The user data is then compressed according to a compression algorithm involving converting at least some of the user data to codewords using a dictionary which is derived from the data. The compressed data is flushed from memory before a new dictionary is created. The user data may be written to magnetic tape after being organized into groups, the groups being independent of the record organization. A codeword indicating the start of a new dictionary is inserted at the beginning of a group and preferably at the beginning of the first record within a group. Records may be further organized into entities. A codeword indicating a flush operation is inserted following each entity and a codeword indicating the start of a new dictionary is inserted at the beginning of the first entity within a group.

Claims

1. A method for compressing user data comprising the steps of:

receiving a stream of user data organized into a plurality of records;

compressing the user data according to a compression algorithm by converting selected data to codewords using a dictionary derived from the user data, the user data so compressed being output from said compression algorithm and defining compressed data, said compression algorithm having a flush operation causing said compression algorithm to output substantially all of the selected user data undergoing compression up to a time of said flush operation, irrespective of a degree of compression attained;

starting a derivation of at least a second dictionary from the user data during compression thereof; and

carrying out a plurality of said flush operations between the beginning of consecutive dictionaries.

2. A method according to claim 1, comprising the step of carrying out said flush operation at an end of each record.

3. A method according to claim 1, comprising the step of outputting information identifying said flush operations within the compressed data.

4. A method according to claim 1, comprising the step of outputting information identifying the beginning of new dictionaries within the compressed data.

5. A method according to claim 1, comprising the steps of:

outputting the compressed data in groups independent of a record structure of the user data; and

beginning one new dictionary substantially at the beginning of each group.

6. A method according to claim 5, comprising the step of beginning one new dictionary at the beginning of a first new record in each group.

7. A method according to claim 5, comprising the steps of:

organizing user data records into entities, each entity comprising one or more records; and

carrying out said flush operation at the end of each entity.

8. A method according to claim 5, comprising the steps of:

organizing user data records into entities, each entity comprising one or more records; and

beginning a new dictionary at the beginning of a first new entity in each group.

9. A method according to claim 1, further comprising the step of storing said compressed data on tape.

10. An apparatus for compressing user data comprising:

interface means for receiving a stream of user data organized into a plurality of records;

compression means for compressing the user data according to a compression algorithm involving converting selected user data to codewords using a dictionary derived from the user data, the user data so compressed being output from said compression means and defining compressed data;

said compression means comprising a flush means for effecting a flush operation, said flush operation causing said compression means to output substantially all of the selected user data undergoing compression up to a time of said flush operation, irrespective of a degree of compression attained;

reset means for starting a derivation of at least a second dictionary from the user data during compression thereof; and

said flush means being arranged to carry out a plurality of said flush operations between the beginning of consecutive dictionaries.

11. The apparatus according to claim 10, wherein said flush means carries out said flush operation at an end of each record.

12. The apparatus according to claim 10, further comprising identification means for outputting information identifying said flush operations within the compressed data.

13. The apparatus according to claim 10, further comprising identification means for outputting information identifying the beginning of new dictionaries within the compressed data.

14. The apparatus according to claim 10, further comprising grouping means for outputting the compressed data in groups independent of a record structure of the user data, said reset means beginning one new dictionary substantially at the beginning of each group.

15. The apparatus according to claim 14, wherein one new dictionary is begun at the beginning of a first new record in each group.

16. The apparatus according to claim 14, further comprising means for organizing user data records into entities, each entity comprising one or more records, said flush means carrying out said flush operation at the end of each entity.

17. The apparatus according to claim 14, further comprising means for organizing user data records into entities, each entity comprising one or more records, said reset means beginning one new dictionary at the beginning of a first new entity in each group.

18. The apparatus according to claim 10, further comprising means for storing said compressed data on tape.