Interpolation search to find arbitrary offsets in a compressed stream

A system, comprising:

• a processor;
• and
• a memory storage device including instructions that when executed by the processor enable the system to:
• determine a low point and a high point in an uncompressed version of a stream corresponding to a compressed version of the stream that is divided into a plurality of chunks;
• calculate an average compression ratio between the low point and the high point;
• interpolate a position in the compressed version of a desired offset in the uncompressed version to identify a bifurcation chunk of the plurality of chunks that includes the interpolated position;
• read an offset of the bifurcation chunk;
• and
• in response to determining that the desired offset is within a threshold distance of the offset of the bifurcation chunk, decompress the compressed version from the bifurcation chunk until the desired offset is output.

A computer-readable storage medium having computer-readable program code embodied therewith, the computer-readable program code executable by one or more computer processors to:

• determine a low point and a high point in an uncompressed version of a stream corresponding to a compressed version of the stream that is divided into a plurality of chunks;
• calculate an average compression ratio between the low point and the high point;
• interpolate a position in the compressed version of a desired offset in the uncompressed version to identify a bifurcation chunk of the plurality of chunks that includes the interpolated position;
• read an offset of the bifurcation chunk;
• and
• in response to determining that the desired offset is within a threshold distance of the offset of the bifurcation chunk, decompress the compressed version from the bifurcation chunk until the desired offset is output.