Semi-static data compression/expansion method

• US 5,323,155 A
• Filed: 12/04/1992
• Issued: 06/21/1994
• Est. Priority Date: 12/04/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sinha, Bhaskar, Iyer, Balakrishna R., Sherwin, Elton B. Jr., Meriwether, Teresa A.
• Primary Examiner(s): Hoff, Marc S.
• Application Number:
  US07/985,409
• Time in Patent Office: 564 Days
• Field of Search: 341/51, 341/67, 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/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A method of transmitting compressed data using a Ziv-Lempel compression/expansion algorithm, using an adaptive Ziv-Lempel (AZL) dictionary modified to a mature state. The mature state is signaled by a time to freeze signal sent as a switch-over signal from a transmitting location to each receiving location. These signals freeze and synchronize the AZL dictionaries at both locations, and starts a translation of the frozen AZL dictionary to a static SZL dictionary--at least at the transmitting location. The SZL dictionary is then used to compress records being transmitted. An index translation process is generates translation information to allow the receiving locations to decompress SZL indices into original characters. The AZL-to-SZL dictionary translation process re-organizes the frozen AZL to an SZL dictionary. The SZL process is used until either the end of the inputted sequence, or a time to unfreeze signal is generated. An SZL to AZL switch-over signal is generated in response to the time to unfreeze signal, which in turn signals a switch over back to the AZL process and invokes the saved frozen AZL dictionary to be used to until mature to on the current input data stream at which time the AZL is frozen and a switch-over signal is provided and a new SZL is generated.

Claims

1. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm, comprising the steps of:

inputting a sequence of records containing characters of data to an adaptive Ziv-Lemel (AZL) process at a transmitting location for compressing the data including;

generating an AZL dictionary in computer storage by inserting an entry therein at an assigned index for each inputted character string not found in the dictionary, detecting indicies in the dictionary for the inputted character strings in the sequence of records to represent compressed records; and

transmitting the compressed records to a receiving location;

generating a corresponding AZL dictionary at the receiving location from received indices of the transmitted compressed records;

freezing the AZL dictionary to maintain its current content at the transmitting location to provide an SZL (static Ziv-Lempel) dictionary when the AZL dictionary has been generated to a mature state to enable SZL processing; and

sending a switch-over signal by the transmitting location to the receiving location to indicate a synchronization point in the sequence of transmitted compressed records to enable the receiving location to freeze the corresponding AZL dictionary with an identical current content for enabling an SZL process to expand data by statically using the current content following the synchronization point in the transmitted compressed records.

2. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm, comprising the step of:

inputting a sequence of records containing characters of data to an adaptive Ziv-Lempel (AZL) process at a transmitting location for compressing the data including;

generating an AZL dictionary in computer storage by inserting an entry therein at an assigned index for each inputted character string not found in the dictionary, and detecting the indicies in the dictionary and transmitting to a receiving location the indices assigned to the inputted character strings in the sequence of records to represent transmitted compressed records;

generating a corresponding AZL dictionary at the receiving location from received indices of the transmitted compressed records;

freezing the AZL dictionary at the transmitting location to provide an SZL (static Ziv-Lempel) dictionary when the AZL dictionary has been generated to a mature state to enable SZL processing (which does not change the SZL dictionary);

sending a switch-over signal by the transmitting location to the receiving location to indicate a synchronization point in the sequence of transmitted compressed records to enable the receiving location to freeze the corresponding AZL dictionary for enabling an SZL process to expand data following the synchronization point in the transmitted compressed records; and

translating the frozen AZL dictionary in to a more processing-efficient corresponding SZL dictionary at the transmitting location by copying child character(s) of each extension character into an entry for the extension character to reduce storage accesses for child entries in the dictionary to speed up SZL processing for compressing subsequent records.

3. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 2, comprising the step of:

converting each index detected in the SZL dictionary into a corresponding index for a same character string in the frozen AZL dictionary, and transmitting converted indices to the receiving location as the transmitted compressed records to enable the frozen SZL dictionary to be used at the receiving location for expanding data in the compressed record.

4. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 2, comprising the step of:

storing the indices and the switch-over signal in a transmission buffer at the transmitting location in preparation for transmitting compressed data to the receiving location.

5. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 2, comprising the step of:

generating a switch-over signal as a predetermined value not used as an index in the frozen AZL dictionary.

6. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 2, comprising the step of:

completing operation by AZL and SZL processes upon detecting an end of a sequence of records being inputted for compression.

7. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 2, comprising the step of:

storing the frozen AZL dictionary in processor storage when a time to freeze signal is provided.

8. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 2, comprising the step of:

providing a time to unfreeze signal at the transmitting location by detecting that greater data compression is available by switching from the SZL process to the AZL process.

9. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 8, comprising the step of:

retrieving the stored AZL dictionary from storage at the transmitting location in response to a time to the unfreeze signal.

10. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 9, comprising the step of:

generating a switch-over signal at the transmitting location in response to a time to unfreeze signal.

11. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 10, comprising the steps of:

buffering the transmitted indices and the switch-over signal in a transmission buffer for transmission to each receiving location;

transmitting the switch-over signal to each receiving location to synchronize a switching to the AZL process using the frozen AZL dictionary at each receiving location with the switch-over at transmitting location; and

invoking the AZL process at each location.

12. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 11, comprising the step of:

inserting the switch-over signal into the transmitted compressed records to synchronize the switch-over operations at both the transmitting and receiving locations.

13. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 12, comprising the step of:

counting N number of characters from the beginning of the AZL process to generate a time to freeze signal when the count of N is reached at the transmitting location.

14. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 12, comprising the step of:

counting M number of characters from the beginning of the SZL process to generate a time to unfreeze signal when the count of M is reached at the transmitting location.

15. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 10, comprising the steps of:

counting the number of characters in an inputted record provided to the AZL process, counting the number of characters in a compressed record generated from the inputted record, and obtaining a record compression ratio by dividing the number of characters in the compressed record by the number of characters in the inputted record; and

generating a time to freeze signal when the record compression ratio is within a predetermined range of ratios for indicating a switch-over to the SZL process.

16. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 10, comprising the steps of:

counting the number of characters in an inputted record provided to the SZL process, counting the number of characters in a compressed record generated from the inputted record, and obtaining a record compression ratio by dividing the number of characters in the compressed record by the number of characters in the inputted record; and

generating a time to unfreeze signal when the record compression ratio is outside of a predetermined range of ratios for indicating a switch-over to the AZL process.

17. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 10, comprising the steps of:

counting the number of characters in an inputted record provided to the AZL process, counting the number of characters in a compressed record generated from the inputted record, and obtaining a record compression ratio by dividing the number of characters in the compressed record by the number of characters in the inputted record;

averaging the last R number of record compression ratios generated for the inputted sequence of records to obtain an average compression ratio; and

generating a time to freeze signal when the average compression ratio is within a predetermined range of ratios for indicating a switch-over to the SZL process.

18. A method of transmitting compressed data using a well-known Ziv-Lempel (ZL) compression/expansion algorithm as defined in claim 10, comprising the steps of:

counting the number of characters in an inputted record provided to the SZL process, counting the number of characters in a compressed record generated from the inputted record, and obtaining a record compression ratio by dividing the number of characters in the compressed record by the number of characters in the inputted record;

averaging the last R number of record compression ratios generated for the inputted sequence of records to obtain an average compression ratio; and

generating a time to unfreeze signal when the average compression ratio is outside of a predetermined range of ratios for indicating a switch-over to the AZL process.