Method for data compression having an improved encoding algorithm which utilizes a token stacking technique

An encoding method for use with digital data compression operations which compress an input data string into an output data string containing compressed and uncompressed substrings mixed in series, the encoding method comprising the following steps:

• a. constructing a group of stacked tokens including a first 2-byte stacked token and a second 2-byte stacked token each having a plurality of fields including a substring type identifier field, a backward displacement pointer field and a substring length counter field, where the substring length counter field occupies 4 bits and is identical among all stacked tokens in the group for serving as the basis in constructing the group of 2-byte stacked tokens;
• b. assigning a respective range of integers to be encoded in said backward displacement pointer field of each individual one of said stacked tokens, where the individual ranges of said backward displacement pointer field assigned to said group of stacked tokens cover a larger range, and no individual range of said backwards displacement pointer field of said stacked token overlaps with the individual range of said backward displacement field of any other stacked tokens in the group, particularly when the range assigned to said backward displacement pointer field of first stacked token is 0 to 31, and the range of said backwards displacement field of second stacked token is 32 to 95;
• c. determining a respective substring type identifier for a respective one of said compressed substrings;
• d. determining a respective substring length counter for said respective one of said compressed substrings;
• e. determining a respective backward displacement pointer for said respective one of said compressed substrings, which backward displacement pointer is a respective integer count of displacement between the respective one of said compressed substrings and a previously processed identical substring in said mixed series;
• f. representing said respective one of said compressed substrings with a respective one of said stacked tokens by encoding a plurality of indicators into said plurality of fields respectively, including encoding said respective substring type identifier into said substring type identifier field of said respective one of said stacked tokens, and encoding said respective substring length counter into said substring length counter field of said respective one of said stacked tokens;
• g. further encoding said respective backward displacement pointer into said backward displacement pointer field of the respective one of said stacked tokens according to the range assigned, such that said respective backward displacement pointer falls within the range assigned to said respective one of said stacked tokens, particularly representing said respective one of said compressed substrings with said first 2-byte stacked token when said respective backward displacement pointer of said respective one of said compressed substrings is within the range of 0 to 31 and representing said compressed substrings with said second 2-byte stacked token when said respective backward displacement pointer of said respective one of said compressed substrings is within the range of 32 to 95;
• and
• h. repeating steps (c) through (h) until all of said compressed substrings are represented by one of said stacked tokens.

A data compression method for compressing an input data string containing a series of compressible substrings, the data compression method comprising the following steps:

• a. constructing a group of stacked tokens each having a plurality of fields including a backward displacement pointer field and a substring length counter field, where the substring length counter field is identical among all stacked tokens in the group for serving as the basis in constructing the group of stacked tokens;
• b. assigning a respective range of integers to be encoded in said backward displacement pointer field of each individual one of said stacked tokens, where the individual ranges of said backward displacement pointer field assigned to said stacked tokens cover a larger range, and no individual range of said backward displacement pointer fields of said stacked tokens overlaps with the individual range of said backwards displacement field of any other stacked token in the group;
• c. identifying a compressible substring of said input data string when there is a previously processed identical substring;
• d. determining a backward displacement pointer for said compressible substring, which backward displacement pointer is an integer count of displacement between said compressible substring and said previously processed identical substring;
• e. representing said compressible substring with a respective one of said stacked tokens by encoding said backward displacement pointer into said backward displacement pointer field of the respective one of said stacked tokens according to the range assigned, such that said backward displacement pointer falls within the range assigned to the respective one of said stacked tokens;
• and
• f. repeating steps (c) through (e) until all of the compressible substrings are represented by one of said stacked tokens.

A method of encoding a compressible substring for digital data compression operations, the encoding method comprising the steps of:

• a. constructing a group of stacked tokens each having a plurality of fields including a backward displacement pointer field and a substring length counter field, where the substring length counter field is identical among all stacked tokens in the group for serving as the basis in constructing the group of stacked tokens;
• b. assigning a respective range of integers to be encoded in said backward displacement pointer field of each individual one of said stacked tokens, where the individual ranges of said backward displacement pointer field assigned to said group of stacked tokens cover a larger range, and no individual range of said backward displacement pointer fields of said stacked tokens overlaps with the individual range of said backwards displacement field of any other stacked token in the group;
• c. determining a backward displacement pointer for said compressible substring, which backward displacement pointer is an integer count of displacement between said compressible substring and a previously processed identical substring;
• and
• d. encoding said backward displacement pointer into said backward displacement pointer field of a respective one of said stacked tokens according to the range assigned, such that said backward displacement pointer falls within the range assigned to the respective one of said stacked tokens.

A method of encoding a compressible substring for digital data compression operations, the encoding method comprising the following steps:

• a. constructing a group of stacked tokens each having a plurality of fields for encoding a plurality of indicators carrying information of said compressible substring, where at least one of the plurality of fields is identical among all of the stacked tokens in the group for serving as the basis in constructing the group of stacked tokens;
• b. assigning a respective range of integers to be encoded in another one of said plurality of fields other than said at least one identical field for each individual one of said stacked tokens, where the individual ranges of said field assigned to said stacked tokens cover a larger range, and no individual range of said field of said stacked token overlaps with the individual range of said field of any other stacked token in the group;
• c. determining at least one of said plurality of indicators for said compressible substring, which carries encoding information of said compressible substring;
• and
• d. encoding said at least one of said plurality of indicators into said another one of said plurality of fields of a respective one of said stacked tokens, where said at least one of said plurality of indicators falls within the range assigned to the respective one of said stacked tokens.