Adaptive data compression system

• US 4,730,348 A
• Filed: 09/19/1986
• Issued: 03/08/1988
• Est. Priority Date: 09/19/1986
• Status: Expired due to Fees

• Current Assignee: Adaptive Computer Technologies
• Original Assignee: Adaptive Computer Technologies
• Inventors: MacCrisken, John E.
• Primary Examiner(s): Safourek, Benedict V.
• Application Number:
  US06/909,281
• Time in Patent Office: 536 Days
• Field of Search: 375/58, 375/122, 370/79, 370/82, 370/83, 370/94, 370/99, 370/118, 371/32, 371/33, 358/133, 358/138, 358/260, 340/347 DD, 382/43, 382/56
• US Class Current: 375/240
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence

Abstract

A data compression system for increasing the speed of data transmission system over a communication channel with a predefined data transmission rate. The system has two data compression units--one on each end of the channel, coupled to first and second data processing systems. Input data from either data processing system is encoded using a selected one of a plurality of encoding tables, each of which defines a method of encoding data using codes whose length varies inversely with the frequency of units of data in a predefined set of data. Whenever an analysis of the encoded data indicates that the data is not being efficiently compressed, the system invokes a table changer for selecting from among the encoding tables the one which minimizes the bit length of the encoded data for a preselected sample of the input data. If a new table is selected, a table change code which corresponds to the selected table is added to the encoded data. Also, a dynamic table builder builds a new encoding table to be including in the set of available encoding tables using a preselected portion of the previously encoded input data which an analysis of the encoded data indicates that a new encoding table will enhance compression. Each data compression unit includes a data decoder for decoding encoded data sent over the channel by the other unit. Thus the data decoder uses a set of decoding tables corresponding to the encoding tables, means for selecting a new table when a table change code is received, and means for building a new decoding table when it receives a table change code which indicates that the encoded data following the table change code was encoded using a new encoding table.

Claims

1. A data compression system for use in a data transmission system for transmitting data over a data communication channel between first and second data processing systems, comprising:

a first data compression unit coupling said first data processing system to said channel and a second data compression unit coupling said second data processing system to said channel, both data compression units including;

host receiving means for receiving host input data comprising sequences of binary data from the data processing system coupled to said data compression unit;

data encoding means for encoding said input data, including

a plurality of encoding tables, each said table defining a method of encoding data using codes whose length varies inversely with the frequency of units of data in a predefined set of data;

means for encoding said input data using a selected one of said encoding tables and thereby producing encoded data;

encoding table building means for building a new encoding table to be including in said plurality of encoding tables using a preselected portion of the previously encoded input data, including

means for determining when to perform said table building; and

encoding table change means for selecting from among said encoding tables the one which minimizes the bit length of the encoded data for a preselected sample of said input data, including

means for determining when to perform said table selection; and

means for adding to said encoded data a table change code which corresponds to said selected table, including means for indicating when said selected table is a new encoding table built by said table building means;

channel transmitting means for transmitting said encoded data over said channel;

channel receiving means for receiving encoded data;

data decoding means for decoding said encoded data, including

a plurality of decoding tables, each said decoding table defining a method of decoding data which was encoded using codes whose length varies inversely with the frequency of units of data in a predefined set of data;

means for decoding said encoded data using a selected one of said decoding tables and thereby producing decoded data;

decoding table building means for building a new decoding table to be including in said plurality of decoding tables using a preselected portion of previously decoded data, including

means for initiating the performance of said table building when said encoded data includes a table change code which indicates that the encoded data following said table change code was encoded using a new encoding table; and

decoding table change means for selecting a new decoding table from among said plurality of decoding tables when said encoded data includes a table change code;

host transmitting means for transmitting said decoded data to the data processing system coupled to said data compressing unit.

2. A data compression system as set forth in claim 1, wherein said means for determining when to perform said table selection in said encoding table change means includes

means for initiating the performance of said table selection if the bit length of said encoded data exceeds a predefined function of the bit length of said input data.

3. A data compression system, comprising:

encoding means for encoding input data received from a first data processing system in accordance with a predefined data compression encoding scheme;

wherein said first data processing system requires acknowledgement of receipt of predefined quantities of said input data before it will send more of said input data to said encoding means;

modem transmission means for transmitting the encoded representation of said input data generated by said encoding means over a communication channel to a second data processing system;

said modem transmission means being able to transmit one set of encoded data at the same time that said encoding means is receiving and encoding a different set of input data;

hold buffer means for storing said transmitted data;

buffer purging means for purging data from said hold buffer means when an acknowledgement of the receipt of said transmitted data is received from said communication channel;

retransmitting means for retransmitting over said communication channel said data in said hold buffer means if receipt of said transmitted data is not acknowledged; and

protocol emulation means for sending to said first data processing system an acknowledgement of the receipt of said input data before said encoded data is transmitted over said communication channel;

whereby the transmission of data from said first data processing system to said second data processing system is not delayed by said first data processing system waiting for an acknowledgement of receipt of said data to be sent by said second data processing system.

4. A data compression system, comprising:

input buffer means for storing input data received from a first data processing system;

encoding means for encoding said input data received from said first data processing system in accordance with a predefined data compression encoding scheme;

packet means for accumulating encoded data from said encoding means and generating packets, including packet sizing means for stopping the accumulation of encoded data for a packet (a) when the quantity of encoded data exceeds a defined packet limit, and (b) when all of said input data has been encoded by said encoding means, and no input data is received by said encoding means for a predefined length of time,

said packet means including means for adding a transmission error detection code to each said packet;

modem transmission means for transmitting said data packets of encoded data over a communication channel to a second data processing system at a predefined transmission rate, including means for transmitting a packet of encoded data at the same time that said encoding means is receiving and encoding input data;

wherein said second data processing system can accept decoded data at a predefined data reading rate; and

said packet sizing means includes means for stopping the accumulation of encoded data for a packet, when said modem transmission means is not transmitting a packet of data, and the lenght of time it will take for said second data processing system to accept the input data already encoded and accumulated by said encoding means and packet means, at said predefined data reading rate, is greater than the length of time it will take to transmit over said channel, at said predefined transmission rate, the input data stored in said input buffer but not yet encoded by said encoding means.

5. A data compression system as set forth in claim 4,

wherein said defined packet limit is increased by a predefined growth ratio each time the accumulation of data for a packet of data is ended by said packet means, until said defined packet limit reaches a predefined maximum packet size limit.

6. A data compression system as set forth in claim 5,

wherein said predefined growth ratio is equal to the ratio of said predefined data reading rate, measured in units of data per period of time, to said predefined data transmission rate multiplied by a number corresponding to an estimate of said system'"'"'s average data compression ratio.

7. A data compression system as set forth in claim 5, further including,

modem receiving means coupled to said communication channel for receiving data transmitted by said second data processing system over said communication channel, including acknowledgement data which indicates whether said second data processing system, using said transmission error detection code in each said packet, detected any transmission errors in said data packets sent to said second data processing system;

wherein said packet means includes means for decreasing said defined packet data limit in accordance with a predefined algorithm each time said data compression system receives acknowledgement data indicating that the data received by said second data transmission system included one or more transmission errors.

8. A data compression system, comprising:

encoding means for encoding input data received from a first data processing system in accordance with a selected character by character data compression encoding scheme;

modem transmission means for transmitting an encoded representation of said input data over a communication channel;

history buffer means for storing at least a portion of said input data which has been encoded by said encoding means;

character substitution encoding means for finding the longest string of data in said history buffer which matches said input data, and, if said longest string meets a predefined length requirement, representing said input data with a string substitution code including a pointer to the portion of said history buffer with said matching string, and a length indicator of the length of said matching string;

whereby

some of said transmitted data is encoded on a character by character basis and some of said transmitted data is encoded with a string substitution code; and

a receiver of said transmitted data can decode said transmitted data by maintaining a history buffer identical in content to said history buffer means in said data compression system, and by separately decoding said transmitted data in accordance with whether said data is encoded on a character by character basis or by a character substitution code.

9. A data compression system as set forth in claim 8, further including:

data receiving means for receiving encoded data and for decoding said received encoded data, including a receiving history buffer for storing at least a portion of said received data which has been decoded and means for decoding each said string substitution code in said received data into a string of data stored in the portion of said receiving history buffer specified by said pointer and length indicator in said string substitution code.

10. A data compression system as set forth in claim 8, said character substitution encoding means including:

hash table means for locating strings of length N in said history buffer including;

a hash function for generating a hash value when said hash function is applied to a string of length N, wherein N is an integer greater than one;

a hash table of pointers to each string of length N stored in said history buffer, wherein each said pointer is stored at a location in said hash table corresponding to said hash value of the corresponding string of length N; and

locating software means using said hash function and said hash table to locate every string in said history buffer starting with a specified string of length N.

11. A data compression system for encoding and transmitting data to a data decoding system that can simultaneously receive encoded data and decode previously received encoded data, comprising:

input buffer means for storing input data received from a data processing system;

encoding means for encoding said input data received from said data processing system in accordance with a predefined data compression encoding scheme;

packet means for accumulating encoded data from said encoding means and generating packets, including packet sizing means for stopping the accumulation of encoded data for a packet (a) when the quantity of encoded data exceeds a defined packet limit, and (b) when all of said input data has been encoded by said encoding means, and no input data is received by said encoding means for a predefined length of time;

modem transmission means for transmitting said data packets of encoded data over a communication channel to said data decoding system at a predefined transmission rate, including means for transmitting a packet of encoded data at the same time that said input buffer means and said encoding means are receiving and encoding input data;

wherein said packet sizing means further includes downsizing means for detecting the end of a data transmission and then decreasing the size of said packets generated by said packet means so that the data decoding system receiving said packets will simultaneously receive encoded packets of data from said end of said data transmission while decoding previously received data packets;

whereby the last datum at the end of said data transmission will be decoded sooner than if the size of said packets were not decreased.

12. A data compression system as set forth in claim 11, wherein said downsizing means successively decreases the size of each succeeding packet after detecting the end of a data transmission.

13. A data compression system as set forth in claim 12, wherein each packet at the end of said data transmission is sized so that the length of time it will take for said data decoding system to decode the data already encoded and accumulated by said encoding means and packet means is approximately equal to the length of time it will take to transmit over said channel the input data stored in said input buffer but not yet encoded by said encoding means.

14. A data compression system for encoding and transmitting data to a data decoding system that can simultaneously receive encoded data and decode previously received encoded data, comprising:

input buffer means for storing input data received from a data processing system;

encoding means for encoding said input data received from said data processing system in accordance with a predefined data compression encoding scheme;

packet means for accumulating encoded data from said encoding means and generating packets, including packet sizing means for stopping the accumulation of encoded data for a packet (a) when the quantity of encoded data exceeds a defined packet limit, and (b) when all of said input data has been encoded by said encoding means, and no input data is received by said encoding means for a predefined length of time;

modem transmission means for transmittng said data packets of encoded data over a communication channel to said data decoding system at a predefined transmission rate, including means for transmitting a packet of encoded data at the same time that said input buffer means and said encoding means are receiving and encoding input data;

wherein said defined packet limit has a predefined initial value and is increased by a predefined growth ratio each time the accumulation of data for a packet of data is ended by said packet means, until said defined packet limit reaches a predefined maximum packet size limit.

15. A data compression system as set forth in claim 14,

wherein said packet sizing means further includes downsizing means for detecting the end of a data transmission and then decreasing the size of said packets generated by said packet means so that the data decoding system receiving said packets will simultaneously receive encoded packets of data from said end of said data transmission while decoding previously received data packets;

whereby the last datum at the end of said data transmission will be decoded sooner than if the size of said packets were not decreased.

16. A data compression system as set forth in claim 14, wherein said downsizing means successively decreases the size of each succeeding packet after detecting the end of a data transmission so that each packet at the end of said data transmission is sized so that the length of time it will take for said data decoding system to decode the data already encoded and accumulated by said encoding means and packet means is approximately equal to the length of time it will take to transmit over said channel the input data stored in said input buffer but not yet encoded by said encoding means.

17. A data compression system as set forth in claim 14, wherein said encoding means includes:

history buffer means for storing at least a portion of said input data which has been encoded by said encoding means; and

character substitution encoding means for finding the longest string of data in said history buffer which matches said input data, and, when said longest string meets a predefined length requirement, representing said input data with a string substitution code including a pointer to the portion of said history buffer with said matching string, and a length indicator of the length of said matching string.