Memory preserving parse tree based compression with entropy coding

A computer program product comprising:

• a computer readable storage medium readable by one or more processor and storing instructions for execution by the one or more processor for performing a method comprising:
• obtaining, by a processor, data comprised of values, wherein the values are of variable size, and generating a value conversion dictionary by applying a parse tree based compression algorithm to the data, wherein the value conversion dictionary is comprised of dictionary entries that represent the values;
• obtaining, by the processor, a distribution of the values and estimating a likelihood for each value based on the distribution;
• generating, by the processor, a code word to represent each value, wherein a size of each code word is inversely proportional to the likelihood of the value represented by the code word;
• assigning, by the processor, a rank to each code word, wherein the rank for each code word represents the likelihood of the value represented by the code word;
• based on the rank associated with each code word, reordering, by the processor, each dictionary entry in the value conversion dictionary to associate each dictionary entry with an equivalent rank, wherein the reordered value conversion dictionary comprises an architected dictionary;
• and
• storing, by the processor, the architected dictionary in a memory, wherein the processor utilizes the architected dictionary to compress data subsequently obtained by the processor and to decompress code words subsequently obtained by the processor, wherein utilizing the architected dictionary to compress data subsequently obtained by the processor and decompressing code words subsequently obtained by the processor do not comprise the processor performing a memory lookup.

A system comprising:

• a memory;
• one or more processor in communication with the memory;
• and
• program instructions executable by the one or more processor via the memory to perform a method, the method comprising:
• obtaining, by a processor, data comprised of values, wherein the values are of variable size, and generating a value conversion dictionary by applying a parse tree based compression algorithm to the data, wherein the value conversion dictionary is comprised of dictionary entries that represent the values;
• obtaining, by the processor, a distribution of the values and estimating a likelihood for each value based on the distribution;
• generating, by the processor, a code word to represent each value, wherein a size of each code word is inversely proportional to the likelihood of the value represented by the code word;
• assigning, by the processor, a rank to each code word, wherein the rank for each code word represents the likelihood of the value represented by the code word;
• based on the rank associated with each code word, reordering, by the processor, each dictionary entry in the value conversion dictionary to associate each dictionary entry with an equivalent rank, wherein the reordered value conversion dictionary comprises an architected dictionary;
• and
• storing, by the processor, the architected dictionary in a memory, wherein the processor utilizes the architected dictionary to compress data subsequently obtained by the processor and to decompress code words subsequently obtained by the processor, wherein utilizing the architected dictionary to compress data subsequently obtained by the processor and decompressing code words subsequently obtained by the processor do not comprise the processor performing a memory lookup.