Method and system for compression and decompression using variable-sized offset and length fields

In a computer system, a method of compressing a sequence of data into chunks of compressed data, comprising:

• (a) dividing the sequence of data into a series of blocks;
• (b) processing a first portion of the data at a location in a block to identify at least one sub-sequence of data in the first portion to compress;
• (c) determining another sub-sequence of data to be compressed at another location in a second portion of the block;
• (d) determining whether at least part of the other sub-sequence of data in the second portion of the block matches at least part of the sub-sequence of data in the first portion of the block;
• (e) where at least part of the other sub-sequence of data in the second portion of the block does not match at least part of the sub-sequence of data in the first portion of the block, encoding the not matched part of the other sub-sequence of data in the second portion of the block as a literal token, said literal token being added to a chunk of compressed data that is associated with the block;
• and
• (f) where at least part of the other sub-sequence of data in the second portion of the block does match at least part of the sub-sequence of data in the first portion of the block, encoding the matched part of the other sub-sequence of data in the second portion of the block into a copy token with a fixed number of bits that is added to the chunk of compressed data associated with the block the copy token including an offset field that identifies an offset between the other location of the matched part of the other sub-sequence of data in the second portion of the block and the location of the matched part of the sub-sequence of data in the first portion of the block, and a length field that identifies a length of the matched part of the sub-sequence of data in the first portion of the block, wherein how many bits are in the offset field depends on the position of the matched part at the other location of the other sub-sequence of data in the second portion of the block.

In a computer system, a method of compressing a file comprising pieces of data, comprising:

• (a) dividing the file into blocks of data;
• (b) separately compressing each block of data into a chunk of compressed data by performing the following:
• (i) sequentially examining each sub-sequence of data in each block of data;
• (ii) encoding each subsequent sub-sequence of data in a block that is over a minimum threshold length and that has occurred previously in the block as a copy token of a predetermined number of bits, each copy token including an offset field that specifies an offset between the subsequent occurrence of the sub-sequence of data at a location in the block and another location in the block that the sub-sequence of data first occurred and a length field that specifies a length of the first occurrence of the sub-sequence of data at the other location in the block, wherein how many bits are used in the offset field depends on the location of the subsequent occurrence of the sub-sequence of data within the block;
• and
• (iii) encoding each sub-sequence of data in the block, that is not encoded as a copy token, as a literal token in the compressed chunk.

In a computer system, a method of decompressing an item in a chunk of a compressed file having a number of separate chunks, comprising:

• (a) identifying which chunk of the compressed file holds the item, said identified chunk including like-sized copy tokens and also including literal tokens;
• (b) decompressing the chunk of the compressed file that has been identified as holding the item while keeping other chunks compressed, said decompressing comprising:
• (i) identifying a first of the copy tokens that encodes a current sub-sequence of data that includes the item, said first copy token including an offset field that specifies an offset between the current sub-sequence of data and a previous occurrence of the sub-sequence of data that is included in a sequence of literal tokens;
• (ii) identifying how many bits are in the offset field by identifying a location of a first of the sequence of literal tokens that encode the previous occurrence of the sub-sequence of data;
• and
• (iii) decompressing the first copy token by replacing the first copy token with the previous occurrence of the sub-sequence of data that the sequence of literal tokens encode.

In a computer system, a method of decompressing a sequence of chunks of compressed data containing copy tokens and literal tokens, wherein the copy tokens each contain an offset field and a number of bits in the offset field that depends upon a location in a sequence of data prior to compressing the sequence of data into the sequence of chunks of compressed data, said method comprising:

• for each of the copy tokens,
• (i) identifying a number of bits in the offset field by determining a location of a sub-sequence of data prior to encoding by the copy token;
• (ii) using the identified offset field to locate the sub-sequence of data that is encoded by the copy token;
• (iii) replacing the copy token with the sub-sequence of data that is encoded by the copy token;
• and
• for each literal token, keeping the literal token in the sequence.

In a computer system, a method for compressing a sequence of data, comprising:

• (a) dividing the sequence of the data into a series of consecutive blocks, each block having a predetermined amount of data;
• (b) compressing each block of data into a chunk of compressed data, the compression of a block of data comprising:
• (i) sequentially examining data in the block to identify a pattern of data;
• (ii) encoding a copy token to represent each subsequent occurrence of each pattern in the block of data that has initially occurred at a previous location in the block of data;
• (iii) encoding a literal token to represent each initial occurrence of each pattern in the block of data;
• and
• (iv) producing a sequence of each literal token and each copy token.