Abstract:
A data compression and decompression method and apparatus utilizing a sliding window dictionary in combination with an adaptive dictionary. Incoming data moves through a buffer and is compared against both the sliding window dictionary and the adaptive dictionary, and matched data is replaced with a pointer to the dictionary entry. All incoming data is entered into the sliding window dictionary, but only data which satisfies certain criteria is entered into the adaptive dictionary.

Description:
This application is a continuation-in-part of application no. 679,530 filed Apr. 2, 1991 by William D. Miller, Gary L. Harrington, Larry Fullerton, E. J. Weldon, Jr. and Christopher M. Bellman for Solid-State RAM Data Storage for Virtual Memory Computer Using Fixed-Size Swap pages, which is a continuation-in-part of application Ser. No. 627,722 filed Dec. 14, 1990 abandoned by William D. Miller, Gary L. Harrington and Lawrence M. Fullerton for Storage of Compressed Data on Random Access Storage Devices, both of which are assigned to CERAM, Inc., the assignee of the present invention. The disclosures of the parent applications are hereby incorporated herein by this reference. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates to the field of digital data storage and retrieval, and more particularly to the field of lossless data compression and data decompression in the storage and retrieval of data using adaptive dictionaries. The invention is especially useful in the storage of data in solid state memories. 
     BACKGROUND OF THE INVENTION 
     Data compression is the reversible encoding of data into a more compact expression which permits more efficient storage and transmission of the data. Some data compressing procedures result in the loss of some of the data upon uncompression; when the data is compressed and then uncompressed, it no longer matches the original data exactly. These so-called &#34;lossy&#34; compression schemes are commonly used for video image data or audio data, where some loss of information can be tolerated or perhaps not even noticed. For example, lossy compression is used extensively in video image compression for multimedia computing and also high-definition television. Although lossy compression loses some of the data, it is highly effective in achieving compression, with compression ratios of 20-to-1 and up to 200-to-1. 
     Other compression algorithms are &#34;lossless&#34; in that the data can be compressed and then uncompressed, and the resulting output matches the original input exactly. Lossless compression is the only acceptable procedure for compressing information or program data in which losses are not tolerable. Such information and program data constitute the great majority of information and program data outside of the field of video and audio applications. The demands for lossless compression usually result in much lower compression ratios as compared to lossy compression, with ratios of 1.5-to-1 and up to 10-to-1 being typical. The present invention is concerned with lossless data compression. 
     Most data compression systems used today rely on the fact that sets of data are typically repetitious in limited ways. For example, data such as ASCII files contain byte streams representing alphanumeric symbols, words and phrases that appear repeatedly in the text. By replacing the byte streams with abbreviated byte streams, the data can be compressed considerably. This is generally accomplished using a &#34;dictionary&#34; containing the abbreviations for the byte streams that are to be compressed. The value of using a fixed dictionary is diminished, however, as the size of the dictionary increases, because the savings achieved in compressing the data becomes offset by the expense of comparing the data to a large dictionary. Therefore, the ideal dictionary is limited in scope to contain only those byte streams that are seen often enough in the data to justify the comparison with the dictionary. 
     Early theoretical work on the use of dictionary compression encoding was done by Jacob Ziv and Abraham Lempel and is described in their article &#34;On Complexity of Finite Sequences&#34;, IEEE Transactions on Information Theory, 22:1 (1976) 75-81. The Ziv and Lempel work developed the idea of &#34;adaptive dictionaries&#34; in which the content of the dictionary and hence the compression scheme for future encoding is based on the recent data output. Therefore, the dictionary is adaptive to the data itself. The many compression techniques based on the theoretical work of Ziv and Lempel are commonly referred to as Lempel-Ziv coding or LZ coding, and the essence of those techniques is that byte streams are replaced with pointers to where the byte streams occurred earlier. 
     An example of LZ coding is presented in an article by J. A. Storer entitled &#34;Textual Substitution Techniques for Data Compression&#34;, Combinational Algorithms on Words (edited by A. Apostolico and Z. Galil) Springer-Verlag, Berlin, p. 120-121, 1985. In the Storer technique, an encoder and decoder are provided with a fixed amount of memory for use as a dictionary containing a number of dictionary entries. Each entry has a unique pointer associated with it. As data is received, the encoder finds the longest string of characters in the data that matches an entry in the dictionary, transmits the pointer associated with the matched entry in place of the string of characters, updates the dictionary, and if the dictionary is full then deletes one of the entries. 
     Other examples of LZ coding are found in U.S. Pat. Nos. 4,876,541 by Storer (and the references discussed and cited therein), 5,003,307 by Whiting et al., 4,847,619 by Kato et al., and 4,701,745 by Waterworth. 
     One of the principal variables in LZ coding which tends to distinguish the many variations of that technique from one another, is the way in which the dictionary is established and updated. Some techniques utilize a sliding window dictionary in which the incoming data are compared against the data in a window sliding over a fixed number N of previous bytes of data. Thus the dictionary in this approach is actually a sequential portion of the text itself. This is sometimes called LZ 77 or LZ 1 coding. 
     LZ 77 coding can give good data compression provided that the dictionary window is long enough, such as 8K bytes. Common words and fragments will often be matched wholly or partially by a sliding window dictionary of that length. With respect to less common words and fragments, the sliding window dictionary takes advantage of the fact that these less common words and fragments are often concentrated in a single portion of the text. Unusual words are often used repeatedly in a brief portion of text to discuss a single concept, rather than scattered through a long text. 
     The principle disadvantage to sliding window dictionaries as used in LZ 77 coding is not that they are ineffective in achieving good compression, for they are indeed effective in achieving good compression. The principal disadvantage to sliding window dictionaries is that they require a large and constant amount of time for performing the encoding because of the relatively large window length. The encoding speed can be increased by using various known data structures, but that also increases the required memory. LZ 77 coding is relatively fast at the decoding step, however, and so it is suitable for applications which require only one encoding on a fast computer with large amounts of memory and multiple decoding, as commonly is the case with on-line help files, and electronic books. 
     Other techniques in LZ coding replace the sliding window dictionary with a true adaptive dictionary which accumulates phrases found in the incoming data under the broad assumption that phrases that occur once are likely to occur again. By using known data structure and hashing techniques, the comparison of the incoming data to the entries in the adaptive dictionary can be done relatively quickly. Adaptive dictionaries also have an advantage over sliding window dictionaries in that the adaptive dictionaries may include entries generated much earlier than the current incoming data, while the entries in a sliding window dictionaries are limited to the span of the window. The main drawback to adaptive dictionaries is that once the limited adaptive dictionary is full, no further entries can be made without deleting some of the existing entries. While the dictionary can be made very large so that it accommodates a large number of entries before being filled, this increases memory requirements and comparison times. 
     SUMMARY OF THE INVENTION 
     The present invention is a very high speed lossless data compression and decompression system using a sliding window dictionary simultaneously with an adaptive dictionary. In the preferred embodiment, there is a 36-byte lookahead buffer, a 256-byte sliding window dictionary, and a 32-byte adaptive dictionary. The adaptive dictionary accepts data from the input stream at the same time as the sliding window dictionary. 
     In the preferred embodiment, all input data flows into and out of the sliding window dictionary, such that the compression of the input data with the sliding window dictionary involves comparison with only a fixed length of data immediately preceding the compared input data. For any input data that form a multiple-byte match with entries in the sliding window, a pointer is substituted for the matched byte-string. Any bytes of input data that does not form part of a multiple-byte match with the sliding window, are compared against the entries in the adaptive dictionary. If a match is found with the entries in the adaptive dictionary, then a pointer is substituted for the matched data. If no match is found in the adaptive dictionary, then the data is entered into the adaptive dictionary with the rationale that the data may occur again in the incoming data and then form a match against the adaptive dictionary. When the adaptive dictionary is full, old entries are deleted to make room for the new ones. 
     Accordingly, it is an object of the present invention to provide a lossless data compression coding system utilizing both a sliding window dictionary and adaptive dictionary in combination whereby data compression can be accomplished quickly and with a minimum amount of memory. 
     It is a further object of the invention to provide a system in which entries are made in the adaptive dictionary only if they satisfy particular criteria, such as being data no more than a fixed number of bytes in length and not being already in the sliding window dictionary. 
     A further object of the invention is to provide a system for updating an adaptive dictionary to accommodate new entries by deleting existing entries as necessary to accommodate new entries. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a diagrammatic flow chart of the compression process of the present invention, which overlaps with FIG. 2. 
     FIG. 2 is a diagrammatic flow chart of the compression process of the present invention, which overlaps with FIG. 1. 
     FIG. 3 is a diagrammatic flow chart of the decompression process of the present invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     A block diagram of the data compression system of the present invention is shown in FIGS. 1 and 2. The system includes a lookahead buffer 18 in the form of a linear array of bytes from an oldest byte to a newest byte which receives the incoming data. The lookahead buffer 18 is actually a single byte in length, but can be visualized as being 36-bytes long since that is the number of bytes that can be matched against the sliding window 20 in a single string match in the manner described below. The incoming data is clocked into the input end of the buffer 18 and out of the output end sequentially, one byte per clock cycle. The sliding window dictionary 20 -- sometimes referred to as a first comparison window herein -- is also a linear array of bytes from an oldest byte to a newest byte. The sliding window dictionary 20 receives the output of the lookahead buffer a byte at a time, so that the input data moves sequentially a byte at a time through the lookahead buffer and then through the sliding window buffer. In the preferred embodiment, the sliding window 20 is 256 bytes long, although it will be appreciated that windows of other lengths are possible as well. 
     If the byte in the lookahead buffer 18 matches a byte in the sliding window dictionary 20, a counter 22 is incremented to indicate a match length of one. Regardless of whether or not there was a match, the byte shifts through the lookahead buffer and into the sliding window dictionary 20. There is a separate sliding window byte comparator 24 for each of the 256 bytes in the sliding window dictionary 20. For each byte in the window 20 that matches the byte in the lookahead buffer 18, the flip flop 28 is set to indicate a match at that window location. As more bytes are shifted into the lookahead buffer 18 and compared against the sliding window 20, the flip flop 28 keeps track of which bytes in the window 20 still match the lookahead buffer 18. The matched string can be as long as the length of the lookahead buffer, namely 36 bytes. If any input byte does not match the sliding window 20, the output of the sliding window byte comparator 24 for that position goes into AND gate 32 and causes flip flop 28 for that position to get turned off. When flip flop 28 gets turned off, the feedback from the output of flip flop 28 back to the upper input of AND gate 32 will ensure that the flip flop will stay off during the remainder of the string match operation, indicating that there is no longer a string match at that position. If the input byte still matches at a position it matched before, AND gate 32 causes the flip flop 28 for that position to continue being set, indicating a multiple-byte match at that position. 
     Input bytes are continually compared against data in the sliding window dictionary 20 until the output of OR gate 34 goes off, indicating the end of the string match. When the output of OR gate 34 goes off, and before the next clock edge, the outputs of all flip flops 28 go into a priority encoder to get a pointer to the position in the window of the longest match just before the non-matching byte came into the lookahead buffer 18. Then on the next clock edge after OR gate 34 went off indicating the end of the string match, the encoded position from encoder 40 and the match count from counter 22 are latched into the output stage of the compressor, shown as bit packer 50, through the multiplexer 52 according to the method of encoding explained below. Simultaneously, the `off` output of OR gate 34 goes through gate 60 to multiplexer 62, causing the raw, ungated output of byte comparator 24 to be clocked into flip flop 28 on the same clock edge that latched the encoded string match output. By bypassing gate 32, multiplexer 62 causes flip flop 28 to latch a new byte comparison result which does not depend on the previous state of the flip flop which is at that time the final result of the previous string match. This starts a new string match with zero delay; a new string match process starts on the same clock edge that latches the results of the previous string match. 
     At the start of a new string match, the adaptive dictionary 70 -- sometimes referred to as a second comparison window herein -- is checked for a match against the byte in lookahead buffer 18. As in the case of the buffer 18 and the sliding window dictionary 20, the adaptive dictionary 70 is a linear array of bytes from an oldest byte to a newest byte. The comparison is accomplished using the adaptive dictionary comparator 71 which has a separate compare circuit for each of the 32 bytes in the adaptive window. If there is a byte match somewhere in adaptive dictionary 70, then the match is encoded in encoder 72 with the compact format explained below. The output encoding of the single-byte match against adaptive dictionary 70 is latched into the output stage of the compressor, shown as bit packer 50, through multiplexer 52 on the next rising edge of the clock. 
     The byte comparisons of lookahead byte 18 against all bytes in sliding window dictionary 20 occur simultaneously with the byte comparisons of lookahead byte 18 against all bytes in adaptive dictionary 70. The output results of the comparisons against the two separate dictionaries go to output multiplexer via 0R gates 34 and 74, allowing the output stage of the compressor to select the appropriate compression output based on where the match occurred. The selection of encoded output from either dictionary can be done on a clock-by-clock basis, so that there is zero delay switching between dictionaries to always give the best compression ratio possible based on the two separate, side-by-side dictionaries. A multiple-byte string match against sliding window dictionary 20 always has priority over a single-byte match in adaptive dictionary 78, since a multiple-byte match will always give a better compression ratio. Single-byte matches against the small adaptive dictionary have priority over single-byte matches against the large sliding window dictionary because of the smaller, more compact encoding of adaptive dictionary matches. 
     The output encoding depends on whether the match of the incoming data is with the sliding window dictionary 20 or with the adaptive dictionary 70. If the data is uncompressible, the coding will indicate a raw 8 bit byte, as in: 
     
         Obbbbbbbb 
    
     If the incoming data has been matched with the 32-byte adaptive dictionary, then the encoding will be:=ps 
     
         10&lt;pointer&gt; 
    
     The &#34;10&#34; indicates the adaptive dictionary while the pointer is a 5-bit binary number pointing to one of the 32-byte entries in the adaptive dictionary. 
     If the data has been matched with the 256-byte sliding window dictionary instead of the adaptive dictionary, then the encoding will be: 
     
         11&lt;pointer&gt;&lt;length&gt; 
    
     The &#34;11&#34; indicates the sliding window dictionary, the pointer is an 8-bit binary number pointing to the byte in the 256-byte sliding window dictionary at which the match begins, and the length indicates the length of the match in bytes. In a preferred embodiment, the length is indicated in a modified binary code to save bits, according to the following table: 
     
         ______________________________________  01             2 bytes  10             3 bytes  11             4 bytes  0000000        5 bytes  0000001        6 bytes  0000010        7 bytes  0000011        8 bytes  0000100        9 bytes  0000101       10 bytes  0000110       11 bytes  0000111       12 bytes  0001000       13 bytes  0001001       14 bytes  0001010       15 bytes  0001011       16 bytes  0001100       17 bytes  0001101       18 bytes  0001110       19 bytes  0001111       20 bytes  0010000       21 bytes  0010001       22 bytes  0010010       23 bytes  0010011       24 bytes  0010100       25 bytes  0010101       26 bytes  0010110       27 bytes  0010111       28 bytes  0011000       29 bytes  0011001       30 bytes  0011010       31 bytes  0011011       32 bytes  0011100       33 bytes  0011101       34 bytes  0011110       35 bytes  0011111       36 bytes______________________________________ 
    
     Instead of the comparators 24 and 71 described above, in which there is a separate compare circuit for each byte of the sliding window dictionary and adaptive dictionary, respectively, and only one byte of the lookahead buffer 18 is compared at a time, a large number of bytes of the lookahead buffer 18 could be compared at a given time in a &#34;gang compare&#34; cycle. For example, at least in theory, all 36-bytes of the lookahead buffer 18 could be compared. Also, the number of bytes in the lookahead buffer 18 could be increased or decreased to allow longer or shorter string matches with appropriate adjustment of the length of the output pointer symbols. Similarly, the length of the sliding window dictionary 20 or adaptive dictionary could be increased or decreased with appropriate changes to the memory and the length of the output pointers. 
     The dictionaries 20 and 70 are updated in the following manner. As already mentioned, all input bytes are clocked through the sliding window dictionary 20 on a byte-by-byte basis. Therefore, the sliding window dictionary is updated by a single byte shift each clock period. In contrast, not all input bytes are entered into the adaptive dictionary 70. Adaptive dictionary 70 can be made smaller than sliding window dictionary 20 and still give a good compare hit rate against input bytes because adaptive dictionary 70 is selective in which input bytes it allows to shift in. Only input bytes which do not become part of a multiple-byte match against sliding window dictionary 20, and which are not already in adaptive dictionary 70, are allowed to shift into the adaptive dictionary. The idea is that if a byte is not part of a multiple-byte match against the sliding window, it is put into the adaptive dictionary (if it is not already there) because there is a very good chance that that byte value may occur again in the input stream and again not fit into a multiple-byte match. In that case, it will match against the small adaptive dictionary and give a small amount of compression. Prior art compression algorithms put out a no-compress encoding for an input byte that is not part of a multiple-byte match; in contrast with the present invention, a no-compress encoding will give a small amount of expansion instead of compression. When the dictionaries are full, old entries must be deleted to make room for new entries. Each time there is a new entry, the oldest entry is deleted and the remaining entries are shifted one byte along the linear array to open a byte position for the new entry. 
     The current invention, with its two side-by-side dictionaries gives better compression over a range of various types of computer data, whereas prior art data compressors with a single dictionary give good compression on some types of data and poor or not-so-good compression on other types of data. 
     Decompression of previously-compressed data is simple, straightforward, and fast, as shown in FIG. 3. Compressed data 81 is parsed in parser 80, which sends a pointer address to either selector 82 to select 1 of 256 bytes from the sliding window dictionary, or to selector 84 to select 1 of 32 bytes from the separate adaptive dictionary. Selector 86 would then pass one of the two selected dictionary bytes on the decompression output 90, which is where the decompressed data is available for the computer system that needs it. The uncompressed byte would also shift into the sliding window dictionary 20 to recreate the same dictionary that was created during compression. For a multiple-byte match, as the uncompressed data entering the sliding window dictionary 20 shifts the contents of the sliding window dictionary, each byte of the string match that is being uncompressed can be read out at the same pointer address within the sliding dictionary. 
     If the incoming word of previously-compressed data is a raw byte of data as described by the raw bit format discussed previously, then parser 80 would pass the raw byte on to selector 86 which would pass the raw byte on to the output 90. The raw byte would also shift into a sliding window dictionary 20. Only uncompressed data which comes from the &#34;raw&#34; encoding format would shift into the separate adaptive dictionary 70, to recreate an exact copy of the adaptive dictionary that was created when the data was originally compressed.