Lossless data compression with variable width codes

A non-transitory machine readable medium storing one or more sequences of instructions for causing a digital processing system to process data, wherein execution of said one or more sequences of instructions by one or more processors contained in said digital processing system causes said digital processing system to perform the actions of:

• receiving an input stream containing a sequence of symbols;
• maintaining a dictionary containing a plurality of entries, wherein each entry associates a token to an assigned code, said plurality of entries being grouped into a first partition and a second partition said dictionary containing a first partition and a second partition;
• emitting to an output stream, an output code corresponding to a string of said input stream, wherein said output code is the assigned code associated with a token matching said string in a first entry of said dictionary;
• storing data indicating whether each entry of said second partition is unused in forming said output stream, wherein the data is stored to indicate that said first entry is not unused if said first entry is in said second partition;
• forming a first token and a second token associated with processing of said string;
• checking whether there are two codes not assigned in said dictionary for a present width of codes being assigned;
• if there are two codes not assigned:
• adding to said first partition a first entry associating said first token to one of the two codes not assigned, and
• adding to said second partition a second entry associating said second token to the other one of the two codes not assigned;
• otherwise:
• inspecting said data to determine a third entry of said second partition that is indicated to be unused;
• and
• adding a fourth entry associating said first token to the code of said third entry such that said third entry is replaced by said fourth entry in said dictionary.

A digital processing system comprising:

• a processor;
• a random access memory (RAM);
• a machine readable medium to store one or more instructions, which when retrieved into said RAM and executed by said processor causes said digital processing system to perform the actions of:
• receiving an input stream containing a sequence of symbols;
• identifying a longest string from a present symbol matching a first token in a dictionary, said dictionary containing a plurality of entries, each entry associating a token to a corresponding code, a first entry of said plurality of entries associating said first token to a first code;
• emitting the code corresponding to said first token in a corresponding entry, as an output code to an output stream;
• adding a second entry and a third entry to said dictionary,
• wherein said second entry associates (said longest string+symbol succeeding said longest string in said input stream) to a first available code according to said dictionary,
• wherein said third entry associates (a previous token+symbol succeeding said previous token in said input stream) to a second available code according to said dictionary, wherein said previous token represents the token of said second entry in a previous iteration,
• wherein ‘+’ represents a text appending operation,
• wherein said emitting and said adding are performed in response to said identifying of said longest string from said present symbol;
• and
• performing a next iteration of said identifying, said emitting and said adding with said present symbol set to the symbol succeeding said longest string in said input stream.