Composite dictionary compression system

• US 5,530,645 A
• Filed: 06/30/1993
• Issued: 06/25/1996
• Est. Priority Date: 06/30/1993
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Chu, Ke-Chiang
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Ives, Felicia
• Application Number:
  US08/085,846
• Time in Patent Office: 1,091 Days
• Field of Search: 364/419.14, 364/419.11, 364/419.1, 341/51, 341/55, 341/79, 341/106, 382/56
• US Class Current: 715/236
• 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

A composite dictionary data compression process for use with a computer system comprising the steps of: receiving into the computer system an uncompressed input data string; searching a composite dictionary to detect for a dictionary data string matching the uncompressed input data string, the composite dictionary comprising a fixed dictionary and an adaptive dictionary; and modifying the adaptive dictionary in response to whether a matching dictionary data string is detected.

Claims

1. A composite dictionary data compression process for use with a computer system comprising the steps of:

receiving into the computer system an uncompressed input data string;

searching a composite dictionary to detect a dictionary data string matching the uncompressed input data string, the composite dictionary comprising a fixed dictionary and an adaptive dictionary; and

modifying the adaptive dictionary in response to whether a matching dictionary data string is detected.

2. A composite dictionary data compression process of claim 1 wherein the step of modifying the adaptive dictionary further comprises adding a new dictionary entry to the adaptive dictionary if a matching dictionary data string is not detected in the composite dictionary.

3. A composite dictionary data compression process of claim 2, wherein if a matching dictionary data string is not detected, the uncompressed input data string is inserted into an output data buffer as a literal string.

4. A composite dictionary data compression process of claim 2, wherein if a matching dictionary data string is detected, a corresponding address locator is inserted into an output data buffer.

5. A composite dictionary data compression process of claim 1 further comprising a decompression process, the decompression process comprising the steps of:

loading the computer system with the fixed dictionary;

initializing the adaptive dictionary;

detecting a compressed input data entry to decompress in a compressed input data buffer;

detecting if the compressed input data entry corresponds to stored data in the composite dictionary, and if the compressed input data entry is detected to correspond to stored data in the composite dictionary, then retrieving the stored data from the composite dictionary.

6. A composite dictionary data compression process of claim 5 wherein the step of retrieving the stored data from the composite dictionary further comprises using the compressed data entry as an address locator to find the stored data in the composite dictionary.

7. A composite dictionary data compression process of claim 5 wherein in response to detecting that the compressed data entry does not correspond to stored data from the composite dictionary, then the decompression process further comprises copying a literal data string from the compressed input data buffer to a decompressed output data buffer.

8. A composite dictionary data compression process of claim 7 further comprising the step of updating the composite dictionary in response to detecting that the compressed data entry does not correspond to stored data from the composite dictionary.

9. A composite dictionary data compression process of claim 8 wherein the step of updating the composite dictionary further comprises copying the literal data string from the compressed input data buffer to the composite dictionary.

10. A composite dictionary data compression process for use with a computer system, the compression process comprising the steps of:

initiating a composite dictionary, the composite dictionary comprising a fixed dictionary and an adaptive dictionary, wherein the step of initiating the composite dictionary comprises loading the fixed dictionary with a set of predefined data entries and resetting the adaptive dictionary;

receiving into the computer system an uncompressed input data string;

searching the composite dictionary to detect a dictionary data string matching the uncompressed input data string; and

modifying the composite dictionary in response to whether a matching dictionary data string is detected.

11. A composite dictionary data compression process of claim 10 wherein modifying the composite dictionary further comprises:

creating a dictionary entry in the adaptive dictionary for the uncompressed input data string in response to not detecting a matching data string in the composite dictionary.

12. A composite dictionary data compression process of claim 10 further comprising a composite dictionary data decompression process, the data decompression process comprising the steps of:

loading a plurality of application dependent dictionary entries into the fixed dictionary;

resetting the adaptive dictionary;

detecting whether an input data buffer contains at least one compressed input data entry;

decompressing the contents of the input data buffer in response to detecting a compressed input data entry.

13. A composite dictionary data compression process of claim 12 wherein the step of decompressing further comprises:

detecting whether the compressed input data entry comprises a literal data string;

wherein in response to not detecting a literal data string, then retrieving a matching dictionary data string from the composite dictionary, and

wherein in response to detecting a literal data string, then storing the literal data string into the decompressed data output buffer.

14. A composite dictionary data compression process of claim 13 further comprising updating the composite dictionary in response to detecting the literal data string.

15. A composite dictionary data compression process of claim 14 wherein the step of updating the composite dictionary in response to detecting the literal data string further comprises:

detecting whether the adaptive dictionary is full;

wherein if the adaptive dictionary is not full, then storing the literal data string in the adaptive dictionary.

16. A composite dictionary data compression of claim 15 wherein if the adaptive dictionary is full, then replacing an old dictionary entry from the adaptive dictionary with the literal data string.

17. A method for compressing data in a computer system, the method comprising the steps of:

retrieving a plurality of stored dictionary entries into a fixed dictionary;

performing the following steps for each input data string in a stream of input data strings;

searching a composite dictionary for a dictionary entry that matches the input data string, the composite dictionary comprising the fixed dictionary and an adaptive dictionary;

if a dictionary entry that corresponds to the input data string is found, then transmitting an address locator that identifies the dictionary entry that corresponds to the input data string;

if a dictionary entry that corresponds to the input data string is not found, then transmitting the input data string as a literal string; and

adding a dictionary entry that corresponds to the input data string to the adaptive dictionary.

18. The method for compressing data of claim 17 wherein said step of retrieving a plurality of stored dictionary entries comprises retrieving a plurality of stored dictionary entries that are associated with a particular software application.