Lossless binary compression in a memory constrained environment

A system for compressing a data structure generated for a computing system, this system comprising:

• one or more computing nodes having a memory and a processor;
• and
• a non-transitory computer readable storage medium of the one or more computing nodes having program instructions embodied therewith, the program instructions executable by the processor to cause the system to:
• generate a table comprising block values of a set of blocks in the data structure, wherein:
• a block size of each block in the set of blocks is determined by an architecture of the computing system, and
• the block values are a threshold number of the most frequently occurring block values in the data structure;
• determine whether a first block value of a block in the data structure is stored in the table, the block occurring at a position in the data structure;
• store, in response to determining that the first block value is stored in the table, a table index of the first block value at a first location in a first data structure, the first location corresponding to the position;
• store, at a second location in a second data structure, a second value indicating whether the first block value is stored in the table, the second location corresponding to the position;
• and
• generate a compressed data structure, the compressed data structure comprising the table, the first data structure, and the second data structure.

A computer program product for compressing a data structure generated for a computing system, the computer program product including a computer readable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal per se, the program instructions executable by a processing circuit to cause the processing circuit to perform a method comprising:

• generating a table comprising block values of a set of blocks in the data structure, wherein:
• a block size of each block in the set of blocks is determined by an architecture of the computing system, and
• the block values are a threshold number of the most frequently occurring block values in the data structure;
• determining whether a first block value of a block in the data structure is stored in the table, the block occurring at a position in the data structure;
• storing, in response to determining that the first block value is stored in the table, a table index of the first block value at a first location in a first data structure, the first location corresponding to the position;
• storing, at a second location in a second data structure, a second value indicating whether the first block value is stored in the table, the second location corresponding to the position;
• and generating a compressed data structure, the compressed data structure comprising the table, first data structure and the second data structure;
• and
• generating a compressed data structure, the compressed data structure comprising the table, the first data structure, and the second data structure.