Method and apparatus for efficient deflate decompression using content-addressable data structures

A method comprising:

• extracting a sequence of tokens and corresponding length values from a header of a compression block, the tokens and corresponding length values associated with a type of compression used to compress a payload of the compression block;
• and
• constructing a content-addressable data structure based on the tokens and length values by:
• writing to an entry in the content-addressable data structure including writing a length value and a count value,
• the count value indicating a number of times the length value was previously written to an entry in the content-addressable data structure.

A machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform the operations of:

• extracting a sequence of tokens and corresponding length values from a header of a compression block, the tokens and corresponding length values associated with a type of compression used to compress a payload of the compression block;
• and
• constructing a content-addressable data structure based on the tokens and length values by:
• writing to an entry in the content-addressable data structure including writing a length value and a count value,
• the count value indicating a number of times the length value was previously written to an entry in the content-addressable data structure.