Method and apparatus for adaptive data compression exhibiting an improved compression efficiency

The present invention relates to a method and apparatus for compressing data in general, and in particular to a method and apparatus for performing adaptive data compression. Still more particularly, the present invention relates to a method and apparatus for providing improved data compression efficiency for an adaptive data compressor.

The type of data presented to a compression algorithm to be compressed can vary enormously. Therefore, most compression algorithms are made to be adaptive in nature in order to attain a better compression performance over a wide range of data types. Both the classical Lempel-Ziv 1 (LZ_1) and Lempel-Ziv 2 (LZ_2) compression algorithms embody this concept to a certain degree.

In the LZ_1 case, every byte processed is moved to a history-buffer that is initially empty. This history-buffer can be thought of as a byte-wide shift register, and once the history-buffer is completely filled, each new incoming data byte will displace the oldest data byte from the history-buffer. The current content within the history-buffer is compared with the incoming data to identify any matching strings or sequences of incoming data bytes that have occurred earlier, which still remain in the history-buffer. This incoming data sequence is then encoded in a more compact form, giving the starting point of the matching string within the history-buffer and the length of the matching string, and this forms the basis of the LZ_1 compression algorithm.

A LZ_1 decompressor maintains a history-buffer with an identical data history to the history-buffer within the LZ_1 compressor, and simply copies such strings as its output when decoding a reference.

In the LZ_2 case, a dictionary of data sequences is maintained, and references to these dictionary entries constitute the basis of the LZ_2 compression algorithm. It is not necessary to encode a length when the incoming data matches one of the dictionary entries because the length is also held in the dictionary. Hence, compressed output data from a LZ_2 compression algorithm usually consists of only a sequence of numbers, representing dictionary entries. Adaptive LZ_2 implementations continually add new dictionary entries based on the incoming data. As in the LZ_1 case, both LZ_2 compressor and LZ_2 decompressor start with and maintain an identical structure, although in the case of LZ_2, different management strategies are utilised when the dictionary becomes full.

Typically, a data stream to be compressed is frequently found to contain sequences of identical characters, commonly known as "runs." For example, executable code often contains significant runs of "00" characters. Also, code compilers often generate null data to initialise arrays or variables to a known state. Further, database software often allocates data fields with either all blank or all zero characters.

In addition, binary bitmap image data often contain a great deal of "whitespaces," typically "00" characters, representing eight pixels which are all blank. Otherwise, grey scale or colour image data, especially, which is encoded utilising one byte per pixel, may also contain long runs of identical data bytes.

These kinds of runs may lead to unnecessary and unproductive adaptations within a data compressor. Furthermore, because a history-buffer in LZ_1 or a dictionary in LZ_2 may easily be overflowed with identical data bytes from a run, it will take a while for the data compressor to resume its optimal compression ratio after the run. Consequently, it would be desirable to provide a method and apparatus to render better data compression efficiency to a data compressor such that the data compressor may be able to resume its optimal compression efficiency more rapidly after an occurrence of a run.

Abdat M. et al. discloses in "Adaptive limitation of the dictionary size in LZW data compression", Proceedings of 1995 IEEE International Symposium on Information Theory, page 18, 1995 a run-length encoding combined with the LZW algorithm. The run-length encoding eliminates the repeated symbols from the input data. The number N of repetitions must be greater than a pre-defined threshold in order to output a run-length code.

In view of the foregoing, it is therefore an object of the present invention to provide an improved method and apparatus for compressing data.

It is another object of the present invention to provide an improved method and apparatus for performing adaptive data compression.

It is yet another object of the present invention to provide an improved method and apparatus for providing better data compression efficiency for an adaptive data compressor.

In accordance with a method of the present invention, an uncompressed data stream is sent to a data compressor unit. But before sending the uncompressed data stream to the data compressor unit, and incoming data byte from the uncompressed data stream is first compared with the preceding data byte from the uncompressed data stream. A first counter value is incremented in response to a match between the incoming data byte and the preceding data byte. A second counter value is then incremented in response to subsequent matches between an incoming data byte and its preceding data byte after the first counter value has reached a preset value. The second counter value is finally sent to the data compressor unit at the completion of a run of the incoming data byte in substitution of a portion of the run, such that the data compressor unit can quickly resume its optimal compression ratio after an occurrence of the run within the uncompressed data stream.

The invention will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein: <ul id="ul0001" list-style="none"><li>Figure <b>1a</b> is a block diagram of a data compressor unit in which a preferred embodiment of the present invention may be incorporated;</li><li>Figure <b>1b</b> is a block diagram of a data decompressor unit in which a preferred embodiment of the present invention may be incorporated;</li><li>Figure <b>2</b> is a block diagram of a data pre-compressor for providing improved compression efficiency to a data compressor unit, in accordance with a preferred embodiment of the present invention;</li><li>Figure <b>3</b> is a state diagram of a method for providing improved data compression efficiency for a data pre-compressor, in accordance with a preferred embodiment of the present invention; and</li><li>Figure <b>4</b> is a state diagram of a method for providing improved data compression efficiency for a data post-compressor, in accordance with a preferred embodiment of the present invention.</li></ul>

The present invention may be implemented along with many types of adaptive data compression algorithms, such as Lempel-Ziv 1, Lempel-Ziv 2, etc. It will be understood by those skilled in the art that the present invention may be implemented in either hardware or software.

Referring now to the drawings and in particular to Figure <b>1a</b>, there is depicted a block diagram of a data compressor unit in which a preferred embodiment of the present invention may be incorporated. As shown, compressor unit <b>10</b> is coupled to a controller <b>11</b> and a random-access memory (RAM) or a content-addressable memory (CAM) <b>12</b>.

Any type of adaptive compression algorithms may be implemented within compressor unit <b>10</b>. Examples of adaptive compression algorithms include classical algorithms such as Lempel-Ziv 1 and Lempel-Ziv 2 that are well-known to those skilled in the art, or a more contemporary algorithm such as Adaptive Loss less Data Compression (ALDC) described in "QIC Development Standard QIC-154," Revision A, 10 Mar 94, Quarter-Inch Cartridge Drive Standards, Inc of. All data structures associated with the chosen compression algorithm, such as a history-buffer for Lempel-Ziv 1 or a dictionary for Lempel-Ziv 2, are maintained within RAM/CAM <b>12.</b> As such, the optimal size of RAM/CAM <b>12</b> depends on the type of compression algorithm utilised within compressor unit <b>10.</b> During operation, an uncompressed data stream is first received by compressor unit <b>10</b> from a data source <b>13.</b> After data-encoding, a compressed data stream is then transmitted to a data sink <b>14</b>.

Referring now to Figure <b>1b</b>, there is depicted a block diagram of a data decompressor unit in which a preferred embodiment of the present invention may be incorporated. As shown, decompressor unit <b>15</b> is coupled to a controller <b>16</b> and a RAM <b>17.</b> Similar to RAM <b>12,</b> all data structures for decompressor unit <b>15</b> are maintained within RAM <b>17</b> and the size of RAM <b>17</b> depends on the type of compression algorithm utilised within compressor unit <b>10.</b>

During operation, a compressed data stream is first received by decompressor unit <b>15</b> from data source <b>19</b>. After data-decoding, an uncompressed data stream will then be transmitted from decompressor unit <b>15</b> to a data sink <b>18</b>.

With reference now to Figure <b>2,</b> there is illustrated a block diagram of a data pre-compressor for providing improved compression efficiency to compressor unit <b>10</b> of Figure <b>1a</b>, in accordance with a preferred embodiment of the present invention. Pre-compressor unit <b>20</b> is preferably coupled between data source <b>13</b> and compressor unit <b>10.</b> As shown, pre-compressor unit <b>20</b> includes a first register <b>22,</b> a second register <b>23,</b> a comparator <b>24,</b> a first counter <b>25,</b> a second counter <b>26,</b> and a multiplexor <b>21.</b>

During operation, each incoming data byte from an uncompressed data stream is first stored in first register <b>22.</b>

This incoming data byte will be sent to second register <b>23</b> upon the arrival of another incoming data byte from the uncompressed data stream. Hence, second register <b>23</b> retains the value of a previous (<i>i. e.</i> immediately preceding) data byte from the uncompressed data stream. The incoming data byte stored in first register <b>22</b> is then compared with the previous data byte stored in second register <b>23</b> utilising comparator <b>24.</b> First counter <b>25</b> is initially reset to zero, but first counter <b>25</b> will be incremented each time there is a match between the data byte stored in first register <b>22</b> and the data byte stored in second register <b>23,</b> indicated by comparator <b>24.</b>

Otherwise, first counter <b>25</b> will be reset again if there is a mismatch between the data byte stored in first register <b>22</b> and the data byte stored in second register <b>23.</b> Also, the incoming data byte from the uncompressed data stream will be sent to compressor unit <b>10</b> via multiplexor <b>21</b> if there is a mismatch between the data byte stored in first register <b>22</b> (<i>i</i>.<i>e</i>. the incoming data byte) and the data byte stored in second register <b>23.</b>

There is a preset value associated with first counter <b>25,</b> and once this preset value is reached, any additional incoming data byte from the uncompressed data stream that still matches with its previous data byte from the uncompressed data stream will be discarded.

This signifies an occurrence of a run condition within the uncompressed data stream. At this point, second counter <b>26</b> will be incremented instead for any matching condition between an incoming data byte and its previous data byte. When a mismatch finally occurs between an incoming data byte and its previous data byte, the accumulated count stored within second counter <b>26</b> will be passed on to compressor unit <b>10</b>, followed by the mis-matching incoming data byte.

The preset value for first counter <b>25</b> should be fairly small and a value of three, corresponding to a run length of four, is found to be quite optimal for most uncompressed data streams. Hence, all data bytes from an uncompressed data stream containing runs of less than the preset value of four will simply be passed on to compressor unit <b>10</b> for further processing according to the compressor algorithm utilised therein.

Because most adaptive compression algorithms are character-based, counters <b>25, 26</b> should preferably be of the same size as a character, typically eight bits long. If the run is exactly the same length as the preset value, then a count value of "00" is passed on to compressor unit <b>10.</b> If the run is one byte longer than the preset value, a count of "01" is passed on to compressor unit <b>10,</b> and so on. If 8-bit characters are in use, the highest value is utilised as a count continuation character.

Referring now to Figure <b>3,</b> there is illustrated a state diagram of a method for providing improved data compression efficiency for a data pre-compressor, in accordance with a preferred embodiment of the present invention. Starting at state (00), Available_Flag, First_Counter, Second_Counter are reset to zero, then go to state (01). In state (01), the pre-compressor waits for an input Data_Byte request. In state (02), a determination is made as to whether or not Available_Flag is set to 0; if yes, then go to state (04); if no, then go to state (03).

In state (03), a previously saved new Data_Byte is delivered to the Compressor. In state (04), a Data_Byte is fetched from the data source, then go to state (05). In state (05), a determination is made as to whether First_Counter is at Preset_ Limit; if yes, then go to state (08); if no, then go to state (07).

In state (06), a determination is made as to whether or not the new Data_Byte is identical to the Previous_Byte; if yes, then go to state (08); if no, then go to state (07).

In state (07), the First_Counter is reset to zero, then go to state (09). In state (08), the First_Counter is incremented by 1, then go to state (09). In state (10), the new Data_Byte is delivered to the Compressor, then go to state (01).

In state (10), a determination is made as to whether or not the new Data_Byte is identical to the Previous_Byte; if yes, then go to state (13); if no, then go to state (11). In state (12), the Available_Flag is set to 1, then go to state (01).

In state (13), the Second_Counter is incremented by 1, then go to state (14). In state (14), a determination is made as to whether or not the Second_Counter is at its maximum value; if yes, then go to state (15); if no, then go to state (04).

In state (15), the Second_Counter value is delivered to the Compressor, then go to state (16). In state (16), the Second_Counter value is reset to "01," then go to state (01).

With reference now to Figure <b>4</b>, there is illustrated a high-level state diagram for the corresponding data post-compressor, in accordance with a preferred embodiment of the present invention. Starting at state (00), Extension_Flag, First_Counter, Second_Counter are reset to zero, then go to state (01).

In state (01), awaiting output of a new Data_Byte from the decompressor. In state (02), a determination is made as to whether or not Extension_Flag is set to 0; if yes, then go to state (13); if no, then go to state (03).

In state (03), a new Data_Byte value is loaded to the Second_Counter. In state (04), a determination is made as to whether or not the Second_Counter is at its maximum value; if yes, then go to state (09); if no, then go to state (05).

In state (05), the Extension_Flag is reset to zero, then go to state (06). In state (06), a determination is made as to whether or not the Second_Counter value is at 0; if yes, then go to state (00); if no, then go to state (07). In state (08), the previous Data_Byte is delivered to the output, then go to state (08). In state (08), the Second_Counter is decremented by 1, then go to state (06).

In state (09), the Extension_Flag is set to 1, then go to state (10). In state (10), the previous Data_Byte is delivered to the output, then go to state (11). In state (11), the Second_Counter is decremented by 1, then go to state (12). In state (12), a determination is made as to whether or not the Second_Counter value is greater than 1; if yes, then go to state (10); if no, then go to state (01).

In state (13), a determination is made as to whether or not the First_Counter is at a Preset_Limit; if yes, then go to state (03); if no, then go to state (14).

In state (14), the new Data_Byte value is delivered to the output, then go to state (15). In state (15), a determination is made as to whether or not the new Data_Byte is identical to the Previous_Byte; if yes, then go to state (17); if no, then go to state (16). In state (16), the First_Counter value is reset to zero, then go to state (01). In state (17), the First_Counter is incremented by 1, then go to state (01).

Table I is an example illustrating the results from pre-compressor unit 20 based on the incoming data stream, in accordance with a preferred embodiment of the present invention. In this example, the preset value is set to three and an 8-bit symbol (one byte) is utilised. <tables id="tabl0001" num="0001"><table frame="none"><title><b>Table I</b></title><tgroup cols="2" colsep="0" rowsep="1"><colspec colnum="1" colname="col1" colwidth="45mm" colsep="0" /><colspec colnum="2" colname="col2" colwidth="42mm" colsep="0" /><thead><row><entry namest="col1" nameend="col1" align="center" valign="top">INPUT DATA STREAM</entry><entry namest="col2" nameend="col2" align="center" valign="top">INPUT TO COMPRESSOR</entry></row></thead><tbody><row rowsep="0"><entry namest="col1" nameend="col1" align="left" valign="top">C3 02 02 02 A7</entry><entry namest="col2" nameend="col2" align="left" valign="top">C3 02 02 20 A7</entry></row><row rowsep="0"><entry namest="col1" nameend="col1" align="left" valign="top">96 FF FF FF FF A2</entry><entry namest="col2" nameend="col2" align="left" valign="top">96 FF FF FF FF 00 A2</entry></row><row rowsep="0"><entry namest="col1" nameend="col1" align="left" valign="top">31 30 30 30 30 30 39</entry><entry namest="col2" nameend="col2" align="left" valign="top">31 30 30 30 30 01 39</entry></row><row rowsep="0"><entry namest="col1" nameend="col1" align="left" valign="top">OA 40 .. (a run of 9) .. 40 C3</entry><entry namest="col2" nameend="col2" align="left" valign="top">OA 40 40 40 40 05 C3</entry></row><row rowsep="0"><entry namest="col1" nameend="col1" align="left" valign="top">64 00 .. (a run of 258) .. 00 32</entry><entry namest="col2" nameend="col2" align="left" valign="top">64 00 00 00 00 FE 32</entry></row><row rowsep="0"><entry namest="col1" nameend="col1" align="left" valign="top">9B 00 .. (a run of 259) .. 00 8D</entry><entry namest="col2" nameend="col2" align="left" valign="top">9B 00 00 00 00 FF 00 8D</entry></row><row rowsep="0"><entry namest="col1" nameend="col1" align="left" valign="top">20 40 .. (a run of 260) .. 40 20</entry><entry namest="col2" nameend="col2" align="left" valign="top">20 40 40 40 40 FF 01 20</entry></row></tbody></tgroup></table></tables>

As has been described, the present invention provides a method and apparatus for providing improved data compression efficiency to a compressor unit.

Although a compressor unit is utilised throughout the entire disclosure for the purpose of illustration, it is understood by those skilled in the art that a pre-compressor as described must also utilise a corresponding post-decompressor. Such post-decompressor is preferably coupled between decompressor unit <b>15</b> and data sink <b>18</b> of Figure <b>1b</b>.

A post-decompressor performs the inverse operation of a pre-compressor. Each data byte output from a de-compressor unit is compared to its previous data byte and a counter is incremented or is reset. If the counter reaches the preset value, then the next data byte is treated as a count representing how many additional copies of the last value output constitute the continuation of the run, and must be copied out before decoding any more compressed data bytes.

For both a pre-compressor and a post-decompressor, the maximum count symbol value is utilised to denote a count of this value but that this count is continued on the next symbol, which must be processed according to the same rule. The use of count continuation characters in this manner permit runs of any length to be encoded, with a penalty of one symbol for runs of length exactly equal to the preset threshold value.

In terms of hardware, the present invention only requires an extra register to hold the previous data symbol, a comparator, and a counter, along with a small amount of control logic. In fact, for a Content-Addressable Memory (CAM) based compressor, the register already exists in hardware, but in any event, the extra silicon area utilised to implement the present invention is negligible.

In addition, the present invention can be applied to any kind of compression algorithms, and clearly can provide considerable compression in and of itself for long runs of data (in excess of 250:1 for 8-bit symbols). In the case of general-purpose adaptive compression algorithms, this is an important advantage, because such compression algorithms generally adapt without regard to whether or not a stream of incoming data should be utilised to adapt the compression algorithm. An Lempel-Ziv 1 algorithm, for example, can only achieve a maximum compression ratio of about 90:1 for a long run of identical data.

While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the scope of the invention as defined in the claims.