Data compression method using textual substitution
FIELD OF THE INVENTION 
     This invention relates generally to a method for compressing and decompressing digital data, and more particularly, to an adaptive method of compression and decompression which utilizes recursion. 
     BACKGROUND OF THE INVENTION 
     Data compression systems encode a stream of digital data signals into compressed digital code signals and decode the compressed code signals back into the original data. Typically, a data compression system is used to encode data for its transmission to a remote location whereby the compression of the data reduces the amount of data transmitted. 
     Data compression algorithms may be divided into various categories, based on the techniques employed and the intended application of the algorithm. Some algorithms require that all of the input data (or a large block of data) be present for analysis prior to the compression taking place. Other algorithms can accept an input stream of uncompressed data and generate an output stream of compressed data without the need to buffer large quantities of data. 
     Accordingly, the latter type of compression algorithm is ideally suited to modems and other data communications applications which operate on a serial data stream. 
     A desirable feature of a data compression system is adaptability. A system&#39;s adaptability depends on its ability to efficiently compress input data that varies over a range of conditions. A second desirable feature is the storing of character strings. Character strings in the input data which match known character strings may be represented in the transmission of data by a single token rather than the entire string of characters. 
     SUMMARY OF THE INVENTION 
     A presently preferred embodiment of the present invention provides a method of compressing input characters represented by digital data, and decompressing said compressed data to produce the original input characters An input substitution table and an output substitution table are formed by storing an identical set of arbitrary character tokens of a fixed length in each of the tables wherein each table entry has a unique identification and a first and second token data field associated with it. The token data fields are representative of either a character token or substitution code token. 
     Input characters are loaded into an input register, one at a time, while ensuring that at least two tokens are contained in the input register before attempting a data compression. Pairs of tokens in the input register are replaced with a substitution code token from the input substitution table when said substitution code represents a substitution table entry having a first and second token which match the tokens in the input register. Substitution is repeated until no more character pairs in the input register can be replaced by substitution code tokens. 
     All of the tokens residing in the input resister, except for the token most recently loaded or substituted for, are transmitted as output tokens to the decompression mechanism. The entries in the input substitution table are then updated by locating a substitution entry in the table which is not referenced by any other substitution table entry and then by replacing the first and second tokens of the located substitution table entry with the two most recently transmitted output tokens. 
     Meanwhile, the transmitted output tokens are loaded into a token field of an output register one at a time. The output substitution table is updated based on the received output tokens by locating a substitution entry which is not referenced by any other substitution table entry and by replacing the first and second tokens of the located substitution table entry with the two output tokens most recently received by the output register. 
     If the token most recently loaded into the output register is a substitution code token then it is expanded to its component character tokens according to the entries in the output substitution table. The character tokens hereby expanded, along with the tokens received by the output register as character tokens are output as output characters These output characters are identical to the input characters. 
     The steps loading the transmitted tokens, updating the output substitution table, expanding substitution code tokens and writing character tokens for each of the output tokens transmitted from the input register are repeated until each of the received output tokens are processed. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other features and advantages of the present invention will be better understood by reference to the following detailed description when considered in connection with the accompanying drawings wherein: 
     FIG. 1 is a block diagram illustrating the flow of data in the compression and decompression procedures; 
     FIG. 2 is a block diagram illustrating the fields of an exemplary substitution table; 
     FIG. 3 illustrates the compression procedure flow chart. 
     FIG. 4 illustrates the substitution table update routine flow chart. 
     FIG. 5 illustrates the decompression routine flow chart. 
    
    
     DETAILED DESCRIPTION 
     Referring to FIG. 1, a block diagram illustrates the overall flow of data through the compression and decompression algorithms An input register 11 receives input characters in a serial fashion. That is, each input character is individually input into the input register. For the purposes of this disclosure, an input character is generally a binary data word which represents the particular character to be input. The binary data word may be of any size, and is not limited to seven-bit ASCII characters. 
     The contents of the input register are compressed according to the contents of a compression substitution table 12. The compression substitution table contains character strings which allow multiple input characters to be represented as a single token. FIG. 2 illustrates a simplified memory map for an exemplary compression substitution table. 
     As shown in FIG. 2, an exemplary substitution table contains a plurality of table entries 13, organized into columns of data. The first two columns contain tokens (designated as token1 14 and token2 16, wherein the content of each token field 17 may be either a character token or a substitution code (sub-code) token. A character token represents an individual character and a sub-code token represents a pair of tokens located elsewhere in the substitution table. In other words, a sub-code token uniquely identifies one of the substitution table entries and represents the two tokens placed in that table entry. 
     For example, assume that one substitution table entry contains two character tokens representing the characters &#34;t&#34; and &#34;h&#34;. Assume further that a second table entry contains one sub-code token representing the table entry having &#34;t&#34; and &#34;h&#34; along with a character token representing the character &#34;e&#34;. The second table entry represents the word &#34;the&#34;. Further, if a third table entry contains a sub-code token representing the second table entry along with a character token representing the character &#34;n&#34;, then this third table entry represents the word &#34;then&#34;. 
     It is important to note that each entry in the substitution table may contain 1) two character tokens, 2) one character token and one sub-code token (each type of token located in either the first or second token position) or 3) two sub-code tokens. The flexibility of the substitution table not only allows additional characters to be added to the end of existing character strings, but also existing character strings to be added as a suffix to individual characters, other character strings or any combination of the above. For example, once the character string &#34;for&#34; is in the table, it may be used as part of the character strings &#34;fort&#34;, &#34;form&#34; and &#34;fork&#34;, as well as &#34;before&#34; and &#34;afford&#34;. 
     The third column shown in FIG. 2 is the reference count 18. Each substitution table entry has associated with it a reference count which is used to make sure that no entry in the substitution table is replaced if that entry is being referenced by a sub-code token in another table entry. In the compression procedure described in detail below, only table entries having a reference count of zero can be changed. In the example cited above where the first table entry had tokens representing the characters &#34;t&#34; and &#34;h&#34; (and thus representing the character string &#34;th&#34;), the reference count for the first table entry was incremented as soon as other table entries were updated to reference the first table entry (such as the second table entry). If, on the other hand, the first table entry was allowed to be changed, to contain the characters &#34;c&#34; and &#34;k&#34; for example, then the dependant table entries would also change their meanings. The second table entry would have tokens which represent the character string &#34;cke&#34; rather than &#34;the&#34;. The third table entry would have tokens which represent the character string &#34;cken&#34; rather than &#34;then&#34;. 
     The fourth column of data contains a pointer mechanism 19. The pointer mechanism uniquely identifies each substitution table entry and has the capability of monitoring the frequency with which each table entry is being used by the compression algorithm. In other words, the pointer mechanism keeps track of the entries in the substitution table in a most recently used to least recently used order. Table entries that are the least recently used are updated first. The pointer mechanism may be implemented in a variety of ways, and as such is not limited to one data field per table entry as shown in FIG. 2. 
     Returning now to the general description of the compression and decompression procedure, pairs of characters in the input data stream are replaced by a single substitution code token which represents the entry in the substitution table containing the characters being replaced Substitution is attempted repeatedly, and pairs of substitution table tokens are replaced by a single substitution code until no more substitutions can be made. The characters and substitution code tokens in the input register are then transmitted as output tokens on a transmission medium 21. 
     Concurrently, new entries are being made in the substitution table according to the substitutions previously made. New entries replace old entries in the substitution table which have not been used in a while. These new entries will allow previously uncompressible character strings to be compressible if they appear again in the input data stream. 
     Once the table update procedure has been completed, more input characters are loaded into the input register according to the compression procedure described above. 
     Meanwhile, the output tokens on line 21 are received by an output register 22 which is, in turn, coupled to an output substitution table 23. The output substitution table contains entries which are identical to the entries originally in the input substitution table. Each sub-code token received by the output register is replaced by the pair of tokens from the output substitution table it represents. Again, these tokens may be either characters tokens or sub-code tokens. Substitution code tokens are repeatedly replaced by pairs of tokens from the substitution table until only character tokens remain. The character tokens are output as the output characters (which are identical to the original input characters). 
     In order to properly decode the transmitted code tokens, the output substitution table must be updated in exactly the same way as the input substitution table. Thus, new entries are made in the output substitution table which are based entirely on the received output tokens. 
     It is crucial that while the decompression algorithm is expanding data in a particular point in the data stream, the contents of the output substitution table be exactly the same as the contents of the input substitution table were when the compression algorithm was compressing the same point in the data stream. 
     FIG. 3 shows, in detail, the procedure used for compressing input characters The compression procedure begins with the step shown in box 26 wherein the input substitution table is initialized so that the table entries contain predetermined values. The actual values are not important, however the values must be known so that the output substitution table can be initialized to the same values. The tokens in each table entry may contain any character token as long as the initial state of the input substitution table is known. The reference count for each table entry is initialized to zero. 
     The compression procedure continues with the step shown in box 27 wherein an integer variable, N, is set to zero and a flag (first flag) is set to a one. The variable N indicates how many memory locations in the input register are filled with either character tokens or sub-code tokens. First flag is a decisional flag used by the substitution table update procedure as described below. 
     The next step in the compression procedure is shown in box 28 wherein N is incremented by one. In the following step, shown in box 29, an input character is stored in the Nth location (B n ) of the input register. At this point in the procedure, according to decisional box 30, if N is less than two, then the portion of the procedure beginning at intermediate point A is repeated. For example if N is equal to one, then N is incremented (to two) and an input character is stored in the Nth location of the input register Note that the previously stored input character now resides in the (N-1)th location (B n-1 ) of the input register. 
     This loop in the compression procedure, shown in the flow chart between box 30 and intermediate point A is required to ensure that there are at least two tokens in the input register. This follows from the simple fact that the input register must have at least two tokens in order for the contents of the input register to be compressible. 
     Continuing with the compression procedure, as shown in box 31, if there is an entry in the input substitution table wherein token1 equals the token in the (N-1)th location of the input register and token2 equals the token in the Nth location of the input register, then N is decremented, according to box 32, and the contents of the Nth location of the input register is replaced with the sub-code token which represents the substitution table entry identified in box 31. For example, if N equals two, and the contents of the first location of the input register is &#34;s&#34;, the contents of the second location of the input register is &#34;o&#34; and there is a table entry having token1 and token2 equal to &#34;s&#34; and &#34;o&#34; respectively, then N is decremented to equal one, according to box 32 of the flow chart, and the sub-code token representing the identified table entry is loaded into the first location of the input register (the second location of the register is now blank). 
     Returning to the compression procedure, if N is greater than one, then the procedure returns to intermediate point B. If N is not greater than 1, then the procedure continues to intermediate point C. Also, if the input substitution table does not contain an entry which satisfies the question in box 31, then the procedure continues to intermediate point C, bypassing boxes 32, 33 and 34. 
     Continuing with the compression procedure, immediately following intermediate point C at decisional box 35, if N is no longer equal to or greater than two, the procedure returns to intermediate point A in order to load another input character into the input register. If, however, N is equal or greater than two, the procedure continues to decisional box 36. Accordingly, if there is an entry in the input substitution table which has a token1 equal to the contents of the (N-1)th location of the input register and a token2 which will expand, through any number of substitutions, to a character string beginning with the contents of the Nth location of the input register, then the portion of the compression procedure beginning at intermediate step A is repeated. 
     Token2 will expand to a string beginning with a particular token if it is a sub-code token and it represents a tree structure of referenced substitution table entries wherein the first node of the tree is a table entry having token1 equal to the designated token. For example, assume a first table entry (Entry1) having a token1 representing &#34;e&#34; and a token2 representing &#34;f&#34; and a second table entry (Entry2) having a token1 representing &#34;d&#34; and a token2 representing Entry1 (i.e., a sub-code token identifying the first table entry). If the input register has in its first two locations the characters &#34;d&#34; and &#34;e&#34; respectively, then the second table entry (Entry2) has a token1 which equals the (N-1)th location in the input register and a token2 which is expandable to a character string starting with the character &#34;e&#34;. 
     If there is no substitution table entry as defined in box 37 then no more compression can be done on the input characters that have been stored in the input register, and the compression procedure is interrupted by the table update subroutine indicated in box 38. At this point in the compression procedure, the input register contains at least two tokens. Each of the tokens may be either a character token or sub-code token. The contents of the first through (N-1)th location of the input register are output, one at a time, as output tokens on transmission medium 21 according to the table update routine described in detail below. 
     The table update routine begins with the steps shown in box 41 shown in FIG. 4 wherein a binary variable &#34;current token&#34; is set to equal the token in the first location of the input register and a flag &#34;X&#34; is set to zero. The following step, shown in box 42, is to transmit &#34;current token&#34; as an output token on transmission medium 21. If &#34;first flag&#34; is still set to one (it was set during the compression procedure according to box 27) then &#34;first flag&#34; is set to zero, a binary variable &#34;previous token&#34; is set to equal &#34;current token&#34; and the procedure returns to intermediate point D in the compression procedure or to the beginning of the table output routine if there more than two tokens in the input register available for output (i.e., if there are more than two tokens in the input register). 
     In other words, no table update is performed upon the output of the first token in the input register However, the output token is saved (in the variable previous token) for use in updating the substitution table the next time through the table update routine. 
     Returning now to the table update subroutine, if &#34;first flag&#34; no longer equals one, then the table update procedure continues to box 43. Accordingly, if there is an entry in the substitution table wherein token1 equals &#34;previous token&#34; and token2 equals &#34;current token&#34;, then the table update routine flows to box 44. According to box 44, if the reference count for the substitution table entry found according to the box 43 is zero then that substitution table entry is to be marked as the most recently used entry. Regardless of whether the reference count is zero for the above identified substitution table entry (i.e., the entry found in decisional box 43), &#34;previous token&#34; is set equal to &#34;current token&#34; and the routine returns to intermediate point D in the compression procedure. 
     However, if no entry is found in the substitution table according to box 43, then the table update proceeds to box 36, wherein if either &#34;previous token&#34; or &#34;current token&#34; is a sub-code token, then the reference count for the corresponding substitution table entries are incremented by one according to box 47 of the flow chart. Incrementing the reference count of the table entries protects those entries from being updated, at least until the reference are decremented once again. This is an important step since the tokens about to be recorded together (&#34;previous token&#34; and &#34;current token&#34;) in a new table entry may reference other table entries. Incrementing the reference count of the referenced entries ensures that the contents of the referenced entries are not changed as long as there are table entries dependant upon them. 
     Returning to the table update routine, regardless of whether &#34;previous token&#34; or &#34;current token&#34; is a sub-code token, the table update routine continues to intermediate point E. 
     Point E in the table substitution routine represents the point where a new table entry is to be written in the substitution table. Accordingly box 48 probes whether there are any entries in the substitution table that have a reference count of zero. If no entries are found with a reference count of zero, then the routine continues to box 49. If either the &#34;previous token&#34; or &#34;current token&#34; is a sub-code token then the reference count for the corresponding table entries is decremented by one. If the corresponding table entries have a reference count of zero, then the entries are marked as the most recently used. Regardless of the outcome of the decision in box 49, &#34;previous token&#34; is set to equal &#34;current token&#34;, and the routine returns to the compression procedure. Note that if no substitution table entries with a reference count of zero are found, then the substitution table is not updated. 
     Returning however to box 48, if a substitution table entry is found with a reference count of zero, then the routine proceeds to box 51 wherein it is asked whether token1 or token2 is a sub-code token. If either is a sub-(code token, then the reference count for the corresponding table entries is decremented. If the corresponding table entries have a reference count of zero, then each entry is marked as most recently used. Regardless of whether either of the tokens is a sub-code token, the routine proceeds to box 53. 
     Box 53 determines whether the contents of the Nth location of the input register is the sub-code for the table entry identified in box 48. If so, then flag &#34;X&#34; is set to one, token1 of the identified table entry is loaded into the Nth location of the input register and token2 of the identified table entry is loaded into the (N+1)th location of the input register according to box 54 of FIG. 4 (Flag &#34;X&#34; is used by the compression procedure to correctly set the contents of the input register). The purpose of these steps is to &#34;un-do&#34; the last data compression performed by the compression procedure. This is necessary since the sub-code token in the Nth location of the input buffer references a table entry that was just updated by the table update routine. 
     Regardless of the outcome of the decision in box 53, the table entry identified in box 48 is updated with &#34;previous token&#34; and &#34;current token&#34; whereby the former is loaded into the token1 data field and the latter is loaded into the token2 data field. The table update routine subsequently returns to the compression procedure. 
     Upon return from the table update routine, the compression procedure continues to decisional box 56 where it is asked whether the flag &#34;X&#34; has been set to a one. If it has not been set to a one, then the contents of the Nth location of the input buffer is moved to the first location and N is set to one. If, on the other hand, the flag &#34;X&#34; has been set to one, then the token in the (N-1)th location of the input register is moved to the first location, the token in the Nth location is moved to the second location and N is set to two. Once the contents of the input register has been adjusted the compression procedure returns to intermediate point A. 
     FIG. 5 shows, in detail, the procedure used for decompressing the transmitted output tokens. The decompression procedure begins with the step shown in box 61 wherein the output substitution table is initialized to the same predetermined values that the input substitution table was initialized to. The decompression procedure continues with the step shown in box 62 wherein an integer variable, M, is set to zero and a flag (first flag) is set to one. The variable M indicates how many memory locations in the output register are filled with tokens. First flag is a decisional flag used by the output substitution table update procedure. 
     The next step in the decompression procedure is shown in box 63 wherein M is incremented by one. In the following step, shown in box 64, an output token is loaded into the Mth location of the output register. At this point in the procedure, if M is less than two (according to decisional box 65), then the decompression procedure continues to intermediate point G. According to decisional box 66, if the token currently in the Mth location of the output register is a character token, then the token is output as an output character. If, however, the token in the Mth location of the output register is a sub-code token, then the token is expanded by replacing in with the tokens in the corresponding table entry in the output substitution table. This expansion is repeated until each of the sub-code tokens which replace previously expanded tokens are expanded to character tokens. 
     It is important to note that although the character tokens are output as output characters, the original character token or un-expanded sub-code token that was resident in the output register remains in the register. After the appropriate tokens are output, the decompression procedure returns to intermediate point F. 
     If M is not less than two when the decisional box 65 is reached, then the procedure continues to decisional box 67. If there is a substitution table entry with a token1 matching the token in the (M-1)th location in the output register and a token2 matching a sub-code token which will expand, through any number of substitutions, to a character string beginning with the token in the Mth location of the output register, then the procedure continues to intermediate point G. On the other hand, if the condition in box 67 is not met, then it is known that there are at least two tokens in the output register, and the output substitution table is to be updated based on the contents of the output register. The output substitution table update routine is performed on each of the tokens 1 through M-1 in the output register. 
     The output table update routine is the same as the update routine for the input substitution table with one minor exception In the table update routine for the output substitution table the steps shown in boxes 53 and 54 are not required Upon completion of the table update routine, the token in the Mth location of the output register is moved to the first location of the output register, M is reset to one, and the decompression procedure continues to intermediate point G. 
     It is apparent that in the compression procedure as described above, the last input character in the message to be transmitted is never output by the compression procedure as an output token. In an exemplary embodiment of the present invention, this is overcome by flushing the input register of all tokens each time the input register has to wait for new input characters for a predetermined period of time. When the input register is flushed in this manner, all of the tokens are used to perform table substitution according to the table update routine as disclosed. Synchronization between the input substitution table and the output substitution table is maintained by using a third type of output token in the compression procedure A special token, called a flush flag is output immediately following the flush of the input register. When the output register receives the flush flag, the decompression procedure ensures that all of the tokens in the output register are flushed and the table update routine is performed on all of the flushed tokens. The flush flag itself is never included in the updated input or output substitution tables. 
     A specific embodiment of the present invention is disclosed in Appendix A, the contents of which are incorporated by reference herein. Appendix A discloses two C language programs, one of which implements the compression procedure, and the other implements the decompression procedure. 
     The preceding description has been presented with reference to the presently preferred embodiment to the invention shown in the drawings. Those skilled in the art and technology to which this invention pertains will appreciate that alterations and changes in the described structures can be practiced without departing from the spirit, principles and scope of this invention.