Compression device, decompression device, and method

A decompression device used to decompress compressed data that includes a first index assigned to a first match position indicating a position in a first buffer of second data at least partially matching first data input to a compression device having a first buffer in which second data previously input to the compression device is stored and a first match length indicating a matched length of the first data and the second data, the decompression device comprising:

• a second buffer in which a second match position converted into a second index previously cut out from the compressed data in the decompression device is stored together with a third index assigned to the second match position;
• a third buffer in which the second data generated based on a second match position converted into the second index previously cut out from the compressed data in the decompression device and a second match length cut out from the compressed data is stored;
• a search unit that searches for a third index matching the first index from the second buffer;
• and
• a first decoder that converts the third index into the second match position to which the third index is assigned, reads the second data from the third buffer based on the second match position, and generates the first data by shaping the second data based on the first match length, when the third index matching the first index is searched.

A compression device used to compress input first data, comprising:

• a buffer in which previously input second data is stored;
• a table in which a second hash value calculated from at least a part of the second data and a match position indicating a position of the second data in the buffer are stored in association with each other;
• a calculator that calculates a first hash value from at least a part of the first data;
• a dictionary based encoder that searches for second data at least partially matching the first data from the buffer based on the match position stored in the table in association with the second hash value matching the first hash value, and acquires a match length indicating a matched length of the first data and the second data;
• an entropy encoder that performs entropy encoding on the first hash value and the match length;
• and
• a compression data generator that generates compressed data including the entropy-encoded hash value and match length.

A decompression device used to decompress compressed data that includes a first hash value calculated from first data input in a compression device and a first match length indicating a matched length of second data at least partially matching the first data searched from a first buffer in which the second data previously input in the compression device is stored and the first data, the first hash value and the first match length being entropy-encoded, the decompression device comprising:

• a second buffer that the second data generated based on a second hash value and a second match length previously cut out from the compressed data in the decompression device is stored;
• a table in which the second hash value calculated from at least a part of the second data and the match position indicating a position of the second data in the second buffer are stored in association with each other;
• an entropy decoder that decodes the first hash value and first match length included in the compressed data;
• and
• a dictionary based decoder that reads the second data from the second buffer based on the match position stored in the table in association with the second hash value matching the decoded first hash value and generates the first data by shaping the second data based on the decoded match length.

A method for compressing input first data, comprising:

• searching for previously input second data at least partially matching the first data from a first buffer in which the second data is stored, and acquiring a first match position indicating a position of the second data in the first buffer and a match length indicating a matched length of the first data and the second data;
• comparing the first match position with a second match position stored in a second buffer by referring to the second buffer in which the previously acquired second match position is stored together with an index assigned to the second match position;
• and
• generating first compressed data including the index assigned to the second match position stored in the second buffer and the match length when the first match position matches the second match position, and generating second compressed data including the first match position and the match length when the first match position does not match the second match position.

A method for compressing input first data, comprising:

• calculating a first hash value from at least a part of the first data;
• acquiring a match position stored in a table in association with a second hash value matching the first hash value by referring to the table in which the second hash value calculated from at least a part of previously input second data and a match position indicating a position of the second data in a buffer in which the second data is stored are stored in association with each other;
• searching for the second data at least partially matching the first data from the buffer based on the acquired match position;
• acquiring a match length indicating a matched length of the first data and the searched second data;
• entropy encoding the first hash value and the match length;
• and
• generating compressed data including the entropy-encoded hash value and match length.

A method for decompressing compressed data that includes a first hash value calculated from first data input in a compression device and a first match length indicating a matched length of second data at least partially matching the first data searched from a first buffer in which the second data previously input in the compression device is stored and the first data, the first hash value and the first match length being entropy-encoded, the method comprising:

• decoding the first hash value and first match length included in the compressed data;
• acquiring a match position stored in a table in association with a second hash value matching the decoded first hash value by referring to the table in which the second hash value previously cut out from the compressed data and a match position indicating the position of the second data in a second buffer in which the second hash value calculated from at least a part of the second data based on the second match length and the second data are stored are stored in association with each other;
• and
• reading the second data from the second buffer based on the acquired match position and generating the first data by shaping the second data based on the decoded match length.