Methods and apparatus to parallelize data decompression

An apparatus to parallelize data decompression, comprising:

• a segment trainer to:
• select initial starting positions in a compressed data bitstream;
• and
• adjust a first one of the initial starting positions to determine a first adjusted starting position by decoding the compressed data bitstream starting at a training position in the compressed data bitstream, the training position preceding the first one of the initial starting positions in the compressed data bitstream, the decoding including traversing the compressed data bitstream from the training position as though first data located at the training position is a valid token;
• a parallelized decoder to output first decoded data generated by decoding a first segment of the compressed data bitstream starting from the first adjusted starting position;
• and
• a segment merger to merge the first decoded data with second decoded data generated by decoding a second segment of the compressed data bitstream, the decoding of the second segment starting from a second position in the compressed data bitstream and being performed in parallel with the decoding of the first segment, and the second segment preceding the first segment in the compressed data bitstream.

A tangible computer readable storage medium comprising computer readable instructions which, when executed, cause a processor to at least:

• select initial starting positions in a compressed data bitstream;
• adjust a first one of the initial starting positions to determine a first adjusted starting position by decoding the compressed data bitstream starting at a training position in the compressed data bitstream, the training position preceding the first one of the initial starting positions in the compressed data bitstream, the decoding including traversing the compressed data bitstream from the training position as though first data located at the training position is a valid token;
• output first decoded data generated by decoding a first segment of the compressed data bitstream starting from the first adjusted starting position;
• and
• merge the first decoded data with second decoded data generated by decoding a second segment of the compressed data bitstream, the decoding of the second segment starting from a second position in the compressed data bitstream and being performed in parallel with the decoding of the first segment, and the second segment preceding the first segment in the compressed data bitstream.